使用数据 table 进行二分查找，包括第二个、第三个、第四个……最接近的值
binary search with data table, include second, third, fourth,.. nearest value
假设我有两个向量。一个是参考 vector/list，它包括所有感兴趣的值和一个可能包含任何可能值的样本向量。现在我想在参考列表中找到我的样本的匹配项，具有一定的公差，该公差不固定并且依赖于向量内的比较值：
matches: abs(((referencelist - sample[i])/sample[i])*10^6)) < 0.5
舍入两个向量是没有选择的！
例如考虑：
referencelist <- read.table(header=TRUE, text="value name
154.00312 A
154.07685 B
154.21452 C
154.49545 D
156.77310 E
156.83991 F
159.02992 G
159.65553 H
159.93843 I")
sample <- c(154.00315, 159.02991, 154.07688, 156.77312)
所以我得到了结果：
name value reference
1 A 154.00315 154.00312
2 G 159.02991 159.02992
3 B 154.07688 154.07685
4 E 156.77312 156.77310
我在这里得到了漂亮且非常快速的二进制搜索解决方案：
library(data.table)
dt <- as.data.table(referencelist)
setattr(dt, "sorted", "value")
tol <- 0.5
dt2 <- dt[J(sample), .(.I, ref = value, name), roll = "nearest", by = .EACHI]
dt2[, diff := abs(ref - value) / value * 1e6]
dt2[diff <= tol]
# value I ref name diff
# 1: 154.0032 1 154.0031 A 0.19480121
# 2: 159.0299 7 159.0299 G 0.06288125
# 3: 154.0769 2 154.0769 B 0.19470799
# 4: 156.7731 5 156.7731 E 0.12757289
但是这里出现了其他问题，我真的不知道如何继续，很乐意提供任何进一步的帮助：
首先： 当我有例如参考列表中的 F = 154.0033。然后我的样本值154.0032不仅在上面A的公差范围内，而且在F的范围内。然而data.table方法只给我最接近的值。我怎样才能获得第二个、第三个……等等最接近的值，但仍然使用 data.table，因为这是对我的大型数据集足够快的唯一解决方案。如果有可能获得行号，则可能只是从参考列表中最近匹配的行开始 +-x 以获得公差范围内的所有可能值，因为它是有序的。那么有没有像
dt2 <- dt[J(sample), .(.I, ref = value, name), roll = "nearest" +-x , by = .EACHI]
?
第二：当使用
dt2 <- dt[J(sample), .(.I, ref = value, name), roll = "nearest", by = .EACHI]
样本只是一个向量。但是，如果样本是一个数据框，其列 value 是与引用列表匹配的关键，但还有其他 100 多列应保留在结果 data.table 中，该怎么办？我真的试图理解 data.tables 的语法，但没有成功。也有人可以帮助我吗？
这里举个例子：
sample <- data.frame(value=c(154.00315, 159.02991, 154.07688, 156.77312),replicate(100,sample(0:1,4,rep=TRUE)))
例如得到这样的东西：
value I ref name diff X1 ... X100
# 1: 154.0032 1 154.0031 A 0.19480121 X X
# 2: 159.0299 7 159.0299 G 0.06288125 X X
# 3: 154.0769 2 154.0769 B 0.19470799 X X
# 4: 156.7731 5 156.7731 E 0.12757289 X X
你的匹配条件
abs(((referencelist - sample[i])/sample[i])*10^6)) < 0.5
可以重写为
sample[i] * (1 - eps) < referencelist < sample[i] * (1 + eps)
与 eps = 0.5E-6.
使用它，我们可以使用 非等值连接 为每个 referencelist 找到 all 个匹配项 sample:
library(data.table)
options(digits = 10)
eps <- 0.5E-6 # tol * 1E6
setDT(referencelist)[.(value = sample,
lower = sample * (1 - eps),
upper = sample * (1 + eps)),
on = .(ref > lower, ref < upper), .(name, value, reference = x.ref)]
重现预期结果：
name value reference
1: A 154.00315 154.00312
2: G 159.02991 159.02992
3: B 154.07688 154.07685
4: E 156.77312 156.77310
比方说，我们用 F = 154.00320 修改了 referencelist2 那么这也会被捕获：
setDT(referencelist2)[.(value = sample,
lower = sample * (1 - eps),
upper = sample * (1 + eps)),
on = .(ref > lower, ref < upper), .(name, value, reference = x.ref)]
name value reference
1: A 154.00315 154.00312
2: F 154.00315 154.00320
3: G 159.02991 159.02992
4: B 154.07688 154.07685
5: E 156.77312 156.77310
顺便说一下，表达式
.(value = sample, lower = sample * (1 - eps), upper = sample * (1 + eps))
正在动态创建 data.table。我们可以在这里加入另一个 datat.table。
编辑：sample 作为数据框给出
为了说明他问题的第二部分，OP 给出了 sample 作为具有 100 多列的数据框：
sample <- data.frame(value = c(154.00315, 159.02991, 154.07688, 156.77312),
replicate(100L, sample(0:1, 4L, rep = TRUE)))
这也可以通过非等连接来处理，但需要进行一些修改：
eps <- 0.5E-6 # tol * 1E6
setDT(referencelist2)[
# modify referencelist2 by copying ref column to preserve its value
, reference := ref][
# modify sample by appending lower and upper for non-equi join
setDT(sample)[, c("lower", "upper") := .(value * (1 - eps), value * (1 + eps))],
on = .(ref > lower, ref < upper)][
# remove upper and lower columns (renamed to ref and ref.1 during the join)
, -c("ref", "ref.1")]
name reference value X1 X2 X3 X4 X5 X6 X7 X8 X9 X10 X11 X12 X13 X14 X15 X16 ...
1: A 154.00312 154.00315 0 1 1 0 0 0 0 1 0 0 0 1 0 0 0 0 0
2: F 154.00320 154.00315 0 1 1 0 0 0 0 1 0 0 0 1 0 0 0 0 0
3: G 159.02992 159.02991 0 0 0 1 0 1 1 0 0 0 1 1 1 0 1 1 0
4: B 154.07685 154.07688 0 1 1 1 1 1 1 1 1 1 0 1 1 1 0 0 0
5: E 156.77310 156.77312 1 0 1 0 1 0 0 1 1 1 0 1 0 1 0 1 0
假设我有两个向量。一个是参考 vector/list，它包括所有感兴趣的值和一个可能包含任何可能值的样本向量。现在我想在参考列表中找到我的样本的匹配项，具有一定的公差，该公差不固定并且依赖于向量内的比较值：
matches: abs(((referencelist - sample[i])/sample[i])*10^6)) < 0.5
舍入两个向量是没有选择的！
例如考虑：
referencelist <- read.table(header=TRUE, text="value name
154.00312 A
154.07685 B
154.21452 C
154.49545 D
156.77310 E
156.83991 F
159.02992 G
159.65553 H
159.93843 I")
sample <- c(154.00315, 159.02991, 154.07688, 156.77312)
所以我得到了结果：
name value reference
1 A 154.00315 154.00312
2 G 159.02991 159.02992
3 B 154.07688 154.07685
4 E 156.77312 156.77310
我在这里得到了漂亮且非常快速的二进制搜索解决方案：
library(data.table)
dt <- as.data.table(referencelist)
setattr(dt, "sorted", "value")
tol <- 0.5
dt2 <- dt[J(sample), .(.I, ref = value, name), roll = "nearest", by = .EACHI]
dt2[, diff := abs(ref - value) / value * 1e6]
dt2[diff <= tol]
# value I ref name diff
# 1: 154.0032 1 154.0031 A 0.19480121
# 2: 159.0299 7 159.0299 G 0.06288125
# 3: 154.0769 2 154.0769 B 0.19470799
# 4: 156.7731 5 156.7731 E 0.12757289
但是这里出现了其他问题，我真的不知道如何继续，很乐意提供任何进一步的帮助：
首先： 当我有例如参考列表中的 F = 154.0033。然后我的样本值154.0032不仅在上面A的公差范围内，而且在F的范围内。然而data.table方法只给我最接近的值。我怎样才能获得第二个、第三个……等等最接近的值，但仍然使用 data.table，因为这是对我的大型数据集足够快的唯一解决方案。如果有可能获得行号，则可能只是从参考列表中最近匹配的行开始 +-x 以获得公差范围内的所有可能值，因为它是有序的。那么有没有像
dt2 <- dt[J(sample), .(.I, ref = value, name), roll = "nearest" +-x , by = .EACHI]
?
第二：当使用
dt2 <- dt[J(sample), .(.I, ref = value, name), roll = "nearest", by = .EACHI]
样本只是一个向量。但是，如果样本是一个数据框，其列 value 是与引用列表匹配的关键，但还有其他 100 多列应保留在结果 data.table 中，该怎么办？我真的试图理解 data.tables 的语法，但没有成功。也有人可以帮助我吗？
这里举个例子：
sample <- data.frame(value=c(154.00315, 159.02991, 154.07688, 156.77312),replicate(100,sample(0:1,4,rep=TRUE)))
例如得到这样的东西：
value I ref name diff X1 ... X100
# 1: 154.0032 1 154.0031 A 0.19480121 X X
# 2: 159.0299 7 159.0299 G 0.06288125 X X
# 3: 154.0769 2 154.0769 B 0.19470799 X X
# 4: 156.7731 5 156.7731 E 0.12757289 X X
你的匹配条件
abs(((referencelist - sample[i])/sample[i])*10^6)) < 0.5
可以重写为
sample[i] * (1 - eps) < referencelist < sample[i] * (1 + eps)
与 eps = 0.5E-6.
使用它，我们可以使用 非等值连接 为每个 referencelist 找到 all 个匹配项 sample:
library(data.table)
options(digits = 10)
eps <- 0.5E-6 # tol * 1E6
setDT(referencelist)[.(value = sample,
lower = sample * (1 - eps),
upper = sample * (1 + eps)),
on = .(ref > lower, ref < upper), .(name, value, reference = x.ref)]
重现预期结果：
name value reference 1: A 154.00315 154.00312 2: G 159.02991 159.02992 3: B 154.07688 154.07685 4: E 156.77312 156.77310
比方说，我们用 F = 154.00320 修改了 referencelist2 那么这也会被捕获：
setDT(referencelist2)[.(value = sample,
lower = sample * (1 - eps),
upper = sample * (1 + eps)),
on = .(ref > lower, ref < upper), .(name, value, reference = x.ref)]
name value reference 1: A 154.00315 154.00312 2: F 154.00315 154.00320 3: G 159.02991 159.02992 4: B 154.07688 154.07685 5: E 156.77312 156.77310
顺便说一下，表达式
.(value = sample, lower = sample * (1 - eps), upper = sample * (1 + eps))
正在动态创建 data.table。我们可以在这里加入另一个 datat.table。
编辑：sample 作为数据框给出
为了说明他问题的第二部分，OP 给出了 sample 作为具有 100 多列的数据框：
sample <- data.frame(value = c(154.00315, 159.02991, 154.07688, 156.77312),
replicate(100L, sample(0:1, 4L, rep = TRUE)))
这也可以通过非等连接来处理，但需要进行一些修改：
eps <- 0.5E-6 # tol * 1E6
setDT(referencelist2)[
# modify referencelist2 by copying ref column to preserve its value
, reference := ref][
# modify sample by appending lower and upper for non-equi join
setDT(sample)[, c("lower", "upper") := .(value * (1 - eps), value * (1 + eps))],
on = .(ref > lower, ref < upper)][
# remove upper and lower columns (renamed to ref and ref.1 during the join)
, -c("ref", "ref.1")]
name reference value X1 X2 X3 X4 X5 X6 X7 X8 X9 X10 X11 X12 X13 X14 X15 X16 ... 1: A 154.00312 154.00315 0 1 1 0 0 0 0 1 0 0 0 1 0 0 0 0 0 2: F 154.00320 154.00315 0 1 1 0 0 0 0 1 0 0 0 1 0 0 0 0 0 3: G 159.02992 159.02991 0 0 0 1 0 1 1 0 0 0 1 1 1 0 1 1 0 4: B 154.07685 154.07688 0 1 1 1 1 1 1 1 1 1 0 1 1 1 0 0 0 5: E 156.77310 156.77312 1 0 1 0 1 0 0 1 1 1 0 1 0 1 0 1 0