R列表中名称查找的时间复杂度是多少？

Question

我拼命想通过谷歌找到答案而失败了.我本人即将自己做基准测试,但认为这里的某个人可能知道答案,或者至少是一个记录在案的参考资料.

为了扩展我的问题:假设我有一个L长度为R的列表N,其中N相当大(例如,10000,1.00000,1百万或更多).假设我的列表中包含每个元素的名称.`

我想知道检索一个命名条目需要多长时间,即要做

 L[[ "any_random_name" ]]  

这是时间O(N),即与列表的长度成比例,还是它O(1),即,与列表名称无关的常量.或者它可能O( log N )？

Answer 1

有趣的是，答案是和 O(1)。O(n)时间与其说取决于列表的长度，不如说取决于获得所需的命名元素之前的列表的长度。

让我们定义一些不同长度的列表：

library(microbenchmark)

makelist <- function(n){
   L <- as.list(runif(n))   
   names(L) <- paste0("Element", 1:n)
   return(L)
}

L100 <- makelist(100)
L1000 <- makelist(1000)
LMillion <- makelist(10^6)
L10Million <- makelist(10^7)

Element100如果我们尝试提取其中每个元素中名为 our 的元素（第 100 个元素），则需要的时间长度基本相同：

microbenchmark(
   L10Million[["Element100"]],
   LMillion[["Element100"]],
   L1000[["Element100"]],
   L100[["Element100"]]
)

Unit: nanoseconds
                       expr min  lq    mean median   uq   max neval cld
 L10Million[["Element100"]] 791 791  996.59    792 1186  2766   100   a
   LMillion[["Element100"]] 791 791 1000.56    989 1186  1976   100   a
      L1000[["Element100"]] 791 791 1474.64    792 1186 28050   100   a
       L100[["Element100"]] 791 791 1352.21    792 1186 17779   100   a

但如果我们尝试获取最后一个元素，则所需时间为 O(n)

microbenchmark(
   L10Million[["Element10000000"]],
   LMillion[["Element1000000"]],
   L1000[["Element1000"]],
   L100[["Element100"]]
)

Unit: nanoseconds
                            expr       min        lq         mean    median        uq       max neval cld
 L10Million[["Element10000000"]] 154965791 165074635 172399030.13 169602043 175170244 235525230   100   c
    LMillion[["Element1000000"]]  15362773  16540057  17379942.70  16967712  17734922  22361689   100  b 
          L1000[["Element1000"]]      9482     10668     17770.94     16594     20544     67557   100 a  
            L100[["Element100"]]       791      1186      3995.15      3556      6322     24100   100 a 


library(ggplot2)
library(dplyr)
res <- data.frame(x = c(100, 1000, 10^6, 10^7), 
           y = c(3556, 16594, 16967715, 169602041)) 

ggplot(res, aes(x = x, y = y ))+
   geom_smooth(method = "lm") +
   geom_point(, size = 3) +
   scale_x_log10() +
   scale_y_log10()