Какова временная сложность поиска имени в списке R?

Question

Я попытался отчаянно найти ответ через Google и не смог. Я собираюсь сделать сам тест, но подумал, что, может быть, кто-то здесь знает ответ или, по крайней мере, ссылку, где это документировано.

Чтобы расширить на мой вопрос: предположим, у меня есть список L в R длины N, где N является довольно большим (скажем, 10000, 100000, 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 нашего каждого из них - 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 (п)

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()