r - 排序向量的有限距离内最远的元素

Question

我们有一个排序向量 foo ，对于每个元素i我们要找到最大的j这样foo[j]-foo[i] < 10 。例如当

foo <- c(1,2,5,7,13,17,25,33,85)

答案是:

bar <- c(4,4,5,5,6,7,8,8,9)

(对于 i=1 ，自 j 以来最大的 foo[4]-foo[1]=7-1<10 是 4。因此 bar 的第一项是 4)。

我们可以轻松计算bar使用for和while环形。但我正在寻找 R 中的高效代码。有什么想法吗？

Answer 1

使用非等值连接更新了解决方案:

最近，非等价连接在 current development version of data.table, v1.9.7 中实现。使用此功能非常简单:

require(data.table) # v1.9.7+
dt1 = data.table(x=foo)
dt2 = data.table(y=foo+10L)
dt1[dt2, on=.(x < y), mult="last", which=TRUE]
# [1] 4 4 5 5 6 7 8 8 9

在 100,000 个元素上，这比 foverlaps 更快:

set.seed(45L)
foo <- sort(sample(1e6, 1e5, FALSE))
dt1 = data.table(x=foo)
dt2 = data.table(y=foo+10L)
system.time(ans <- dt1[dt2, on=.(x < y), mult="last", which=TRUE])
#    user  system elapsed 
#   0.011   0.001   0.011 

请注意，此操作可以直接完成，如下所示:

ans <- data.table(x=foo)[.(y=x+10L), on=.(x < y), mult="last", which=TRUE]

---

使用foverlaps的旧方法:

这是一种可能可以更好扩展的方法。使用 data.table 版本 1.9.4 中的重叠范围连接函数 foverlaps():

require(data.table) ## 1.9.4+
x = data.table(start=foo, end=foo+9L)
lookup = data.table(start=foo, end=foo)
setkey(lookup) ## order doesn't change, as 'foo' is already sorted
foverlaps(x, lookup, mult="last", which=TRUE)
# [1] 4 4 5 5 6 7 8 8 9

100,000 个数字的计时:

set.seed(45L)
foo <- sort(sample(1e6, 1e5, FALSE))
arun <- function(foo) {
    x = data.table(start=foo, end=foo+9L)
    lookup = data.table(start=foo, end=foo)
    setkey(lookup)
    foverlaps(x, lookup, mult="last", which=TRUE)
}
system.time(arun(foo))
#    user  system elapsed 
#  0.142   0.009   0.153