使用二进制搜索按范围子集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 

以上不使用键(矢量扫描),加速不是那么戏剧化.使用二进制搜索对data.table的数值范围进行子集化的语法是什么？我在文档中找不到一个好例子; 如果有人可以使用上面的玩具数据提供一个例子,将会有所帮助.

编辑:这个问题是类似的,但仍然没有演示如何按范围子集: data.table:矢量扫描v二进制搜索与数字列 - 超慢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,date),(id1,id2,date,time)等.

但是,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 

因此,矢量扫描方法比设置密钥更快(我们甚至还没有使用密钥).鉴于数据是浮点数并且几乎是独一无二的,所以这并不太令人惊讶,但我认为这是一个非常快的时间setkey来完全随机和几乎独特的双打.

比较基数,例如,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)]就是丑陋和复制.我想不出一个像这样使用密钥的好方法来做这个y<7部分.在其他示例数据中,我们做了类似的事情,DT[.(unique(x), 7), which=TRUE, roll=TRUE]但在这种情况下,数据是如此独特,浮动点会变慢.

理想情况下,此任务需要范围连接(FR#203)实现.此示例中的语法可能是:

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

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

在我们继续这样的事情之前,需要首先完成v1.9.2中的加速.如果您setkey在v1.8.10中尝试这些数据,您会发现v1.9.2明显更快.

也可以看看 :

如何在条件下自行加入data.table

删除data.table中的范围