कोई भी सामान्य कार्यान्वयन में ECMAScript5 की Object.keys() की समय-जटिलता को जानता है? n कुंजी के लिए O(n) है? हैश तालिका के आकार के अनुपात में समय है, एक हैश कार्यान्वयन मानते हैं?ऑब्जेक्ट.की() जटिलता?
मैं या तो भाषा कार्यान्वयनकर्ताओं या कुछ वास्तविक विश्व बेंचमार्किंग द्वारा गारंटी की तलाश में हूं।
यह वी 8 में O(n) प्रतीत होता है (क्रोम, Node.js) कम से कम:
> var hash = {}
> , c = 0;
>
> var s = +new Date();Object.keys(hash);console.log(+new Date() - s);
0
> for(var i=0; i<100000; i++, c++){ hash[c] = 1; }
> var s = +new Date();Object.keys(hash);console.log(+new Date() - s);
26
> for(var i=0; i<100000; i++, c++){ hash[c] = 1; }
> var s = +new Date();Object.keys(hash);console.log(+new Date() - s);
49
> for(var i=0; i<100000; i++, c++){ hash[c] = 1; }
> var s = +new Date();Object.keys(hash);console.log(+new Date() - s);
75
> for(var i=0; i<100000; i++, c++){ hash[c] = 1; }
> var s = +new Date();Object.keys(hash);console.log(+new Date() - s);
102
उन परिणामों को घने हैश मानचित्र के लिए समझ में आता है। क्या कुंजी के रूप में प्रदर्शन खराब हो जाता है और अधिक स्पैस मिलता है? – hurrymaplelad
@hurrymaplelad - क्या? सभी जेएस हैश कुंजी तार हैं। यह कोड प्रभावी ढंग से '{' 1 ': 1,' 2 ': 1,' 3 ': 1, ...} '_sparse_ बनाम _dense_ कुंजी उत्पन्न करता है हैश कार्यान्वयन, केवल सरणी के लिए समझ में नहीं आता है। और यह वास्तव में एक इंजन के लिए एक हैश को एक सरणी के रूप में लागू करने के लिए कोई समझ नहीं आता है क्योंकि संख्यात्मक सूचकांक आमतौर पर दुर्लभ होते हैं। यद्यपि यदि आप किसी कारण से इसका परीक्षण करना चाहते हैं, तो बस 'C++' को 'c + = Math.random() 'में बदलें जो आपको पूरी तरह से गैर-सहयोगी कुंजी देगा। –
@cwolves: एक 'ऐरे' ऑब्जेक्ट केवल एक ऑब्जेक्ट है जिसका गुण पूरे नंबर होने की उम्मीद है। वे बहुत दुर्लभ नहीं हैं, और निश्चित रूप से जेएस कार्यान्वयन हैं जो 'ऐरे' उदाहरणों को वापस करने के लिए सरणी का उपयोग करते हैं। – Gabe
कितने कुंजी हो रहा की उम्मीद करते हैं, जैसे कि गणना उन मामलों की समय जटिलता? – Gabe
मुझे नहीं लगता कि यह 'ओ (एन) ' –
@ पाब्लोफर्नान्डेज़ से कम हो सकता है, ओ (एन) – Joe