हैश के रूप में उपयोग किए जाने पर जावास्क्रिप्ट की सरणी के लिए बड़ा ओ क्या है?

Question

जब एक हैश के रूप में इस्तेमाल जावास्क्रिप्ट का उपयोग करने के लिए सरणी बड़ा हे क्या है?

उदाहरण के लिए

,

var x= []; 
for(var i=0; i<100000; i++){ 
    x[i.toString()+'a'] = 123; // using string to illustrate x[alpha] 
} 
alert(x['9999a']); // linear search? 

एक आशा कर सकते हैं जे एस इंजन एक रेखीय खोज आंतरिक हे (एन) का उपयोग नहीं होगा, लेकिन यकीन है कि के लिए है?

Answer 1

पहला और सबसे महत्वपूर्ण Arrays वास्तव में हैंश हैं। हमेशा।

var x = []; 
x[5] = 10; 
alert(x[5] === x["5"]); // true 

वस्तुओं हैश कर रहे हैं और सरणी सिर्फ विशेष वस्तुओं हैं: यही कारण है कि x[5] === x["5"] है। यदि आप ऑब्जेक्ट्स के लिए सामान्य हैश का उपयोग करना चाहते हैं। जावास्क्रिप्ट में "एसोसिएटिव सरणी" ऑब्जेक्ट्स हैं। Arrays संख्यात्मक रूप से अनुक्रमित डेटा के लिए हैं। Arrays एक length संपत्ति और push, pop, sort, आदि जो हैश पर इस्तेमाल किया जा करने के लिए कोई मतलब नहीं है की तरह सरणी की तरह तरीकों की है।

ऑब्जेक्ट्स में खोज के लिए बड़े ओ के लिए: यह कार्यान्वयन निर्भर है।

शायद 2 सबसे अच्छी चीजों में आप के लिए कर सकते हैं:

1. चेक कुछ ब्राउज़र कार्यान्वयन

2. के स्रोत कोड बड़ा n के लिए कुछ बेंचमार्क करो और अपने निष्कर्ष

---

के संबंधित भाग:

4.3.3 वस्तु

एक वस्तु गुण का एक संग्रह है और एक भी प्रोटोटाइप वस्तु है।

8.6.2 वस्तु आंतरिक गुण और तरीके

सरणी वस्तुओं एक से थोड़ा [[DefineOwnProperty]] आंतरिक विधि के विभिन्न कार्यान्वयन है। सरणी वस्तुओं संपत्ति के नाम की एक निश्चित वर्ग के लिए विशेष उपचार दे।

Answer 2

जावास्क्रिप्ट में ऑब्जेक्ट गुणों और सरणी तत्वों तक पहुंचने के लिए वाक्य रचनात्मक रूप से constant time: O (1) में किया जाना माना जाता है। ईसीएमएस्क्रिप्ट विनिर्देश में प्रदर्शन विशेषताओं की गारंटी नहीं है, लेकिन सभी आधुनिक जावास्क्रिप्ट इंजन निरंतर समय में ऑब्जेक्ट गुणों को पुनर्प्राप्त करते हैं।- 2.93GHz इंटेल कोर 2 डुओ

Firebug, फ़ायरफ़ॉक्स 3.6.10 (मैक ओएस एक्स 10.6.4 में

var largeObject = {}; 
var smallObject = {}; 

var x, i; 

for (i = 0; i < 1000000; i++) { 
    largeObject['a' + i] = i; 
} 

for (i = 0; i < 1000; i++) { 
    smallObject['b' + i] = i; 
} 

console.time('10k Accesses from largeObject'); 
for (i = 0; i < 10000; i++) x = largeObject['a' + (i % 1000000)]; 
console.timeEnd('10k Accesses from largeObject'); 

console.time('10k Accesses from smallObject'); 
for (i = 0; i < 10000; i++) x = largeObject['a' + (i % 1000)]; 
console.timeEnd('10k Accesses from smallObject'); 

परिणाम:

यहाँ एक सरल तरीका दिखाते हुए अभिगम समय बढ़ने जब कंटेनर x1000 गुना बड़ी है उदाहरण दिया गया है): क्रोम देव उपकरण में

10k Accesses from largeObject: 22ms 
10k Accesses from smallObject: 19ms 

परिणाम 6.0.472:

10k Accesses from largeObject: 15ms 
10k Accesses from smallObject: 15ms 

इंटरनेट Expl विंडोज पर Firebug Lite के साथ 8.0.7600 orer 7

10k Accesses from largeObject: 250ms 
10k Accesses from smallObject: 219ms