प्रमुख जावास्क्रिप्ट इंजन में जावास्क्रिप्ट सहयोगी सरणी (गतिशील वस्तु गुण) में पुनर्प्राप्ति/सम्मिलन की जटिलता क्या है?

Question

निम्नलिखित कोड उदाहरण लें:

var myObject = {}; 
var i = 100; 

while (i--) { 
    myObject["foo"+i] = new Foo(i); 
} 

console.log(myObject["foo42"].bar()); 

मैं कुछ प्रश्न हैं।

प्रमुख इंजन (आईई, मोज़िला, क्रोम, सफारी) किस प्रकार की डेटा संरचना कुंजी-मूल्य जोड़े संग्रहीत करने के लिए उपयोग करते हैं? मुझे उम्मीद है कि यह किसी तरह का बाइनरी सर्च पेड़ है, लेकिन मुझे लगता है कि वे लिंक्ड सूचियों का उपयोग कर सकते हैं (तथ्य के कारण पुनरावृत्ति आदेश प्रविष्टि में किया जाता है)।

यदि वे एक खोज पेड़ का उपयोग करते हैं, तो क्या यह स्वयं संतुलन है? चूंकि एक पारंपरिक खोज पेड़ वाला उपरोक्त कोड एक असंतुलित वृक्ष पैदा करेगा, जिससे एक संतुलित पेड़ के लिए ओ (लॉग एन) की बजाय खोज के लिए ओ (एन) का सबसे खराब केस परिदृश्य होगा।

मैं केवल यह पूछ रहा हूं क्योंकि मैं एक पुस्तकालय लिखूंगा जिसके लिए डेटा संरचना से चाबियों की कुशल पुनर्प्राप्ति की आवश्यकता होगी, और जब मैं अपना खुद का या मौजूदा लाल-काला पेड़ लागू कर सकता हूं तो मैं मूल वस्तु गुणों का उपयोग करूंगा अगर वे काफी कुशल हैं।

Answer 1

प्रश्न दो कारणों से उत्तर देना मुश्किल है। सबसे पहले, आधुनिक ब्राउज़र सभी निष्पादित करते समय कोड को भारी और गतिशील रूप से अनुकूलित करते हैं, इसलिए गुणों तक पहुंचने के लिए चुने गए एल्गोरिदम एक ही कोड के लिए अलग हो सकते हैं। दूसरा, प्रत्येक इंजन अलग-अलग एल्गोरिदम और हेरिस्टिक का उपयोग करता है यह निर्धारित करने के लिए कि कौन सी एक्सेस एल्गोरिदम का उपयोग करना है। तीसरा, ईसीएमए विनिर्देश बताता है कि परिणाम क्या होना चाहिए, न कि परिणाम कैसे प्राप्त किया जाता है, इसलिए इस क्षेत्र में इंजनों को नवाचार करने की बहुत सारी स्वतंत्रता है।

यह कहा गया है कि, आपके उदाहरण के अनुसार, जिन सभी इंजनों से मैं परिचित हूं, वे myobject से foo42 से जुड़े मान को पुनर्प्राप्त करने के लिए हैश तालिका के कुछ रूप का उपयोग करेंगे। यदि आप किसी ऑब्जेक्ट का उपयोग किसी एसोसिएटिव सरणी जैसे जावास्क्रिप्ट इंजन का उपयोग करते हैं तो हैश टेबल का पक्ष लेना होगा। कोई भी नहीं जिसे मैं स्ट्रिंग गुणों के लिए एक पेड़ का उपयोग करने के बारे में जानता हूं। हैश टेबल सबसे खराब मामला ओ (एन) है, सबसे अच्छा मामला ओ (1) और ओ (एन) से ओ (एन) के करीब होना चाहिए यदि कुंजी जनरेटर कोई अच्छा है। प्रत्येक इंजन में एक पैटर्न होगा जिसका उपयोग आप ओ (एन) करने के लिए कर सकते हैं लेकिन यह प्रत्येक इंजन के लिए अलग होगा। एक संतुलित पेड़ सबसे बुरी स्थिति ओ (लॉग एन) की गारंटी देगा, लेकिन इसे संतुलित रखने के दौरान संतुलित पेड़ को संशोधित करना ओ (लॉग एन) नहीं है और हैश टेबल स्ट्रिंग कुंजियों के लिए ओ (लॉग एन) से अधिक बार बेहतर होते हैं और ओ (1) अद्यतन करने के लिए (एक बार जब आप निर्धारित करते हैं कि आपको वही बड़ा-ओ पढ़ा जाता है) यदि तालिका में जगह है (समय-समय पर ओ (एन) तालिका को पुनर्निर्माण करने के लिए, लेकिन टेबल आमतौर पर अंतरिक्ष में दोगुना होता है जिसका अर्थ है कि आप केवल भुगतान करेंगे ओ (एन) तालिका के जीवन के लिए 7 या 8 बार)।

संख्यात्मक गुण विशेष हैं, हालांकि। यदि आप पूर्णांक संख्यात्मक गुणों का उपयोग करके किसी ऑब्जेक्ट तक पहुंचते हैं जिसमें श्रेणी में कम या कोई अंतराल नहीं है, यानी, ऑब्जेक्ट का उपयोग करें जैसे कि यह एक सरणी है, मानों को O (1) एक्सेस के साथ स्मृति के रैखिक ब्लॉक में संग्रहीत किया जाएगा। भले ही आपकी पहुंच अंतराल हो, फिर भी इंजन शायद एक स्पैर सरणी पहुंच में स्थानांतरित हो जाएंगे, जो शायद सबसे खराब होगा, ओ (लॉग एन)।

पहचानकर्ता द्वारा संपत्ति तक पहुंच भी विशेष है। आप की तरह,

myObject.foo42 

संपत्ति पहुँच सकते हैं और इस कोड को अक्सर निष्पादित हैं (जो है, इस मामले की गति) और एक या समान वस्तु इस एक या दो मशीन निर्देशों में अनुकूलित किया जा सकता है के साथ। ऑब्जेक्ट्स समान बनाता है जो प्रत्येक इंजन के लिए भी अलग होता है लेकिन यदि वे एक ही शाब्दिक या फ़ंक्शन द्वारा निर्मित होते हैं तो उन्हें समान रूप से माना जाने की अधिक संभावना होती है।

कोई भी इंजन जो जावास्क्रिप्ट बेंचमार्क पर अच्छी तरह से करता है, प्रत्येक ऑब्जेक्ट के लिए समान एल्गोरिदम का उपयोग नहीं करेगा।उन्हें सभी को गतिशील रूप से निर्धारित करना होगा कि ऑब्जेक्ट का उपयोग कैसे किया जा रहा है और तदनुसार एक्सेस एल्गोरिदम समायोजित करने का प्रयास करें।