我们可以使用 OR 选择查询在 data.table 中进行二进制搜索吗 [英] Can we do binary search in data.table with OR select queries
问题描述
按照上一个问题使用data.table
DT = data.table(x=sample(letters,1e7,T),y=sample(1:25,1e7,T),rnorm(1e7))
setkey(DT,x,y)
我们可以使用二分查找吗
Can we use binary search to find
DT[x=='a' | y==25]
记住 DT[J('a',25)] == DT[x=='a' &y==25]
推荐答案
是的:
为了进行二元搜索，我们需要适当的索引.
Yes:
In order to do a binary serach, we need the appropriate indices.
indx <- rbind(DT[y==25, list(y=25), by=x], DT[.("a"), list(x="a"), by=y], use.names=TRUE)
indx <- setdiff(indx, setdiff(indx, unique(DT[, key(DT), with=FALSE])))
indx
DT[.(indx)]
<小时>
基准测试:
与矢量化搜索相比，这为我们提供了 10 倍以上的改进.
identical(setkey(DT[.(indx)]), setkey(DT[x=="a" | y == 25]))
# [1] TRUE
library(microbenchmark)
microbenchmark(UsingIndx = DT[.(indx)], UsingVecSearch = DT[x=="a" | y == 25], times=100 )
Unit: milliseconds
expr min lq median uq max
1 UsingIndx 34.27562 41.70119 48.13215 49.29752 231.1669
2 UsingVecSearch 506.62670 545.85673 636.67701 680.93894 802.0842
<小时><小时>
为方便起见，我们可以将代码的创建索引"部分包装成一个漂亮的函数，这样我们就可以在一行中调用它.例如:
For convenience, we can wrap the "creating the index" portion of the code into a nice function, so that we can then call it in a single line. For example:
DT[.(OrIndx("a", 25, DT))]
其中OrIndx()定义如下:
OrIndx <- function(xval, yval, DT) {
# TODO: Allow for arbitrary columns and column names
if(!is.data.table(DT))
stop("DT is not a data.table")
# create all appropriate combinations
indx <- rbind(DT[y==yval, list(y=yval), by=x], DT[.(xval), list(x=xval), by=y], use.names=TRUE)
# take out any combinations in indx that are not actually present in DT and return
return( setdiff(indx, setdiff(indx, unique(DT[, key(DT), with=FALSE]))) )
}
解释:
这里的想法是执行或"搜索需要某种形式的组合.
在标准向量搜索中，这种组合是每个单独向量搜索的结果.
Explanation:
The idea here is that performing an "or" serach requires some form of combination.
In a standard vector search, this combination is of the results of each individual vector serach.
data.table 通过允许诸如
data.table offers some great speed improvements by allowing seraches such as
DT[.(c("cdf", "tmb"), c(25, 3))]
因此，问题的自然解决方案是使用:
Therefore, a natural solution to the question would be to use:
DT[.(c(<all values of x>, "a"), c(25, <all values of y>))]
唯一的问题是回收不能正确排列.
最好有一个像
The only problem is that the recycling would not line up properly.
It would be ideal to have an option like
DT[.( list( c(unique(x), y=25), c(x="a", y=unique(y) ) )]
但据我所知，这还没有实施(还没有！)
因此，我们可以采取适当的组合.
上面的函数 OrIndx 正是这样做的.(它又快又脏，而且有更有效的方法来创建索引)
But as far as I can tell that has not been implemented (yet!)
So instead, we can take appropriate combinations.
The function OrIndx above does exactly that. (it s quick & dirty and there are more efficient ways of creating the index)
根据@Aruns 的建议，我们包括
As per @Aruns suggestion, we include
rbind(DT[J("a")], DT[J(setdiff(unique(x), "a"), 25)])
rbindlist(list( DT[J("a")], DT[J(setdiff(unique(x), "a"), 25)] ))
在 1e6 和 1e7 行上测试:
Tested on 1e6 and 1e7 rows:
## Using 1 Million rows
> microbenchmark(Using_Indx = DT[.(indx)], Using_RbindList = rbindlist(list(DT[J("a")], DT[J(setdiff(unique(x), "a"), 25)])), Using_Rbind = rbind(DT[J("a")], DT[J(setdiff(unique(x), "a"), 25)]), Using_VecSearch = DT[x=="a" | y == 25], times=70L )
Unit: milliseconds
expr min lq median uq max
1 Using_Indx 4.865089 5.755615 5.813938 5.957352 6.880743
2 Using_Rbind 42.657953 49.239558 49.682407 50.505977 139.770670
3 Using_RbindList 36.319170 44.169151 44.484350 45.279158 155.361338
4 Using_VecSearch 49.003307 64.030384 64.443666 65.123886 150.099946
## Using 10 Milliion rows
Unit: milliseconds
expr min lq median uq max
1 Using_Indx 33.71108 47.5402 48.7574 50.75285 122.0950
2 Using_rbind 492.38244 535.6062 565.8623 590.92841 727.3907
3 Using_RbindList 436.29325 478.3626 507.4665 525.25980 657.6639
4 Using_VecSearch 511.86248 607.8046 643.9822 688.36733 765.3997
# Making sure all the same results:
> identical(setkey(DT[.(indx)]), setkey(DT[x=="a" | y == 25]))
[1] TRUE
> identical(setkey(DT[.(indx)]), setkey(rbind(DT[J("a")], DT[J(setdiff(unique(x), "a"), 25)])))
[1] TRUE
请注意，对于小表(少于 15K 行)，向量搜索更快(对于非常小的表，大约快两倍)
Note that for SMALL tabbles (less than 15K rows), vector search is faster (for really small tables, about twice as fast)
## Using 100 Rows
> microbenchmark(Using_Indx = DT[.(indx)], Using_RbindList = rbindlist(list(DT[J("a")], DT[J(setdiff(unique(x), "a"), 25)])), Using_rbind = rbind(DT[J("a")], DT[J(setdiff(unique(x), "a"), 25)]), Using_VecSearch = DT[x=="a" | y == 25], times=150L )
Unit: microseconds
expr min lq median uq max
1 Using_Indx 884.819 901.854 917.3715 933.642 9740.046
2 Using_rbind 2385.842 2424.893 2462.5210 2502.704 4266.637
3 Using_RbindList 1962.504 2005.594 2027.4085 2069.516 4238.146
4 Using_VecSearch 386.867 401.328 407.5730 420.647 2908.090
这种模式一直保持到大约 10,000 行，此时我们开始看到收益:
This pattern holds until about 10,000 rows, at which point we start to see the gains:
## 10,000 Rows
Unit: microseconds
expr min lq median uq max
1 Using_Indx 891.374 921.784 931.6585 956.737 3780.971
4 Using_VecSearch 796.316 815.965 824.1480 845.151 2531.314
## 15,000 Rows
Unit: microseconds
expr min lq median uq max
1 Using_Indx 913.963 939.198 954.518 986.609 2900.174
4 Using_VecSearch 1018.830 1041.449 1053.098 1072.188 8418.470
## 30,000 Rows
Unit: microseconds
expr min lq median uq max
1 Using_Indx 964.402 995.883 1018.535 1045.908 5999.390
4 Using_VecSearch 1649.231 1709.090 1801.760 1927.976 8868.470
## 100,000 Rows
Unit: milliseconds
expr min lq median uq max
1 Using_Indx 1.142318 1.181023 1.198611 1.268417 3.611945
4 Using_VecSearch 4.663948 4.763179 5.052995 6.058354 12.133510
## 10,000,000 Rows (only ran 30 reps for this one)
Unit: milliseconds
expr min lq median uq max
1 Using_Indx 33.95004 42.24995 48.90363 50.15424 177.0991
2 Using_VecSearch 512.34760 557.02867 622.37670 662.14323 861.3465
这篇关于我们可以使用 OR 选择查询在 data.table 中进行二进制搜索吗的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
