गतिशील सरणी: Difference between revisions

From Vigyanwiki
(Created page with "{{Short description|List data structure to which elements can be added/removed}} File:Dynamic array.svg|thumb|ज्यामितीय विस्तार का उप...")
 
No edit summary
 
(13 intermediate revisions by 4 users not shown)
Line 1: Line 1:
{{Short description|List data structure to which elements can be added/removed}}
{{Short description|List data structure to which elements can be added/removed}}
[[File:Dynamic array.svg|thumb|ज्यामितीय विस्तार का उपयोग करके गतिशील सरणी के अंत में कई मान डाले गए हैं। ग्रे सेल विस्तार के लिए आरक्षित स्थान का संकेत देते हैं। अधिकांश सम्मिलन तेज़ ([[निरंतर समय]]) होते हैं, जबकि कुछ मेमोरी प्रबंधन की आवश्यकता के कारण धीमे होते हैं ({{math|Θ(''n'')}} समय, कछुओं के साथ लेबल)। अंतिम सरणी का तार्किक आकार और क्षमता दिखाई जाती है।]][[कंप्यूटर विज्ञान]] में, एक गतिशील सरणी, बढ़ने योग्य सरणी, आकार बदलने योग्य सरणी, गतिशील तालिका, उत्परिवर्तनीय सरणी, या सरणी सूची एक यादृच्छिक अभिगम, चर-आकार [[सूची डेटा संरचना]] है जो तत्वों को जोड़ने या निकालने की अनुमति देती है। यह कई आधुनिक मुख्यधारा की [[प्रोग्रामिंग भाषा]]ओं में [[मानक पुस्तकालय]]ों के साथ आपूर्ति की जाती है। डायनेमिक सरणियाँ स्थैतिक [[सरणी डेटा प्रकार]] की एक सीमा को पार कर जाती हैं, जिनकी एक निश्चित क्षमता होती है जिसे मेमोरी प्रबंधन में निर्दिष्ट करने की आवश्यकता होती है।
[[File:Dynamic array.svg|thumb|ज्यामितीय विस्तार का उपयोग करके गतिशील सरणी के अंत में कई मान डाले गए हैं। ग्रे कोशिकाएं विस्तार के लिए आरक्षित स्थान का संकेत देते हैं। अधिकांश सम्मिलन तेज़ (निरंतर समय) होते हैं, जबकि कुछ पुनः आवंटन (Θ(n) समय, कछुओं के साथ अंकित) की आवश्यकता के कारण धीमे होते हैं। अंतिम सरणी का तार्किक आकार और क्षमता दिखाई जाती है।]]गणना विज्ञान ([[कंप्यूटर विज्ञान|कंप्यूटर विज्ञान)]] में, एक गतिशील सरणी, बढ़ने योग्य सरणी, आकार बदलने योग्य सरणी, गतिशील तालिका, उत्परिवर्तनीय सरणी, या सरणी सूची एक यादृच्छिक अभिगम, चर-आकार [[सूची डेटा संरचना|आँकड़े (डेटा) संरचना की सूची]] है जो अवयव को जोड़ने या निकालने की अनुमति देती है। यह कई आधुनिक मुख्यधारा की [[प्रोग्रामिंग भाषा|प्रोग्रामिंग भाषाओं]] में [[मानक पुस्तकालय|मानक पुस्तकालयों]] के साथ आपूर्ति की जाती है। गतिविज्ञान सरणियाँ स्थैतिक सरणियों की एक सीमा को पार करती हैं, जिनकी एक निश्चित क्षमता होती है जिसे आवंटन के समय निर्दिष्ट करने की आवश्यकता होती है।


डायनेमिक एरे [[गतिशील स्मृति आवंटन]] एरे या [[चर-लंबाई सरणी]] के समान नहीं है, इनमें से कोई भी एक एरे है जिसका आकार एरे आवंटित होने पर तय हो जाता है, हालांकि डायनेमिक एरे इस तरह के फिक्स्ड-साइज एरे का उपयोग कर सकता है पिछला अंत।<ref name="java_util_ArrayList">उदाहरण के लिए देखें, [http://hg.openjdk.java.net/jdk6/jdk6/jdk/file/e0e25ac28560/src/share/classes/java/util/ArrayList.java java.util.ArrayList का स्रोत कोड ओपनजेडीके 6 से क्लास]। </ रेफ>
एक गतिशील सरणी गतिशील रूप से आवंटित सरणी या चर-लंबाई सरणी के समान नहीं है, इनमें से कोई भी एक सरणी है जिसका आकार सरणी आवंटित होने पर तय किया गया है, हालांकि एक गतिशील सरणी बैकएंड के रूप में इस तरह के निश्चित आकार की सरणी का उपयोग कर सकती है। <ref name="java_util_ArrayList">उदाहरण के लिए देखें, [http://hg.openjdk.java.net/jdk6/jdk6/jdk/file/e0e25ac28560/src/share/classes/java/util/ArrayList.java java.util.ArrayList का स्रोत कोड ओपनजेडीके 6 से क्लास]। </ref>


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


निश्चित आकार की एक सरणी आवंटित करके एक साधारण गतिशील सरणी का निर्माण किया जा सकता है, आमतौर पर तुरंत आवश्यक तत्वों की संख्या से बड़ा। गतिशील सरणी के तत्वों को अंतर्निहित सरणी की शुरुआत में लगातार संग्रहित किया जाता है, और अंतर्निहित सरणी के अंत की शेष स्थिति आरक्षित या अप्रयुक्त होती है। आरक्षित स्थान का उपयोग करके समय जटिलता # लगातार समय में एक गतिशील सरणी के अंत में तत्वों को जोड़ा जा सकता है, जब तक कि यह स्थान पूरी तरह से खपत न हो जाए। जब सभी स्थान का उपभोग किया जाता है, और एक अतिरिक्त तत्व जोड़ा जाना है, तो अंतर्निहित निश्चित आकार के सरणी को आकार में बढ़ाना होगा। आमतौर पर आकार बदलना महंगा होता है क्योंकि इसमें एक नई अंतर्निहित सरणी आवंटित करना और प्रत्येक तत्व को मूल सरणी से कॉपी करना शामिल होता है। तत्वों को निरंतर समय में एक गतिशील सरणी के अंत से हटाया जा सकता है, क्योंकि कोई आकार बदलने की आवश्यकता नहीं है। गतिशील सरणी सामग्री द्वारा उपयोग किए जाने वाले तत्वों की संख्या इसका तार्किक आकार या आकार है, जबकि अंतर्निहित सरणी के आकार को गतिशील सरणी की क्षमता या भौतिक आकार कहा जाता है, जो डेटा को स्थानांतरित किए बिना अधिकतम संभव आकार है।<ref>{{citation|author=Lambert, Kenneth Alfred|title=Physical size and logical size|work=Fundamentals of Python: From First Programs Through Data Structures|page=510|url=https://books.google.com/books?id=VtfM3YGW5jYC&q=%22logical+size%22+%22dynamic+array%22&pg=PA518|publisher=Cengage Learning|year=2009|isbn=978-1423902188}}</ref> एक निश्चित आकार की सरणी उन अनुप्रयोगों में पर्याप्त होगी जहां अधिकतम तार्किक आकार निश्चित है (उदाहरण के लिए विनिर्देश द्वारा), या सरणी आवंटित होने से पहले गणना की जा सकती है। एक गतिशील सरणी को प्राथमिकता दी जा सकती है यदि:
निश्चित आकार की एक सरणी आवंटित करके एक साधारण गतिशील सरणी का निर्माण किया जा सकता है, सामान्यतः अविलम्ब आवश्यक तत्वों की संख्या से बड़ा होता है। गतिशील सरणी के तत्वों को अंतर्निहित सरणी की प्रारंभ में लगातार संग्रहित किया जाता है, और अंतर्निहित सरणी के अंत की शेष स्थिति आरक्षित या अप्रयुक्त होती है। आआरक्षित स्थान का उपयोग करके तत्वों को एक गतिशील सरणी के अंत में निरंतर समय में जोड़ा जा सकता है, जब तक कि यह स्थान पूरी तरह से उपभुक्त न हो जाए। जब सभी स्थान का उपभोग किया जाता है, और एक अतिरिक्त तत्व जोड़ा जाता है, तो अंतर्निहित निश्चित आकार के सरणी को आकार में बढ़ाना होगा। सामान्यतः आकार बदलना महंगा होता है क्योंकि इसमें एक नई अंतर्निहित सरणी आवंटित करना और प्रत्येक तत्व को मूल सरणी से कॉपी करना सम्मिलित होता है। तत्वों को निरंतर समय में एक गतिशील सरणी के अंत से हटाया जा सकता है, क्योंकि कोई आकार बदलने की आवश्यकता नहीं है। गतिशील सरणी सामग्री द्वारा उपयोग किए जाने वाले तत्वों की संख्या इसका तार्किक आकार या आकार है, जबकि अंतर्निहित सरणी के आकार को गतिशील सरणी की क्षमता या भौतिक आकार कहा जाता है, जो डेटा को स्थानांतरित किए बिना अधिकतम संभव आकार है।<ref>{{citation|author=Lambert, Kenneth Alfred|title=Physical size and logical size|work=Fundamentals of Python: From First Programs Through Data Structures|page=510|url=https://books.google.com/books?id=VtfM3YGW5jYC&q=%22logical+size%22+%22dynamic+array%22&pg=PA518|publisher=Cengage Learning|year=2009|isbn=978-1423902188}}</ref>
 
एक निश्चित आकार की सरणी उन अनुप्रयोगों में पर्याप्त होगी जहां अधिकतम तार्किक आकार निश्चित है (उदाहरण के लिए विनिर्देश द्वारा), या सरणी आवंटित होने से पहले गणना की जा सकती है। एक गतिशील सरणी को प्राथमिकता दी जा सकती है यदि:
* अधिकतम तार्किक आकार अज्ञात है, या सरणी आवंटित होने से पहले गणना करना मुश्किल है
* अधिकतम तार्किक आकार अज्ञात है, या सरणी आवंटित होने से पहले गणना करना मुश्किल है
* यह माना जाता है कि विनिर्देश द्वारा दिए गए अधिकतम तार्किक आकार में परिवर्तन होने की संभावना है
* यह माना जाता है कि विनिर्देश द्वारा दिए गए अधिकतम तार्किक आकार में परिवर्तन होने की संभावना है
* एक गतिशील सरणी का आकार बदलने की परिशोधित लागत प्रदर्शन या जवाबदेही को महत्वपूर्ण रूप से प्रभावित नहीं करती है
* एक गतिशील सरणी का आकार बदलने की परिशोधित लागत प्रदर्शन या अनुक्रियाशीलता को महत्वपूर्ण रूप से प्रभावित नहीं करती है


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


कई बार आकार बदलने की लागत से बचने के लिए, डायनेमिक सरणियों को बड़ी मात्रा में आकार दिया जाता है, जैसे आकार में दोगुना, और भविष्य के विस्तार के लिए आरक्षित स्थान का उपयोग करें। किसी तत्व को अंत में जोड़ने का कार्य निम्नानुसार कार्य कर सकता है:
कई बार आकार बदलने की अधिव्यय से बचने के लिए, गतिशील सरणी को बड़ी मात्रा में आकार दिया जाता है, जैसे आकार में दोगुना, और भविष्य के विस्तार के लिए आरक्षित स्थान का उपयोग करें। किसी तत्व को अंत में जोड़ने का कार्य निम्नानुसार कार्य कर सकता है:
<वाक्यविन्यास प्रकाश लैंग = सी>
 
फंक्शन इन्सर्ट एंड (डायनारे ए, एलिमेंट ई)
<syntaxhighlight lang="c">
     अगर (a.size == a.capacity)
function insertEnd(dynarray a, element e)
         // a को उसकी वर्तमान क्षमता से दोगुना आकार दें:
     if (a.size == a.capacity)
         a.क्षमता ← a.क्षमता * 2
         // resize a to twice its current capacity:
         // (सामग्री को यहां नए मेमोरी स्थान पर कॉपी करें)
         a.capacity ← a.capacity * 2  
     एक [एक आकार] ← ई
         // (copy the contents to the new memory location here)
     ए.साइज़ ← ए.साइज़ + 1
     a[a.size] ← e
</वाक्यविन्यास हाइलाइट>
     a.size ← a.size + 1
चूंकि एन तत्व डाले जाते हैं, क्षमता एक ज्यामितीय प्रगति बनाती है। किसी भी निरंतर अनुपात द्वारा सरणी का विस्तार करना सुनिश्चित करता है कि एन तत्वों को सम्मिलित करने में बिग ओ नोटेशन | ओ (एन) समय समग्र रूप से लगता है, जिसका अर्थ है कि प्रत्येक सम्मिलन [[परिशोधित विश्लेषण]] निरंतर समय लेता है। यदि इसका आकार एक निश्चित सीमा से कम हो जाता है, जैसे क्षमता का 30%, तो कई गतिशील सरणियाँ कुछ अंतर्निहित भंडारण को भी हटा देती हैं। [[हिस्टैरिसीस]] प्रदान करने के लिए (बार-बार बढ़ने और सिकुड़ने से बचने के लिए एक स्थिर बैंड प्रदान करें) और परिशोधित निरंतर लागत के साथ सम्मिलन और निष्कासन के मिश्रित अनुक्रमों का समर्थन करने के लिए यह सीमा 1/a से सख्ती से छोटी होनी चाहिए।
</syntaxhighlight>
क्योंकि ''n'' तत्व डाले जाते हैं, क्षमता एक ज्यामितीय प्रगति बनाती है। किसी भी स्थिर अनुपात द्वारा सरणी का विस्तार करना सुनिश्चित करता है कि n तत्वों को सम्मिलित करने में समग्र रूप से O(n) समय लगता है, जिसका अर्थ है कि प्रत्येक सम्मिलन में परिशोधित निरंतर समय लगता है। यदि इसका आकार एक निश्चित सीमा से कम हो जाता है, जैसे क्षमता का 30%, तो कई गतिशील सरणियाँ कुछ अंतर्निहित संग्रहण को भी हटा देती हैं। [[हिस्टैरिसीस]] प्रदान करने के लिए (बार-बार बढ़ने और सिकुड़ने से बचने के लिए एक स्थिर बैंड प्रदान करें) और परिशोधित निरंतर लागत के साथ सम्मिलन और निष्कासन के मिश्रित अनुक्रमों का समर्थन करने के लिए यह सीमा 1/a से दृढता से छोटी होनी चाहिए।


परिशोधित विश्लेषण पढ़ाते समय गतिशील सरणियाँ एक सामान्य उदाहरण हैं।<ref name="gt-ad"/><ref name="clrs"/>
परिशोधित विश्लेषण पढ़ाते समय गतिशील सरणियाँ एक सामान्य उदाहरण हैं।<ref name="gt-ad"/><ref name="clrs"/>




== विकास कारक ==
== विकास कारक ==
डायनेमिक एरे के लिए ग्रोथ फैक्टर स्पेस-टाइम ट्रेड-ऑफ और मेमोरी एलोकेटर में इस्तेमाल होने वाले एल्गोरिदम सहित कई कारकों पर निर्भर करता है। ग्रोथ फैक्टर ए के लिए, प्रति इंसर्शन ऑपरेशन का औसत समय है {{citation needed span|text=about ''a''/(''a''−1), while the number of wasted cells is bounded above by (''a''−1)''n''|date=January 2018}}. यदि मेमोरी एलोकेटर [[पहले फिट एल्गोरिदम]] | फर्स्ट-फिट एलोकेशन एल्गोरिदम का उपयोग करता है, तो वृद्धि कारक मान जैसे कि a = 2 डायनेमिक एरे एक्सपेंशन को मेमोरी से बाहर चलाने का कारण बन सकता है, भले ही मेमोरी की एक महत्वपूर्ण मात्रा अभी भी उपलब्ध हो।<ref name=":0">{{Cite web|title = सी++ एसटीएल वेक्टर: परिभाषा, विकास कारक, सदस्य कार्य|url = http://www.gahcep.com/cpp-internals-stl-vector-part-1/|access-date = 2015-08-05|archive-url = https://web.archive.org/web/20150806162750/http://www.gahcep.com/cpp-internals-stl-vector-part-1/|archive-date = 2015-08-06|url-status = dead}}</ref> स्वर्ण अनुपात के साथ-साथ मूल्य 1.5 के प्रस्तावों सहित आदर्श विकास कारक मूल्यों पर विभिन्न चर्चाएँ हुई हैं।<ref>{{Cite web|url = https://groups.google.com/forum/#!topic/comp.lang.c++.moderated/asH_VojWKJw%5B1-25%5D|title = 1.5 का वेक्टर विकास कारक|website = comp.lang.c++.moderated|publisher = Google Groups|access-date = 2015-08-05|archive-date = 2011-01-22|archive-url = http://arquivo.pt/wayback/20110122130054/https://groups.google.com/forum/#!topic/comp.lang.c++.moderated/asH_VojWKJw%5B1-25%5D|url-status = dead}}</ref> हालाँकि, कई पाठ्यपुस्तकें सरलता और विश्लेषण उद्देश्यों के लिए a = 2 का उपयोग करती हैं।<ref name="gt-ad">{{citation|first1=Michael T.|last1=Goodrich|author1-link=Michael T. Goodrich|first2=Roberto|last2=Tamassia|author2-link=Roberto Tamassia|title=Algorithm Design: Foundations, Analysis and Internet Examples|publisher=Wiley|year=2002|contribution=1.5.2 Analyzing an Extendable Array Implementation|pages=39–41}}.</ref><ref name="clrs">{{Introduction to Algorithms|chapter=17.4 Dynamic tables|edition=2|pages=416–424}}</ref>
गतिशील सरणी के लिए विकास कारक अंतराल-समय उद्योग-बंद और मेमोरी संभाजक में प्रयुक्त होने वाले एल्गोरिदम सहित कई कारकों पर निर्भर करता है। वृद्धि कारक a के लिए, प्रति सम्मिलन संचालन का औसत समय लगभग {{citation needed span|text=''a''/(''a''−1),है, जबकि व्यर्थ कोशिकाओं की संख्या (''a''−1)''n'' से ऊपर है|date=January 2018}} यदि मेमोरी आवंटनकर्ता [[पहले फिट एल्गोरिदम|प्रथम अनुरूप]] एल्गोरिदम का उपयोग करता है, तो वृद्धि कारक मान जैसे कि a = 2 गतिशील सरणी प्रसारण को मेमोरी से बाहर चलाने का कारण बन सकता है, भले ही मेमोरी की एक महत्वपूर्ण मात्रा अभी भी उपलब्ध हो।<ref name=":0">{{Cite web|title = सी++ एसटीएल वेक्टर: परिभाषा, विकास कारक, सदस्य कार्य|url = http://www.gahcep.com/cpp-internals-stl-vector-part-1/|access-date = 2015-08-05|archive-url = https://web.archive.org/web/20150806162750/http://www.gahcep.com/cpp-internals-stl-vector-part-1/|archive-date = 2015-08-06|url-status = dead}}</ref> सुनहरा अनुपात के साथ-साथ मूल्य 1.5 के प्रस्तावों सहित आदर्श विकास कारक मूल्यों पर विभिन्न चर्चाएँ हुई हैं।<ref>{{Cite web|url = https://groups.google.com/forum/#!topic/comp.lang.c++.moderated/asH_VojWKJw%5B1-25%5D|title = 1.5 का वेक्टर विकास कारक|website = comp.lang.c++.moderated|publisher = Google Groups|access-date = 2015-08-05|archive-date = 2011-01-22|archive-url = http://arquivo.pt/wayback/20110122130054/https://groups.google.com/forum/#!topic/comp.lang.c++.moderated/asH_VojWKJw%5B1-25%5D|url-status = dead}}</ref> यद्यपि, कई पाठ्य पुस्तकें सादापन और विश्लेषण उद्देश्यों के लिए a = 2 का उपयोग करती हैं।<ref name="gt-ad">{{citation|first1=Michael T.|last1=Goodrich|author1-link=Michael T. Goodrich|first2=Roberto|last2=Tamassia|author2-link=Roberto Tamassia|title=Algorithm Design: Foundations, Analysis and Internet Examples|publisher=Wiley|year=2002|contribution=1.5.2 Analyzing an Extendable Array Implementation|pages=39–41}}.</ref><ref name="clrs">{{Introduction to Algorithms|chapter=17.4 Dynamic tables|edition=2|pages=416–424}}</ref>
नीचे कई लोकप्रिय कार्यान्वयनों द्वारा उपयोग किए जाने वाले विकास कारक हैं:
 
नीचे कई प्रचलित कार्यान्वयनों द्वारा उपयोग किए जाने वाले विकास कारक हैं:
{| class="wikitable"
{| class="wikitable"
!Implementation
!कार्यान्वयन
!Growth factor (''a'')
!विकास कारक (a)
|-
|-
|Java ArrayList<ref name="java_util_ArrayList" />
|जावा ऐरेलिस्ट<ref name="java_util_ArrayList" />
|1.5 (3/2)
|1.5 (3/2)
|-
|-
|[[Python (programming language)|Python]] PyListObject<ref>[https://github.com/python/cpython/blob/bace59d8b8e38f5c779ff6296ebdc0527f6db14a/Objects/listobject.c#L58 List object implementation] from github.com/python/cpython/, retrieved 2020-03-23.</ref>
|पायथन पाइलिस्टउद्देश्य<ref>[https://github.com/python/cpython/blob/bace59d8b8e38f5c779ff6296ebdc0527f6db14a/Objects/listobject.c#L58 List object implementation] from github.com/python/cpython/, retrieved 2020-03-23.</ref>
|~1.125 (n + (n >> 3))
|~1.125 (n + (n >> 3))
|-
|-
|[[Microsoft Visual C++]] 2013<ref>{{Cite web|title = Dissecting the C++ STL Vector: Part 3 - Capacity & Size|url = https://hadibrais.wordpress.com/2013/11/15/dissecting-the-c-stl-vector-part-3-capacity/|website = Micromysteries|access-date = 2015-08-05|first = Hadi|last = Brais}}</ref>
|माइक्रोसॉफ्ट विज़ुअल [[Microsoft Visual C++|C++]] 2013<ref>{{Cite web|title = Dissecting the C++ STL Vector: Part 3 - Capacity & Size|url = https://hadibrais.wordpress.com/2013/11/15/dissecting-the-c-stl-vector-part-3-capacity/|website = Micromysteries|access-date = 2015-08-05|first = Hadi|last = Brais}}</ref>
|1.5 (3/2)
|1.5 (3/2)
|-
|-
Line 47: Line 61:
|2
|2
|-
|-
|[[Clang]] 3.6<ref name=":0" />
|[[Clang|क्लैंग]] 3.6<ref name=":0" />
|2
|2
|-
|-
|Facebook folly/FBVector<ref>{{Cite web|title = facebook/folly|url = https://github.com/facebook/folly/blob/master/folly/docs/FBVector.md|website = GitHub|access-date = 2015-08-05}}</ref>
|फेसबुक फौली / एफबी वेक्टर<ref>{{Cite web|title = facebook/folly|url = https://github.com/facebook/folly/blob/master/folly/docs/FBVector.md|website = GitHub|access-date = 2015-08-05}}</ref>
|1.5 (3/2)
|1.5 (3/2)
|-
|-
|Rust Vec<ref>{{Cite web|title=rust-lang/rust|url=https://github.com/rust-lang/rust/blob/fd4b177aabb9749dfb562c48e47379cea81dc277/src/liballoc/raw_vec.rs#L443|access-date=2020-06-09|website=GitHub|language=en}}</ref>
|रस्ट वेक<ref>{{Cite web|title=rust-lang/rust|url=https://github.com/rust-lang/rust/blob/fd4b177aabb9749dfb562c48e47379cea81dc277/src/liballoc/raw_vec.rs#L443|access-date=2020-06-09|website=GitHub|language=en}}</ref>
|2
|2
|-
|-
|[[Go (programming language)|Go]] slices<ref>{{Cite web|title = golang/go|url = https://github.com/golang/go/blob/master/src/runtime/slice.go#L188|website=GitHub|access-date = 2021-09-14}}</ref>
|[[Go (programming language)|Go]] स्लाइसेस<ref>{{Cite web|title = golang/go|url = https://github.com/golang/go/blob/master/src/runtime/slice.go#L188|website=GitHub|access-date = 2021-09-14}}</ref>
|between 1.25 and 2
|1.25 और 2 के बीच
|-
|-
|[[Nim (programming language)|Nim]] sequences<ref>{{Cite web |title=The Nim memory model |url=http://zevv.nl/nim-memory/#_growing_a_seq |access-date=2022-05-24 |website=zevv.nl}}</ref>
|निम अनुक्रम<ref>{{Cite web |title=The Nim memory model |url=http://zevv.nl/nim-memory/#_growing_a_seq |access-date=2022-05-24 |website=zevv.nl}}</ref>
|2
|2
|}
|}


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


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


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


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


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


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


गुडरिक<ref>{{Citation | title=Tiered Vectors: Efficient Dynamic Arrays for Rank-Based Sequences | first1=Michael T. | last1=Goodrich | author1-link=Michael T. Goodrich | first2=John G. | last2=Kloss II | year=1999 | url=https://archive.org/details/algorithmsdatast0000wads/page/205 | journal=[[Workshop on Algorithms and Data Structures]] | pages=[https://archive.org/details/algorithmsdatast0000wads/page/205 205–216] | doi=10.1007/3-540-48447-7_21 | volume=1663 | series=Lecture Notes in Computer Science | isbn=978-3-540-66279-2 | url-access=registration }}</ref> एक डायनेमिक ऐरे एल्गोरिथम प्रस्तुत किया जिसे टायर्ड वैक्टर कहा जाता है जो O(n<sup>1/k</sup>) सरणी में कहीं से भी सम्मिलन और विलोपन के लिए प्रदर्शन, और O(k) मिलता है और सेट होता है, जहाँ k ≥ 2 एक स्थिर पैरामीटर है।
गुडरिक<ref>{{Citation | title=Tiered Vectors: Efficient Dynamic Arrays for Rank-Based Sequences | first1=Michael T. | last1=Goodrich | author1-link=Michael T. Goodrich | first2=John G. | last2=Kloss II | year=1999 | url=https://archive.org/details/algorithmsdatast0000wads/page/205 | journal=[[Workshop on Algorithms and Data Structures]] | pages=[https://archive.org/details/algorithmsdatast0000wads/page/205 205–216] | doi=10.1007/3-540-48447-7_21 | volume=1663 | series=Lecture Notes in Computer Science | isbn=978-3-540-66279-2 | url-access=registration }}</ref> एक गतिशील सरणियों एल्गोरिथम ने प्रस्तुत किया जिसे स्तरित सदिश कहा जाता है जो सरणियों में कहीं से भी सम्मिलन और विलोपन के लिए O(n<sup>1/k</sup>) प्रदर्शन प्रदान करता है, और O(k) प्राप्त और उत्पन्न करता है, जहां k ≥ 2 एक स्थिर मापदण्ड है।


[[हैशेड ऐरे ट्री]] (HAT) 1996 में सितारस्की द्वारा प्रकाशित एक डायनेमिक ऐरे एल्गोरिथम है।<ref name="sitarski96">{{Citation | title=HATs: Hashed array trees | department=Algorithm Alley | journal=Dr. Dobb's Journal | date=September 1996 | first1=Edward | last1=Sitarski | volume=21 | issue=11 | url=http://www.ddj.com/architect/184409965?pgno=5}}</ref> हैशेड ऐरे ट्री वेस्ट ऑर्डर एन<sup>1/2</sup> संग्रहण स्थान की मात्रा, जहाँ n सरणी में तत्वों की संख्या है। हैशेड ऐरे ट्री के अंत में ऑब्जेक्ट्स की एक श्रृंखला को जोड़ते समय एल्गोरिथ्म में O (1) परिशोधित प्रदर्शन होता है।
[[हैशेड ऐरे ट्री|हैशेड सरणी वृक्ष]] (HAT) 1996 में सितारस्की द्वारा प्रकाशित एक गतिशील सरणियों एल्गोरिथम है।<ref name="sitarski96">{{Citation | title=HATs: Hashed array trees | department=Algorithm Alley | journal=Dr. Dobb's Journal | date=September 1996 | first1=Edward | last1=Sitarski | volume=21 | issue=11 | url=http://www.ddj.com/architect/184409965?pgno=5}}</ref> हैशेड सरणी ट्री स्टोरेज स्पेस की ''n''<sup>1/2</sup> मात्रा को बर्बाद करता है, जहाँ n सरणी में तत्वों की संख्या है। हैशेड सरणी ट्री के अंत में वस्तुओं की एक श्रृंखला को जोड़ते समय एल्गोरिथ्म में O(1) परिशोधित प्रदर्शन होता है।


1999 के एक पेपर में,<ref name="brodnik">{{Citation | title=Resizable Arrays in Optimal Time and Space |type=Technical Report CS-99-09 | url=http://www.cs.uwaterloo.ca/research/tr/1999/09/CS-99-09.pdf | year=1999 | first1=Andrej | last1=Brodnik | first2=Svante | last2=Carlsson | first5=ED | last5=Demaine | first4=JI | last4=Munro | first3=Robert | last3=Sedgewick | author3-link=Robert Sedgewick (computer scientist) | publisher=Department of Computer Science, University of Waterloo}}</ref><!-- Defined in {{List data structure comparison}}: {{Citation | title=Resizable Arrays in Optimal Time and Space | date=Technical Report CS-99-09 | url=http://www.cs.uwaterloo.ca/research/tr/1999/09/CS-99-09.pdf | year=1999 | first1=Andrej | last1=Brodnik | first2=Svante | last2=Carlsson | first5=ED | last5=Demaine | first4=JI | last4=Munro | first3=Robert | last3=Sedgewick | author3-link=Robert Sedgewick (computer scientist) | publisher=Department of Computer Science, University of Waterloo}} --> ब्रोडनिक एट अल। एक स्तरीय गतिशील सरणी डेटा संरचना का वर्णन करें, जो केवल एन को बर्बाद करता है<sup>किसी भी समय n तत्वों के लिए 1/2 </sup> स्थान, और वे यह दिखाते हुए एक निचली सीमा साबित करते हैं कि किसी भी गतिशील सरणी को इतना स्थान बर्बाद करना होगा यदि संचालन को स्थिर समय रहना है। इसके अतिरिक्त, वे एक संस्करण प्रस्तुत करते हैं जहां बफर के बढ़ने और सिकुड़ने से न केवल परिशोधन होता है, बल्कि सबसे खराब समय भी होता है।
1999 के एक पेपर में, ब्रोडनिक एट अल। एक स्तरीय गतिशील सरणी डेटा संरचना, जो समय पर किसी भी बिंदु पर n तत्वों के लिए केवल n1/2 स्थान बर्बाद करता है, और वे यह दिखाते हुए एक निचली सीमा साबित करते हैं कि किसी भी गतिशील सरणी को इतना स्थान बर्बाद करना होगा यदि संचालन निरंतर समय को परिशोधित करना है। इसके अतिरिक्त, वे एक संस्करण प्रस्तुत करते हैं जहां बफर के बढ़ने और सिकुड़ने से न केवल परिशोधन होता है, बल्कि सबसे खराब समय भी होता है।


बागवेल (2002)<ref>{{Citation | title=Fast Functional Lists, Hash-Lists, Deques and Variable Length Arrays | first1=Phil | last1=Bagwell | year=2002 | publisher=EPFL | url=http://citeseer.ist.psu.edu/bagwell02fast.html}}</ref> VList एल्गोरिथ्म प्रस्तुत किया, जिसे एक गतिशील सरणी को लागू करने के लिए अनुकूलित किया जा सकता है।
बागवेल (2002)<ref>{{Citation | title=Fast Functional Lists, Hash-Lists, Deques and Variable Length Arrays | first1=Phil | last1=Bagwell | year=2002 | publisher=EPFL | url=http://citeseer.ist.psu.edu/bagwell02fast.html}}</ref> ने वी लिस्ट एल्गोरिथम प्रस्तुत किया, जिसे एक गतिशील सरणी को अनुबंध करने के लिए अनुकूलित किया जा सकता है।


नाओव आकार बदलने योग्य सरणी - जिसे आकार बदलने योग्य सरणी का सबसे खराब कार्यान्वयन भी कहा जाता है - सरणी के आवंटित आकार को इसमें शामिल सभी डेटा के लिए पर्याप्त रूप से बड़ा रखें, शायद सरणी में जोड़े गए प्रत्येक आइटम के लिए रीयलोक को कॉल करके। सी में एक आकार बदलने योग्य सरणी को लागू करने का आसान आकार बदलने योग्य सरणी सबसे आसान तरीका है। वे किसी भी स्मृति को बर्बाद नहीं करते हैं, लेकिन सरणी के अंत में संलग्न होने में हमेशा Θ (एन) समय लगता है।<ref name="sitarski96" /><ref>
नाओव आकार बदलने योग्य सरणी - जिसे आकार बदलने योग्य सरणी का सबसे खराब कार्यान्वयन भी कहा जाता है - सरणी के आवंटित आकार को इसमें सम्मिलित सभी डेटा के लिए पर्याप्त रूप से बड़ा रखें, संभवतः सरणी में जोड़े गए प्रत्येक विषय के लिए रीयलोक को कॉल करके C में एक आकार बदलने योग्य सरणी को लागू करने का सबसे सरल तरीका अनुभवहीन आकार बदलने योग्य सरणी है। वे किसी भी मेमोरी को व्यर्थ नहीं करते हैं, लेकिन सरणी के अंत में सम्मिलित होने में हमेशा Θ(n) समय लगता है।<ref name="sitarski96" /><ref>
Mike Lam.
Mike Lam.
[https://w3.cs.jmu.edu/lam2mo/cs240_2015_08/files/04-dyn_arrays.pdf "Dynamic Arrays"].
[https://w3.cs.jmu.edu/lam2mo/cs240_2015_08/files/04-dyn_arrays.pdf "Dynamic Arrays"].
Line 101: Line 114:
[https://people.ksp.sk/~kuko/gnarley-trees/Complexity2.html "Different notions of complexity"].
[https://people.ksp.sk/~kuko/gnarley-trees/Complexity2.html "Different notions of complexity"].
</ref>
</ref>
रैखिक रूप से बढ़ने वाली सरणियाँ पूर्व-आवंटन (अपशिष्ट) Θ (1) स्थान हर बार जब वे सरणी को फिर से आकार देती हैं, तो उन्हें भोले आकार देने योग्य सरणियों की तुलना में कई गुना तेज बना देती हैं - सरणी के अंत में संलग्न होने में अभी भी Θ (n) समय लगता है लेकिन साथ बहुत छोटा स्थिरांक।
रैखिक रूप से बढ़ने वाली सरणियाँ पूर्व-आवंटन (अपशिष्ट) Θ (1) स्थान हर बार जब वे सरणी को फिर से आकार देती हैं, तो उन्हें नैवे आकार देने योग्य सरणियों की तुलना में कई गुना तेज बना देती हैं - सरणी के अंत में संलग्न होने में अभी भी Θ (n) समय लगता है लेकिन बहुत छोटे स्थिरांक के साथ।
भोले आकार बदलने योग्य सरणियाँ और रैखिक रूप से बढ़ने वाली सरणियाँ तब उपयोगी हो सकती हैं जब अंतरिक्ष-बाधित अनुप्रयोग को बहुत से छोटे आकार बदलने योग्य सरणियों की आवश्यकता होती है;
सरल आकार बदलने योग्य सरणियाँ और रैखिक रूप से बढ़ने वाली सरणियाँ तब उपयोगी हो सकती हैं जब अंतरिक्ष-बाधित अनुप्रयोग को बहुत से सूक्ष्म आकार बदलने योग्य सरणियों की आवश्यकता होती है;
वे आमतौर पर एक शैक्षिक उदाहरण के रूप में भी उपयोग किए जाते हैं जो तेजी से बढ़ते गतिशील सरणियों के लिए अग्रणी होते हैं।<ref>
वे सामान्यतया पर एक शैक्षिक उदाहरण के रूप में भी उपयोग किए जाते हैं जो तेजी से बढ़ते गतिशील सरणियों के लिए अग्रणी होते हैं।<ref>
Peter Kankowski.
Peter Kankowski.
[https://www.strchr.com/dynamic_arrays "Dynamic arrays in C"].
[https://www.strchr.com/dynamic_arrays "Dynamic arrays in C"].
</ref>
</ref>
== भाषा समर्थन ==


[[सी ++|C ++<code>एसटीडी :: वेक्टर</code>]]  और रस्ट  [[जंग (प्रोग्रामिंग भाषा)|(प्रोग्रामिंग भाषा)]] [[सी ++|<code>एसटीडी :: वेक्टर:: वेक्टर</code>]] गतिशील सरणियों के कार्यान्वयन हैं, जैसा कि हैं <ref>Javadoc on {{Javadoc:SE|java/util|ArrayList}}</ref> [[जावा (प्रोग्रामिंग भाषा)]] API और NET फ्रेमवर्क के साथ प्रदान की जाने वाली सारणी सूची कक्षाएं हैं।<ref>[https://msdn.microsoft.com/en-us/library/system.collections.arraylist ArrayList Class]</ref>


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


[[सी ++]] का वेक्टर (सी ++) |<code>std::vector</code>और [[जंग (प्रोग्रामिंग भाषा)]] की <code>std::vec::Vec</code> गतिशील सरणियों के कार्यान्वयन हैं, जैसा कि हैं <code>ArrayList</code><ref>Javadoc on {{Javadoc:SE|java/util|ArrayList}}</ref> [[जावा (प्रोग्रामिंग भाषा)]] एपीआई और .NET फ्रेमवर्क के साथ प्रदान की जाने वाली कक्षाएं।<ref>[https://msdn.microsoft.com/en-us/library/system.collections.arraylist ArrayList Class]</ref> सामान्य <code>List<></code> .NET फ्रेमवर्क के संस्करण 2.0 के साथ आपूर्ति की गई क्लास को डायनेमिक सरणियों के साथ भी लागू किया गया है। स्मॉलटॉक <code>OrderedCollection</code> डायनेमिक स्टार्ट और एंड-इंडेक्स के साथ एक डायनेमिक एरे है, जिससे पहले एलिमेंट को भी O (1) हटा दिया जाता है।
पायथन सूची डेटा प्रकार कार्यान्वयन एक गतिशील सरणी है जिसका विकास स्वरूप :0, 4, 8, 16, 24, 32, 40, 52, 64, 76, ...है<ref>[https://github.com/python/cpython/blob/bace59d8b8e38f5c779ff6296ebdc0527f6db14a/Objects/listobject.c#L58 listobject.c (github.com)]</ref>  


पायथन (प्रोग्रामिंग लैंग्वेज)। <code>list</code> डेटाटाइप कार्यान्वयन एक गतिशील सरणी है जिसका विकास पैटर्न है: 0, 4, 8, 16, 24, 32, 40, 52, 64, 76, ...<ref>[https://github.com/python/cpython/blob/bace59d8b8e38f5c779ff6296ebdc0527f6db14a/Objects/listobject.c#L58 listobject.c (github.com)]</ref> [[डेल्फी (प्रोग्रामिंग भाषा)]] और [[डी (प्रोग्रामिंग भाषा)]] भाषा के मूल में गतिशील सरणियों को लागू करते हैं।
[[डेल्फी (प्रोग्रामिंग भाषा)]] और [[डी (प्रोग्रामिंग भाषा)]] भाषा के मूल में गतिशील सरणियों को प्रवर्तित करते हैं।


एडा (प्रोग्रामिंग लैंग्वेज) की विकिबुक: एडा प्रोग्रामिंग/लाइब्रेरी/एडा.कॉन्टेनर्स.वेक्टर|<code>Ada.Containers.Vectors</code>जेनेरिक पैकेज किसी दिए गए उपप्रकार के लिए गतिशील सरणी कार्यान्वयन प्रदान करता है।
एडा (प्रोग्रामिंग लैंग्वेज) <code>एडा.कंटेनर.वैक्टर</code>सामान्य संवेष्टन किसी दिए गए उपप्रकार के लिए गतिशील सरणी कार्यान्वयन प्रदान करता है।


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


कई क्रॉस-प्लेटफ़ॉर्म ढांचे [[सी (प्रोग्रामिंग भाषा)]] के लिए गतिशील सरणी कार्यान्वयन प्रदान करते हैं, जिनमें शामिल हैं <code>CFArray</code> तथा <code>CFMutableArray</code> [[कोर फाउंडेशन]] में, और <code>GArray</code> तथा <code>GPtrArray</code> जीएलआईबी में।
कई क्रॉस-प्लेटफ़ॉर्म फ्रेमवर्क [[सी (प्रोग्रामिंग भाषा)|C (प्रोग्रामिंग भाषा)]] के लिए गतिशील सरणी कार्यान्वयन प्रदान करते हैं, जिनमें सम्मिलित हैं <code>सीएफ</code> तथा <code>सीएफ उत्परिवर्तनीय सरणी</code> [[कोर फाउंडेशन|बीजकोष  संस्थान]] में, और <code>जी सरणी</code> तथा <code>जीपी टीआर सरणी</code>ग्लिब.में।


[[सामान्य लिस्प]] बिल्ट-इन को कॉन्फ़िगर करने की अनुमति देकर आकार बदलने योग्य वैक्टर के लिए प्राथमिक समर्थन प्रदान करता है <code>array</code> समायोज्य के रूप में टाइप करें और भरण-सूचक द्वारा सम्मिलन का स्थान।
[[सामान्य लिस्प]] अंतर्निर्मित सरणी समायोज्य के रूप में और भरण-सूचक द्वारा निवेशन के स्थान को समनुरूप करने की अनुमति देकर आकार बदलने योग्य वैक्टर के लिए एक अल्पविकसित समर्थन प्रदान करता है।


== संदर्भ ==
== संदर्भ ==
<references />
<references />


==इस पेज में लापता आंतरिक लिंक की सूची==
*स्मृति प्रबंधन
*रैंडम एक्सेस
*ज्यामितीय अनुक्रम
*सुनहरा अनुपात
*लिंक्ड सूची
*संदर्भ का इलाका
*कैश (कंप्यूटिंग)
*realloc
*छोटी बात
*पायथन (प्रोग्रामिंग भाषा)
*एडा (प्रोग्रामिंग भाषा)
*फिसलनदार
== बाहरी संबंध ==
== बाहरी संबंध ==
* [https://xlinux.nist.gov/dads/HTML/dynamicarray.html NIST Dictionary of Algorithms and Data Structures: Dynamic array]
* [https://xlinux.nist.gov/dads/HTML/dynamicarray.html NIST Dictionary of Algorithms and Data Structures: Dynamic array]
Line 150: Line 149:
{{Data structures}}
{{Data structures}}


{{DEFAULTSORT:Dynamic Array}}[[Category:सारणी]]
{{DEFAULTSORT:Dynamic Array}}
[[Category: स्यूडोकोड उदाहरण के साथ लेख]]
[[Category: परिशोधित डेटा संरचनाएं]]
 


[[Category: Machine Translated Page]]
[[Category:All articles with unsourced statements|Dynamic Array]]
[[Category:Created On 15/12/2022]]
[[Category:Articles with invalid date parameter in template|Dynamic Array]]
[[Category:Articles with short description|Dynamic Array]]
[[Category:Articles with unsourced statements from January 2018|Dynamic Array]]
[[Category:CS1 English-language sources (en)]]
[[Category:CS1 français-language sources (fr)]]
[[Category:CS1 maint]]
[[Category:CS1 Ελληνικά-language sources (el)]]
[[Category:Citation Style 1 templates|W]]
[[Category:Collapse templates|Dynamic Array]]
[[Category:Created On 15/12/2022|Dynamic Array]]
[[Category:Machine Translated Page|Dynamic Array]]
[[Category:Navigational boxes| ]]
[[Category:Navigational boxes without horizontal lists|Dynamic Array]]
[[Category:Pages with TemplateStyles errors]]
[[Category:Pages with reference errors|Dynamic Array]]
[[Category:Pages with script errors|Dynamic Array]]
[[Category:Short description with empty Wikidata description|Dynamic Array]]
[[Category:Sidebars with styles needing conversion|Dynamic Array]]
[[Category:Template documentation pages|Documentation/doc]]
[[Category:Templates based on the Citation/CS1 Lua module]]
[[Category:Templates generating COinS|Cite web]]
[[Category:Templates generating microformats|Dynamic Array]]
[[Category:Templates that are not mobile friendly|Dynamic Array]]
[[Category:Templates used by AutoWikiBrowser|Cite web]]
[[Category:Templates using TemplateData|Dynamic Array]]
[[Category:Wikipedia fully protected templates|Cite web]]
[[Category:Wikipedia metatemplates|Dynamic Array]]

Latest revision as of 10:06, 1 January 2023

ज्यामितीय विस्तार का उपयोग करके गतिशील सरणी के अंत में कई मान डाले गए हैं। ग्रे कोशिकाएं विस्तार के लिए आरक्षित स्थान का संकेत देते हैं। अधिकांश सम्मिलन तेज़ (निरंतर समय) होते हैं, जबकि कुछ पुनः आवंटन (Θ(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’