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

Question

原生R中的哪个()方法使用什么算法来搜索数据帧？例如，如果我调用

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

R使用什么算法来搜索此数据帧？二分搜索？线性搜索？我在任何地方都找不到关于这方面的文档。如果它没有使用上述两种算法中的任何一种，它使用的是什么算法，它的时间复杂度是什么？

Answer 1

如果你对这个问题感兴趣，你可以看看the datatable vignette on the subject

默认情况下，R使用线性搜索。它扫描整个向量。这是支持带索引表的binary search的data.table的伟大特性之一。在data.table中，索引数据集的元素在内存中以物理方式排序，因此在其中搜索值非常快。data.table(请参阅here)中的二级索引将启用二进制搜索，但不会在连续的内存插槽中对数据进行物理重新排序。

也许data.table vignette更明确：

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

此外，由于我们无需创建那些巨大的逻辑向量(等于data.table中的行数)而直接获得匹配的行索引，因此它也非常有效地利用了内存。

示例

让我们通过一个例子来看看。microbenchmark包用于比较。

我们将进行比较：

在具有主键的data.frame

• Filter上使用dplyr

• (Linear)搜索在data.table

• (Binary)上进行used)

• (Binary)搜索(
• (线性)在具有主键的data.table上进行used)
• (Binary)搜索(setkey是在具有辅键的data.table上进行data.table
• (Binary)搜索(使用setindex)

让我们创建所需的所有部分：

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

到目前为止，base R方法是最慢的。在本例中，使用辅助索引并不能显著提高性能。但是主键就是这样！

ggplot2::autoplot(m)

​

​