r - 在大字段中搜索值时，如果字段已排序，效率会有所不同吗

Question

我经常需要在一个字段中搜索一个值，我搜索的字段很大而且我会重复这样做。但通常我正在搜索值(value)的字段会进入我的预排序数据。与排序字段相比，在未排序字段中搜索值是否花费更多？如果是这样，我们是否必须在搜索我们想要的内容之前告诉 R 该字段已排序，如果是的话如何？

set.seed(4)
v1<- runif(1000000)
x <- v1[384932]
v2<- sort(v1)

我们正在两个向量中搜索 x

Answer 1

Package data.table 对此进行了优化:

which(x == v1)
#[1] 384932

library(data.table)
DT <- data.table(v = v1)
DT[, ind := .I]
DT[v == x,]
#          v    ind
#1: 0.807405 384932

library(microbenchmark)
microbenchmark(which(x == v1),
               DT[v == x,])
#Unit: microseconds
#           expr      min        lq     mean   median       uq      max neval cld
# which(x == v1) 6507.923 6735.3560 6994.638 6930.145 7038.240 9693.825   100   b
#   DT[v == x, ]  813.030  849.9855 1082.465 1228.628 1258.347 1456.677   100  a 

引用 1.9.4 新闻:

“DT[column==value] 和 DT[column %in% values] 现在优化为使用 DT 的键当 key(DT)[1]=="column" 时，否则会自动添加辅助键(又名索引)，因此下一个 DT[column==value] 是快得多。无需更改代码；现有代码会自动受益。”