रूबी सरणी आंतरिक

Question

रूबी सरणी आंतरिक रूप से कार्यान्वित कैसे होते हैं (मुख्य रूप से क्रुबी में, लेकिन किसी अन्य जानकारी का स्वागत है)?

क्या वे सी ++ वेक्टर की तरह बढ़ते सरणी हैं या वे सूची आधारित हैं? शिफ्ट/unshift की जटिलता और सूचकांक द्वारा एक तत्व का उपयोग क्या है?

Answer 1

वे उगने वाले सरणी हैं जो "अंत में बढ़ते हैं"।

shiftO(1) है, unshiftO(n) है और सूचकांक द्वारा तक पहुँचने O(1) है। मेरे सबसे अच्छे ज्ञान के लिए यह सभी रूबी कार्यान्वयन के लिए सच है, लेकिन यह निश्चित रूप से एमआरआई में करता है।

Answer 2

unshift मेरी ruby1.9 में ओ (एन^2) है।

$ /usr/bin/time ruby -e 'n=100000;l=[];(1..n).each{|i| l.push(i);}' 
     0.03 real   0.02 user   0.00 sys 
$ /usr/bin/time ruby -e 'n=100000;l=[];(1..n).each{|i| l.unshift(i);}' 
     3.15 real   3.11 user   0.01 sys 
$ /usr/bin/time ruby -e 'n=200000;l=[];(1..n).each{|i| l.unshift(i);}' 
     12.96 real  12.85 user   0.03 sys 
$ ruby -v 
ruby 1.9.3p194 (2012-04-20 revision 35410) [x86_64-darwin11.3.0]