data.table： 矢量扫描 v 二进制搜索与数字列 - 超慢设置键

Question

我正在尝试找到用几个数字列子集大数据集的最快方法。正如data.table所promise的，进行二进制搜索所需的时间比矢量扫描快得多。但是，二进制搜索需要事先执行setkey。正如您在这段代码中看到的，它需要非常长的时间！一旦您考虑到这段时间，矢量扫描就快得多：

set.seed(1)
n=10^7
nums <- round(runif(n,0,10000))
DT = data.table(s=sample(nums,n), exp=sample(nums,n), 
         init=sample(nums,n), contval=sample(nums,n))
this_s = DT[0.5*n,s] 
this_exp = DT[0.5*n,exp]
this_init = DT[0.5*n,init]
system.time(ans1<-DT[s==this_s&exp==this_exp&init==this_init,4,with=FALSE])
#   user  system elapsed 
#   0.65    0.01    0.67 
system.time(setkey(DT,s,exp,init))
#   user  system elapsed 
#  41.56    0.03   41.59 
system.time(ans2<-DT[J(this_s,this_exp,this_init),4,with=FALSE])
#   user  system elapsed 
#    0       0       0 
identical(ans1,ans2)
# [1] TRUE

我做错了什么吗？我已经阅读了data.table常见问题解答等。任何帮助都将不胜感激。

非常感谢。

Answer 1

该行：

nums <- round(runif(n,0,10000))

将数字保留为类型数字而不是整数。这有很大的不同。数据表常见问题解答和介绍面向整数和字符列;在这些类型上，您不会看到 setkey 很慢。例如：

nums <- as.integer(round(runif(n,0,10000)))
...
setkey(DT,s,exp,init)  # much faster now

还有两点...

首先，在当前的数据开发版本中，排序/排序操作要快得多。表v1.8.11。@jihoward关于数字列的排序是一个更耗时的操作的观点是正确的。但是，在1.8.11中，它仍然快了大约5-8倍（因为实现了6次基数顺序，请查看本文）。比较1.8.10和1.8.11中＜code＞设置键＜code＞操作所需的时间：

# v 1.8.11
system.time(setkey(DT,s,exp,init))
#    user  system elapsed 
#   8.358   0.375   8.844 

# v 1.8.10
system.time(setkey(DT,s,exp,init))
#   user  system elapsed 
# 66.609   0.489  75.216 

这是我的系统8.5倍的改进。所以，我的猜测是，这大约需要4.9秒。

第二，正如@Roland提到的，如果你的目标是执行几个子集化，而这就是你要做的全部，那么当然做setkey是没有意义的，因为它必须找到列的顺序，然后重新排序整个data.table(通过引用，以便内存占用非常少，查看这篇文章了解更多关于setkey的信息)。