r - 使用二分搜索按范围对 data.table 进行子集化

Question

为了使用二进制搜索，您如何通过数字范围对 data.table 进行子集化？

例如:

require(data.table)
set.seed(1)

x<-runif(10000000,min=0,max=10)
y<-runif(10000000,min=0,max=10)

DF<-data.frame(x,y)
DT<-data.table(x,y)

system.time(DFsub<-DF[DF$x>5 & DF$y<7,])
# user  system elapsed 
# 1.529   0.250   1.821 

#subset DT
system.time(DTsub<-DT[x>5 & y<7])
# user  system elapsed 
#0.716   0.119   0.841 

以上不使用 key (矢量扫描)，并且加速不是那么显着。使用二进制搜索对 data.table 的数字范围进行子集化的语法是什么？
我在文档中找不到很好的例子；如果有人可以使用上面的玩具 data.table 提供一个示例，那将会很有帮助。

编辑:这个问题很相似，但仍然没有演示如何按范围进行子集:
data.table: vector scan v binary search with numeric columns - super-slow setkey

Answer 1

有趣的问题。首先让我们看一下示例数据:

> print(DT)
                     x        y
       1: 2.607703e-07 5.748127
       2: 8.894131e-07 5.233994
       3: 1.098961e-06 9.834267
       4: 1.548324e-06 2.016585
       5: 1.569279e-06 7.957730
      ---                      
 9999996: 9.999996e+00 9.977782
 9999997: 9.999998e+00 2.666575
 9999998: 9.999999e+00 6.869967
 9999999: 9.999999e+00 1.953145
10000000: 1.000000e+01 4.001616
> length(DT$x)
[1] 10000000
> length(unique(DT$x))
[1] 9988478
> length(DT$y)
[1] 10000000
> length(unique(DT$y))
[1] 9988225
> DT[,.N,by=x][,table(N)]
N
      1       2       3 
9976965   11504       9 
> DT[,.N,by="x,y"][,table(N)]
N
       1 
10000000 
> 

因此，第一列中有近 1000 万个唯一的浮点值:几组大小为 2 和 3 行的组，但大多数为 1 行组。一旦包含第二列，就有 1000 万个大小为 1 行的唯一组。这是一个相当棘手的问题，因为 data.table专为分组数据而设计；例如，(id，日期)，(id1，id2，日期，时间)等。

然而， data.table和 setkey确实支持键中的浮点数据，所以让我们试一试。

在我的慢上网本上:

> system.time(setkey(DT,x,y))
   user  system elapsed 
  7.097   0.520   7.650 

> system.time(DT[x>5 & y<7])
   user  system elapsed 
  2.820   0.292   3.122 

所以矢量扫描方法比设置 key 更快(我们甚至还没有使用 key )。鉴于数据是浮点数且几乎是唯一的，所以这并不太令人惊讶，但我认为对于 setkey 来说这是一个相当快的时间。对 1000 万个完全随机且几乎独特的 double 进行排序。

例如，与 base 相比，只是排序 x甚至没有 y还有:

> system.time(base::order(x))
   user  system elapsed 
 72.445   0.292  73.072 

假设这个数据代表你的真实数据，你不想只做一次而是多次，所以愿意付出 setkey的代价。 ，第一步很清楚:

system.time(w <- DT[.(5),which=TRUE,roll=TRUE])
   user  system elapsed 
  0.004   0.000   0.003 
> w
[1] 4999902

但在这里我们被困住了。下一步如 DT[(w+1):nrow(DT)]是丑陋的副本。我想不出一个体面的方法来使用这里的 key 来做 y<7部分也是如此。在其他示例数据中，我们执行类似 DT[.(unique(x), 7), which=TRUE, roll=TRUE] 的操作但在这种情况下，数据是如此独特且浮点数会很慢。

理想情况下，此任务需要 range joins (FR#203)实现。此示例中的语法可能是:

DT[.( c(5,Inf), c(-Inf,7) )]

或者为了更容易， DT[x>5 & y<7]可以优化以在引擎盖下做到这一点。允许 i 中的两列范围连接到相应的 x 列可能非常有用，并且已经出现了好几次。

需要先完成 v1.9.2 中的加速，然后才能继续进行此类操作。如果您尝试 setkey在 v1.8.10 中的这些数据上，您会发现 v1.9.2 明显更快。

也可以看看 :

How to self join a data.table on a condition

Remove a range in data.table