r - R 使用什么算法搜索数据帧？

Question

本机 R 中的 which() 方法使用什么算法来搜索数据帧？例如，如果我打电话

df[which(df$parameter == 3)]

R 使用什么算法来搜索这个数据框？二进制搜索？线性搜索？我在任何地方都找不到这方面的文档。如果它不使用上述任何一种，它使用什么算法，它的时间复杂度是多少？

标签： ralgorithmsearch

Answer 1

如果您对此问题感兴趣，可以查看有关该主题的数据表小插图

默认情况下，R使用线性搜索。它扫描整个向量。这是data.table启用binary search索引表的一大特色。在data.table中，索引数据集将具有在内存中物理排序的元素，因此在其中搜索值非常快。data.table（见这里）中的二级索引将启用二分搜索，但数据不会在连续的内存插槽中物理重新排序。

也许data.table小插图更明确：

可以看出，每次搜索我们都会将搜索次数减少一半。这就是为什么基于二进制搜索的子集非常快的原因。由于 data.tables 的每一列的行在内存中具有连续的位置，因此操作以非常缓存有效的方式执行（也有助于提高速度）。

此外，由于我们直接获得匹配的行索引，而无需创建那些巨大的逻辑向量（等于 data.table 中的行数），因此内存效率也很高。

例子

让我们看一个例子。该包microbenchmark用于比较。

我们将比较：

• （线性）搜索data.frame
• 过滤dplyr
• （线性）搜索data.table
• data.table使用主键（setkey使用）在 a 上进行（二进制）搜索
• data.table使用辅助键（setindex使用）在 a 上进行（二进制）搜索

让我们创建所需的每个部分：

library(data.table)
library(dplyr)

df <- data.frame(
  x = rnorm(1e6),
  y = rnorm(1e6)
)
dt <- as.data.table(df) 

dt2 <- copy(dt)
dt3 <- copy(dt)

我们将设置主键dt2（二进制搜索+内存中重新排序的对象）和辅助键dt3（二进制搜索但没有在内存中重新排序）

setkey(dt2, x)
setindex(dt3, x)

微基准：

m <- microbenchmark::microbenchmark(
  df[df$x<0,],
  df %>% dplyr::filter(x<0),
  dt[x<0],
  dt2[x<0],
  dt3[x<0],
  times = 20L
)

m 

Unit: milliseconds
                        expr      min       lq     mean   median       uq       max neval
              df[df$x < 0, ] 56.56557 57.54392 66.97838 61.39609 75.30391  91.42418    20
 df %>% dplyr::filter(x < 0) 23.24242 24.15183 34.64290 26.02232 34.91405 143.10476    20
                   dt[x < 0] 18.32496 18.96585 21.35255 20.25604 23.02666  33.25656    20
                  dt2[x < 0] 10.85129 10.94804 11.92941 11.21601 11.80469  18.29040    20
                  dt3[x < 0] 18.37789 18.47568 19.51928 18.76135 19.39782  26.90826    20

到目前为止，基本 R 方法是最慢的。在这个例子中，使用二级索引并没有提高那么多的性能。但是主键可以！

ggplot2::autoplot(m)