r - data.table 是否实现了基于二分查找的快速范围子集？那是什么语法？

Question

我有一个浮点数向量。我想在各种范围内反复找到该向量的子集。我当前的语法( DT[x > 1.8 & x < 2.9] )似乎是矢量扫描(相对较慢)。

是否有更快的语法利用二进制搜索来搜索基于范围/间隔的 data.tables 子设置？

例子:

set.seed(123L)
x = runif(1E6)
DT = data.table(x, key = "x")

# For foverlaps()
DT[,xtemp:=x]
range = data.table(start = 0.04, end = 0.5, key=c("start", "end"))


microbenchmark::microbenchmark(
    DT[x < 0.5 & x > 0.04], 
    x[x < 0.5 & x > 0.04],
    foverlaps(DT, range, by.x = c("x", "xtemp"))
    )

Unit: milliseconds
                                         expr       min        lq      mean    median        uq      max neval
                       DT[x < 0.5 & x > 0.04]  12.65391  16.10852  18.43412  17.23268  17.76868 104.1112   100
                        x[x < 0.5 & x > 0.04]  16.48126  19.63882  21.65813  20.31534  20.95264 113.7965   100
 foverlaps(DT, range, by.x = c("x", "xtemp")) 116.72732 131.93093 145.56821 140.09218 146.33287 226.6069   100

Answer 1

基于 the answer here ，这似乎是某种改进。但是，此方案中将包含等于 0.5 的值:

bs <- function() DT[{ind <- DT[.(c(0.04, 0.5)), which=TRUE, roll=TRUE]; (ind[1]+1):ind[2]}]
vs <- function() x[x < 0.5 & x > 0.04]

x = runif(1E6)
DT = data.table(x, key = "x")

microbenchmark::microbenchmark(
    bs(), 
    vs()
)

#Unit: milliseconds
# expr       min        lq      mean   median        uq        max neval
# bs()  3.594993  4.150932  5.002947  4.44695  4.952283   9.750284   100
# vs() 15.054460 16.217198 18.999877 17.45298 19.554958 113.623699   100

如果我们修改 vs()成为:

vs <- function() x[x <= 0.5 & x > 0.04]

两种方法的结果是一样的:

identical(bs()$x, sort(vs()))
# [1] TRUE