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，自foo[4]-foo[1]=7-1<10以来最大的j是4。因此bar的第一项是4）。

我们可以使用for和while循环来容易地计算bar。但我正在R中寻找一个高效的代码。有什么想法吗？

Answer 1

使用非等联接的更新解决方案：

最近，非equi联接在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

在100000个元素上，这比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

100000个号码的计时：

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 

Answer 2

尝试

 sapply(foo, function(x) {m1 <-foo-x; which.max(m1[m1<10])})
 #[1] 4 4 5 5 6 7 8 8 9

Answer 3

假设没有NA值：

apply(as.matrix(dist(foo)), 1, function(x) {
  which.max(cumsum(x < 10))  
  })
#1 2 3 4 5 6 7 8 9 
#4 4 5 5 6 7 8 8 9 

这里有一个只使用稀疏矩阵的解决方案：

library(spam)
res <- apply.spam(as.spam(dist(foo)), 2, function(x) {
  test <- cumsum(x < 10)
  if (sum(test) > 0 ) which.max(test) else (0)
  }) + seq_along(foo)
res[length(res)] <- length(res)
#[1] 4 4 5 5 6 7 8 8 9