使用二进制搜索而不是矢量扫描,仅按2列密钥的第二列对data.table进行子集化

Question

我最近发现了二进制搜索data.table.如果表格在多个键上排序,则只能在第二个键上搜索？

DT = data.table(x=sample(letters,1e7,T),y=sample(1:25,1e7,T),rnorm(1e7))
setkey(DT,x,y)
#R> DT[J('x')]
#        x  y       V3
#     1: x  1  0.89109
#     2: x  1 -2.01457
#    ---              
#384922: x 25  0.09676
#384923: x 25  0.25168
#R> DT[J('x',3)]
#       x y       V3
#    1: x 3 -0.88165
#    2: x 3  1.51028
#   ---             
#15383: x 3 -1.62218
#15384: x 3 -0.63601

编辑:感谢@Arun

R> system.time(DT[J(unique(x), 25)])
   user  system elapsed 
  0.220   0.068   0.288 
R> system.time(DT[y==25])
   user  system elapsed 
  0.268   0.092   0.359

Answer 1

是的,您可以将所有值传递给第一个键值,并使用第二个键的特定值传递子集.

DT[J(unique(x), 25), nomatch=0]

如果您需要在第二个键中使用多个值进行子集(例如,相当于DT[y %in% 25:24]),则可以使用更通用的解决方案CJ

DT[CJ(unique(x), 25:24), nomatch=0]

请注意,CJ默认情况下会对列进行排序并将键设置为所有列,这意味着结果也将进行排序.如果这不可取,你应该使用sorted=FALSE

DT[CJ(unique(x), 25:24, sorted=FALSE), nomatch=0]

还有一个功能请求,以便data.table将来添加辅助密钥.我相信计划是添加一个新功能set2key.

FR#1007内置辅助密钥

还有merge,有一种方法data.table.它为您构建了内部的二级密钥,因此应该比基本合并更快.见?merge.data.table.

Answer 2

基于这个电子邮件线程,我写了以下函数:

create_index = function(dt, ..., verbose = getOption("datatable.verbose")) {
  cols = data.table:::getdots()
  res = dt[, cols, with=FALSE]
  res[, i:=1:nrow(dt)]
  setkeyv(res, cols, verbose = verbose)
}

JI = function(index, ...) {
  index[J(...),i]$i
}

以下是我的系统上具有更大DT(1e8行)的结果:

> system.time(DT[J("c")])
   user  system elapsed 
  0.168   0.136   0.306 

> system.time(DT[J(unique(x), 25)])
   user  system elapsed 
  2.472   1.508   3.980 
> system.time(DT[y==25])
   user  system elapsed 
  4.532   2.149   6.674 

> system.time(IDX_y <- create_index(DT, y))
   user  system elapsed 
  3.076   2.428   5.503 
> system.time(DT[JI(IDX_y, 25)])
   user  system elapsed 
  0.512   0.320   0.831     

如果您多次使用索引,那么它是值得的.