गतिशील सरणी

From Vigyanwiki
ज्यामितीय विस्तार का उपयोग करके गतिशील सरणी के अंत में कई मान डाले गए हैं। ग्रे कोशिकाएं विस्तार के लिए आरक्षित स्थान का संकेत देते हैं। अधिकांश सम्मिलन तेज़ (निरंतर समय) होते हैं, जबकि कुछ पुनः आवंटन (Θ(n) समय, कछुओं के साथ अंकित) की आवश्यकता के कारण धीमे होते हैं। अंतिम सरणी का तार्किक आकार और क्षमता दिखाई जाती है।

गणना विज्ञान (कंप्यूटर विज्ञान) में, एक गतिशील सरणी, बढ़ने योग्य सरणी, आकार बदलने योग्य सरणी, गतिशील तालिका, उत्परिवर्तनीय सरणी, या सरणी सूची एक यादृच्छिक अभिगम, चर-आकार आँकड़े (डेटा) संरचना की सूची है जो अवयव को जोड़ने या निकालने की अनुमति देती है। यह कई आधुनिक मुख्यधारा की प्रोग्रामिंग भाषाओं में मानक पुस्तकालयों के साथ आपूर्ति की जाती है। गतिविज्ञान सरणियाँ स्थैतिक सरणियों की एक सीमा को पार करती हैं, जिनकी एक निश्चित क्षमता होती है जिसे आवंटन के समय निर्दिष्ट करने की आवश्यकता होती है।

एक गतिशील सरणी गतिशील रूप से आवंटित सरणी या चर-लंबाई सरणी के समान नहीं है, इनमें से कोई भी एक सरणी है जिसका आकार सरणी आवंटित होने पर तय किया गया है, हालांकि एक गतिशील सरणी बैकएंड के रूप में इस तरह के निश्चित आकार की सरणी का उपयोग कर सकती है। [1]

परिबद्ध-आकार गतिशील सरणियाँ और क्षमता

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

एक निश्चित आकार की सरणी उन अनुप्रयोगों में पर्याप्त होगी जहां अधिकतम तार्किक आकार निश्चित है (उदाहरण के लिए विनिर्देश द्वारा), या सरणी आवंटित होने से पहले गणना की जा सकती है। एक गतिशील सरणी को प्राथमिकता दी जा सकती है यदि:

  • अधिकतम तार्किक आकार अज्ञात है, या सरणी आवंटित होने से पहले गणना करना मुश्किल है
  • यह माना जाता है कि विनिर्देश द्वारा दिए गए अधिकतम तार्किक आकार में परिवर्तन होने की संभावना है
  • एक गतिशील सरणी का आकार बदलने की परिशोधित लागत प्रदर्शन या अनुक्रियाशीलता को महत्वपूर्ण रूप से प्रभावित नहीं करती है

ज्यामितीय विस्तार और परिशोधित लागत

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

function insertEnd(dynarray a, element e)
    if (a.size == a.capacity)
        // resize a to twice its current capacity:
        a.capacity ← a.capacity * 2 
        // (copy the contents to the new memory location here)
    a[a.size] ← e
    a.size ← a.size + 1

क्योंकि n तत्व डाले जाते हैं, क्षमता एक ज्यामितीय प्रगति बनाती है। किसी भी स्थिर अनुपात द्वारा सरणी का विस्तार करना सुनिश्चित करता है कि n तत्वों को सम्मिलित करने में समग्र रूप से O(n) समय लगता है, जिसका अर्थ है कि प्रत्येक सम्मिलन में परिशोधित निरंतर समय लगता है। यदि इसका आकार एक निश्चित सीमा से कम हो जाता है, जैसे क्षमता का 30%, तो कई गतिशील सरणियाँ कुछ अंतर्निहित संग्रहण को भी हटा देती हैं। हिस्टैरिसीस प्रदान करने के लिए (बार-बार बढ़ने और सिकुड़ने से बचने के लिए एक स्थिर बैंड प्रदान करें) और परिशोधित निरंतर लागत के साथ सम्मिलन और निष्कासन के मिश्रित अनुक्रमों का समर्थन करने के लिए यह सीमा 1/a से दृढता से छोटी होनी चाहिए।

परिशोधित विश्लेषण पढ़ाते समय गतिशील सरणियाँ एक सामान्य उदाहरण हैं।[3][4]







विकास कारक

गतिशील सरणी के लिए विकास कारक अंतराल-समय उद्योग-बंद और मेमोरी संभाजक में प्रयुक्त होने वाले एल्गोरिदम सहित कई कारकों पर निर्भर करता है। वृद्धि कारक a के लिए, प्रति सम्मिलन संचालन का औसत समय लगभग a/(a−1),है, जबकि व्यर्थ कोशिकाओं की संख्या (a−1)n से ऊपर है[citation needed] यदि मेमोरी आवंटनकर्ता प्रथम अनुरूप एल्गोरिदम का उपयोग करता है, तो वृद्धि कारक मान जैसे कि a = 2 गतिशील सरणी प्रसारण को मेमोरी से बाहर चलाने का कारण बन सकता है, भले ही मेमोरी की एक महत्वपूर्ण मात्रा अभी भी उपलब्ध हो।[5] सुनहरा अनुपात के साथ-साथ मूल्य 1.5 के प्रस्तावों सहित आदर्श विकास कारक मूल्यों पर विभिन्न चर्चाएँ हुई हैं।[6] यद्यपि, कई पाठ्य पुस्तकें सादापन और विश्लेषण उद्देश्यों के लिए a = 2 का उपयोग करती हैं।[3][4]

नीचे कई प्रचलित कार्यान्वयनों द्वारा उपयोग किए जाने वाले विकास कारक हैं:

कार्यान्वयन विकास कारक (a)
जावा ऐरेलिस्ट[1] 1.5 (3/2)
पायथन पाइलिस्टउद्देश्य[7] ~1.125 (n + (n >> 3))
माइक्रोसॉफ्ट विज़ुअल C++ 2013[8] 1.5 (3/2)
G++ 5.2.0[5] 2
क्लैंग 3.6[5] 2
फेसबुक फौली / एफबी वेक्टर[9] 1.5 (3/2)
रस्ट वेक[10] 2
Go स्लाइसेस[11] 1.25 और 2 के बीच
निम अनुक्रम[12] 2

प्रदर्शन

Comparison of list data structures
Peek
(index) 		Mutate (insert or delete) at … Excess space,
average
Beginning End Middle
Linked list Θ(n) Θ(1) Θ(1), known end element;
Θ(n), unknown end element 		Peek time +
Θ(1)[13][14] 		Θ(n)
Array Θ(1) — — — 0
Dynamic array Θ(1) Θ(n) Θ(1) amortized Θ(n) Θ(n)[15]
Balanced tree Θ(log n) Θ(log n) Θ(log n) Θ(log n) Θ(n)
Random-access list Θ(log n)[16] Θ(1) —[16] —[16] Θ(n)
Hashed array tree Θ(1) Θ(n) Θ(1) amortized Θ(n) Θ(√n)

तत्वों को जोड़ने और हटाने के लिए नए कार्यों को जोड़ने के साथ गतिशील सरणी में एक सरणी के समान प्रदर्शन होता है:

  • किसी विशेष अनुक्रमणिका (निरंतर समय) पर मूल्य प्राप्त करना या समुच्चयन करना
  • क्रम में तत्वों पर ध्यान देना (रैखिक समय, अच्छा कैश प्रदर्शन)
  • सरणी के बीच में एक तत्व सम्मिलित करना या हटाना (रैखिक समय)
  • सरणी के अंत में एक तत्व सम्मिलित करना या हटाना (निरंतर परिशोधन समय)

संदर्भ और डेटा कैश उपयोग, कॉम्पैक्टनेस (निम्न मेमोरी उपयोग), और यादृच्छिक पहुंच सहित सरणियों के कई लाभों से गतिशील सरणियाँ लाभान्वित होती हैं। आकार और क्षमता के बारे में जानकारी संग्रहीत करने के लिए उनके पास सामान्यतया पर केवल एक छोटा निश्चित अतिरिक्त उपरिव्यय होता है। यह गतिशील सरणियों को कैश-अनुकूल डेटा संरचना के निर्माण के लिए एक आकर्षक उपकरण बनाता है। तथापि, पायथन या जावा जैसी भाषाओं में जो संदर्भ शब्दार्थ को प्रवर्तित करते हैं, गतिशील सरणी साधारणतयः पर वास्तविक तथ्य को संग्रहीत नहीं करती, बल्कि यह मेमोरी के अन्य क्षेत्रों में रहने वाले डेटा के संदर्भ (कंप्यूटर विज्ञान) को संग्रहीत करेगी। इस मामले में, सरणी में वस्तुओं तक क्रमिक रूप से पहुंचने में वास्तव में मेमोरी के कई गैर-सन्निहित क्षेत्रों तक पहुंच सम्मिलित होगी, इसलिए इस डेटा संरचना के कैश-मित्रता के कई लाभ लुप्त हो गए हैं।

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

एक संतुलित वृक्ष गतिशील सरणियों और श्रृंखलित सूचियों दोनों के सभी संचालन को यथोचित कुशलता से प्रदान करते हुए एक सूची को संग्रहीत कर सकता है, लेकिन अंत में सम्मिलन और सूची में पुनरावृत्ति दोनों एक गतिशील सरणी की तुलना में धीमी होती है, सिद्धांत और व्यवहार में, गैर के कारण- असन्निकट संचयन और ट्री ट्रैवर्सल/हस्तोपचार उपरि के कारण।

भिन्न

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

गुडरिक[17] एक गतिशील सरणियों एल्गोरिथम ने प्रस्तुत किया जिसे स्तरित सदिश कहा जाता है जो सरणियों में कहीं से भी सम्मिलन और विलोपन के लिए O(n1/k) प्रदर्शन प्रदान करता है, और O(k) प्राप्त और उत्पन्न करता है, जहां k ≥ 2 एक स्थिर मापदण्ड है।

हैशेड सरणी वृक्ष (HAT) 1996 में सितारस्की द्वारा प्रकाशित एक गतिशील सरणियों एल्गोरिथम है।[18] हैशेड सरणी ट्री स्टोरेज स्पेस की n1/2 मात्रा को बर्बाद करता है, जहाँ n सरणी में तत्वों की संख्या है। हैशेड सरणी ट्री के अंत में वस्तुओं की एक श्रृंखला को जोड़ते समय एल्गोरिथ्म में O(1) परिशोधित प्रदर्शन होता है।

1999 के एक पेपर में, ब्रोडनिक एट अल। एक स्तरीय गतिशील सरणी डेटा संरचना, जो समय पर किसी भी बिंदु पर n तत्वों के लिए केवल n1/2 स्थान बर्बाद करता है, और वे यह दिखाते हुए एक निचली सीमा साबित करते हैं कि किसी भी गतिशील सरणी को इतना स्थान बर्बाद करना होगा यदि संचालन निरंतर समय को परिशोधित करना है। इसके अतिरिक्त, वे एक संस्करण प्रस्तुत करते हैं जहां बफर के बढ़ने और सिकुड़ने से न केवल परिशोधन होता है, बल्कि सबसे खराब समय भी होता है।

बागवेल (2002)[19] ने वी लिस्ट एल्गोरिथम प्रस्तुत किया, जिसे एक गतिशील सरणी को अनुबंध करने के लिए अनुकूलित किया जा सकता है।

नाओव आकार बदलने योग्य सरणी - जिसे आकार बदलने योग्य सरणी का सबसे खराब कार्यान्वयन भी कहा जाता है - सरणी के आवंटित आकार को इसमें सम्मिलित सभी डेटा के लिए पर्याप्त रूप से बड़ा रखें, संभवतः सरणी में जोड़े गए प्रत्येक विषय के लिए रीयलोक को कॉल करके C में एक आकार बदलने योग्य सरणी को लागू करने का सबसे सरल तरीका अनुभवहीन आकार बदलने योग्य सरणी है। वे किसी भी मेमोरी को व्यर्थ नहीं करते हैं, लेकिन सरणी के अंत में सम्मिलित होने में हमेशा Θ(n) समय लगता है।[18][20][21][22][23] रैखिक रूप से बढ़ने वाली सरणियाँ पूर्व-आवंटन (अपशिष्ट) Θ (1) स्थान हर बार जब वे सरणी को फिर से आकार देती हैं, तो उन्हें नैवे आकार देने योग्य सरणियों की तुलना में कई गुना तेज बना देती हैं - सरणी के अंत में संलग्न होने में अभी भी Θ (n) समय लगता है लेकिन बहुत छोटे स्थिरांक के साथ। सरल आकार बदलने योग्य सरणियाँ और रैखिक रूप से बढ़ने वाली सरणियाँ तब उपयोगी हो सकती हैं जब अंतरिक्ष-बाधित अनुप्रयोग को बहुत से सूक्ष्म आकार बदलने योग्य सरणियों की आवश्यकता होती है; वे सामान्यतया पर एक शैक्षिक उदाहरण के रूप में भी उपयोग किए जाते हैं जो तेजी से बढ़ते गतिशील सरणियों के लिए अग्रणी होते हैं।[24]

भाषा समर्थन

C ++एसटीडी :: वेक्टर और रस्ट (प्रोग्रामिंग भाषा) एसटीडी :: वेक्टर:: वेक्टर गतिशील सरणियों के कार्यान्वयन हैं, जैसा कि हैं [25] जावा (प्रोग्रामिंग भाषा) API और NET फ्रेमवर्क के साथ प्रदान की जाने वाली सारणी सूची कक्षाएं हैं।[26]

NET फ्रेमवर्क के संस्करण 2.0 के साथ आपूर्ति की गई सामान्य सूची <> वर्ग को गतिशील सरणियों के साथ भी लागू किया गया है। स्मॉलटॉक का आदेशित संग्रह गतिशील आरम्भ और अंत-सूचकांक के साथ एक गतिशील सरणिया है, जिससे पहले घटक को भी O(1) हटा दिया जाता है।

पायथन सूची डेटा प्रकार कार्यान्वयन एक गतिशील सरणी है जिसका विकास स्वरूप :0, 4, 8, 16, 24, 32, 40, 52, 64, 76, ...है[27]

डेल्फी (प्रोग्रामिंग भाषा) और डी (प्रोग्रामिंग भाषा) भाषा के मूल में गतिशील सरणियों को प्रवर्तित करते हैं।

एडा (प्रोग्रामिंग लैंग्वेज) एडा.कंटेनर.वैक्टरसामान्य संवेष्टन किसी दिए गए उपप्रकार के लिए गतिशील सरणी कार्यान्वयन प्रदान करता है।

पर्ल और रूबी_(प्रोग्रामिंग_लैंग्वेज) जैसी कई स्क्रिप्टिंग भाषाएं में निर्मित आदिम डेटा प्रकार के रूप में गतिशील सरणियाँ प्रदान करती हैं।

कई क्रॉस-प्लेटफ़ॉर्म फ्रेमवर्क C (प्रोग्रामिंग भाषा) के लिए गतिशील सरणी कार्यान्वयन प्रदान करते हैं, जिनमें सम्मिलित हैं सीएफ तथा सीएफ उत्परिवर्तनीय सरणी बीजकोष संस्थान में, और जी सरणी तथा जीपी टीआर सरणीग्लिब.में।

सामान्य लिस्प अंतर्निर्मित सरणी समायोज्य के रूप में और भरण-सूचक द्वारा निवेशन के स्थान को समनुरूप करने की अनुमति देकर आकार बदलने योग्य वैक्टर के लिए एक अल्पविकसित समर्थन प्रदान करता है।

संदर्भ

  1. ↑ 1.0 1.1 उदाहरण के लिए देखें, java.util.ArrayList का स्रोत कोड ओपनजेडीके 6 से क्लास।
  2. ↑ Lambert, Kenneth Alfred (2009), "Physical size and logical size", Fundamentals of Python: From First Programs Through Data Structures, Cengage Learning, p. 510, ISBN 978-1423902188
  3. ↑ 3.0 3.1 Goodrich, Michael T.; Tamassia, Roberto (2002), "1.5.2 Analyzing an Extendable Array Implementation", Algorithm Design: Foundations, Analysis and Internet Examples, Wiley, pp. 39–41.
  4. ↑ 4.0 4.1 Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001) [1990]. "17.4 Dynamic tables". Introduction to Algorithms (2nd ed.). MIT Press and McGraw-Hill. pp. 416–424. ISBN 0-262-03293-7.
  5. ↑ 5.0 5.1 5.2 "सी++ एसटीएल वेक्टर: परिभाषा, विकास कारक, सदस्य कार्य". Archived from the original on 2015-08-06. Retrieved 2015-08-05.
  6. ↑ "1.5 का वेक्टर विकास कारक". comp.lang.c++.moderated. Google Groups. Archived from the original on 2011-01-22. Retrieved 2015-08-05.
  7. ↑ List object implementation from github.com/python/cpython/, retrieved 2020-03-23.
  8. ↑ Brais, Hadi. "Dissecting the C++ STL Vector: Part 3 - Capacity & Size". Micromysteries. Retrieved 2015-08-05.
  9. ↑ "facebook/folly". GitHub. Retrieved 2015-08-05.
  10. ↑ "rust-lang/rust". GitHub (in English). Retrieved 2020-06-09.
  11. ↑ "golang/go". GitHub. Retrieved 2021-09-14.
  12. ↑ "The Nim memory model". zevv.nl. Retrieved 2022-05-24.
  13. ↑ Day 1 Keynote - Bjarne Stroustrup: C++11 Style at GoingNative 2012 on channel9.msdn.com from minute 45 or foil 44
  14. ↑ Number crunching: Why you should never, ever, EVER use linked-list in your code again at kjellkod.wordpress.com
  15. ↑ Brodnik, Andrej; Carlsson, Svante; Sedgewick, Robert; Munro, JI; Demaine, ED (1999), Resizable Arrays in Optimal Time and Space (Technical Report CS-99-09) (PDF), Department of Computer Science, University of Waterloo
  16. ↑ 16.0 16.1 16.2 Chris Okasaki (1995). "Purely Functional Random-Access Lists". Proceedings of the Seventh International Conference on Functional Programming Languages and Computer Architecture: 86–95. doi:10.1145/224164.224187.
  17. ↑ Goodrich, Michael T.; Kloss II, John G. (1999), "Tiered Vectors: Efficient Dynamic Arrays for Rank-Based Sequences", Workshop on Algorithms and Data Structures, Lecture Notes in Computer Science, 1663: 205–216, doi:10.1007/3-540-48447-7_21, ISBN 978-3-540-66279-2
  18. ↑ 18.0 18.1 Sitarski, Edward (September 1996), "HATs: Hashed array trees", Algorithm Alley, Dr. Dobb's Journal, 21 (11)
  19. ↑ Bagwell, Phil (2002), Fast Functional Lists, Hash-Lists, Deques and Variable Length Arrays, EPFL
  20. ↑ Mike Lam. "Dynamic Arrays".
  21. ↑ "Amortized Time".
  22. ↑ "Hashed Array Tree: Efficient representation of Array".
  23. ↑ "Different notions of complexity".
  24. ↑ Peter Kankowski. "Dynamic arrays in C".
  25. ↑ Javadoc on ArrayList
  26. ↑ ArrayList Class
  27. ↑ listobject.c (github.com)

बाहरी संबंध

Retrieved from ‘https://www.vigyanwiki.in/index.php?title=गतिशील_सरणी&oldid=58327’