दिलचस्प, उत्तर दोनोंO(1) और O(n) दोनों के रूप में सामने आता है। समय सूची की लंबाई पर इतना निर्भर नहीं करता है, क्योंकि नामित तत्व से पहले सूची की लंबाई प्राप्त की जाती है।
के अलग-अलग लंबाई के कुछ सूचियां निर्धारित करते हैं: हम तत्व Element100 हमारे इनमें से प्रत्येक के नाम पर रखा गया निकालने के लिए प्रयास करते हैं तो
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)
- 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()
है
स्रोत
2016-12-28 20:31:04
यह दृढ़ता से सुझाव देता है कि यह 'ओ (1) 'नहीं है: https://www.r-bloggers.com/hash-table-performance-in-r-part-i/ इसके अलावा, देखें यह प्रश्न: http://stackoverflow.com/q/3470447/4996248 (पहला लिंक दिखाता है कि यह 'ओ (एन) 'है। वे * सभी * कुंजी को देखने के परिणाम का समय दे रहे हैं, जो वर्गबद्ध है हालांकि वे गलती से कहते हैं कि यह घातीय है)। –
एक एकल मूल्य लुकअप के लिए (जैसे '"any_random_name" '), [' do_subset2_dflt'] का प्रासंगिक हिस्सा (https://github.com/wch/r-source/blob/d8f952565bb9c48bd524c368f3e4ac0d3de096b0/src/main/subset.C# एल 1018-एल 1030) ['get1index'] (https://github.com/wch/r-source/blob/af7f52f70101960861e5d995d3a4bec010bc89e6/src/main/subscript.c#L224-L233) पर कॉल होना चाहिए, जो प्रतीत होता है रैखिक हो। – nrussell
ए [त्वरित बेंचमार्क] (https://gist.github.com/nathan-russell/d09e220899115d85b10c0959188a287b) इसकी पुष्टि करने लगता है। – nrussell