Độ phức tạp của việc tra cứu tên trong danh sách R là bao nhiêu?

Question

Tôi đã cố gắng hết sức để tìm câu trả lời qua Google và không thành công. Tôi chuẩn bị làm điểm chuẩn cho bản thân nhưng nghĩ rằng có lẽ ai đó ở đây biết câu trả lời hoặc ít nhất là một tài liệu tham khảo trong đó tài liệu này được ghi lại.

Để mở rộng câu hỏi của tôi: giả sử tôi có danh sách L ở R dài N, trong đó N là khá lớn (ví dụ: 10000, 100.000, 1 triệu trở lên). Giả sử danh sách của tôi có tên cho mọi phần tử. '

Tôi tự hỏi bao lâu để lấy một mục tên là duy nhất, tức là, để làm

L[[ "any_random_name" ]] 

là thời gian này O(N), tức là tỷ lệ thuận với độ dài của danh sách, hoặc là nó O(1), mà là, liên tục độc lập với tên của danh sách. hoặc có thể là O(log N)?

Answer 1

Thú vị, câu trả lời hóa ra là cả haiO(1) và O(n). Thời gian phụ thuộc không quá nhiều vào độ dài của danh sách, vì độ dài của danh sách trước phần tử được đặt tên bạn muốn thu được.

Hãy xác định một số danh sách có độ dài khác nhau:

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) 

Nếu chúng ta cố gắng trích xuất các yếu tố được đặt tên Element100 của chúng tôi của mỗi - yếu tố thứ 100 - phải mất cơ bản cùng độ dài của thời gian:

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 

Nhưng nếu chúng tôi cố gắng để có được những yếu tố cuối cùng, thời gian cần thiết là 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()