r - data.table:使用数字列进行矢量扫描 v 二进制搜索 - 超慢 setkey

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))

叶子 nums如类型 numeric不是 integer .这有很大的不同。 data.table 常见问题解答和介绍面向 integer和 character列;你不会看到 setkey那些类型的速度很慢。例如 :

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

还有两点……

首先，在data.table v1.8.11的当前开发版本中，排序/排序操作要快得多。 @jihoward 关于对数字列进行排序是更耗时的操作是正确的。但是，它在 1.8.11 中仍然快了大约 5-8 倍(因为 6 遍基数顺序实现，检查 this post)。比较 setkey 所用的时间1.8.10 和 1.8.11 之间的操作:

# 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 重新排序(通过引用使内存占用非常小，查看 this post 以了解有关 setkey 的更多信息)。