गतिशील सरणी: 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|ज्यामितीय विस्तार का उप...")
 
(TEXT)
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|ज्यामितीय विस्तार का उपयोग करके गतिशील सरणी के अंत में कई मान डाले गए हैं। ग्रे सेल विस्तार के लिए आरक्षित स्थान का संकेत देते हैं। अधिकांश सम्मिलन तेज़ ([[निरंतर समय]]) होते हैं, जबकि कुछ मेमोरी प्रबंधन की आवश्यकता के कारण धीमे होते हैं ({{math|Θ(''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>{{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>  
 
== परिबद्ध-आकार गतिशील सरणियाँ और क्षमता ==
निश्चित आकार की एक सरणी आवंटित करके एक साधारण गतिशील सरणी का निर्माण किया जा सकता है, सामान्यतया पर तुरंत आवश्यक तत्वों की संख्या से बड़ा होता है। गतिशील सरणी के तत्वों को अंतर्निहित सरणी की आरम्भ में लगातार संग्रहित किया जाता है, और अंतर्निहित सरणी के अंत की शेष स्थिति आरक्षित या अप्रयुक्त होती है। आरक्षित स्थान का उपयोग करके तत्वों को एक गतिशील सरणी के अंत में निरंतर समय में जोड़ा जा सकता है, जब तक कि यह स्थान पूरी तरह से उपभुक्त न हो जाए। जब सभी स्थान का उपभोग किया जाता है, और एक अतिरिक्त तत्व जोड़ा जाना है, तो अंतर्निहित निश्चित आकार के सरणी को आकार में बढ़ाना होगा। सामान्यतया  पर आकार बदलना महंगा होता है क्योंकि इसमें एक नई अंतर्निहित सरणी आवंटित करना और प्रत्येक तत्व को मूल सरणी से प्रतिलिपि करना सम्मिलित होता है। तत्वों को निरंतर समय में एक गतिशील सरणी के अंत से हटाया जा सकता है, क्योंकि कोई आकार बदलने की आवश्यकता नहीं है। गतिशील सरणी सामग्री द्वारा उपयोग किए जाने वाले तत्वों की संख्या इसका तार्किक आकार या आकार है, जबकि अंतर्निहित सरणी के आकार को गतिशील सरणी की क्षमता या भौतिक आकार कहा जाता है, जो डेटा को स्थानांतरित किए बिना अधिकतम संभव आकार है।
 
एक निश्चित आकार की सरणी उन अनुप्रयोगों में पर्याप्त होगी जहां अधिकतम तार्किक आकार निश्चित है (उदाहरण के लिए विनिर्देश द्वारा), या सरणी आवंटित होने से पहले गणना की जा सकती है। एक गतिशील सरणी को प्राथमिकता दी जा सकती है यदि:
* अधिकतम तार्किक आकार अज्ञात है, या सरणी आवंटित होने से पहले गणना करना मुश्किल है
* अधिकतम तार्किक आकार अज्ञात है, या सरणी आवंटित होने से पहले गणना करना मुश्किल है
* यह माना जाता है कि विनिर्देश द्वारा दिए गए अधिकतम तार्किक आकार में परिवर्तन होने की संभावना है
* यह माना जाता है कि विनिर्देश द्वारा दिए गए अधिकतम तार्किक आकार में परिवर्तन होने की संभावना है
Line 13: Line 18:
== ज्यामितीय विस्तार और परिशोधित लागत ==
== ज्यामितीय विस्तार और परिशोधित लागत ==


कई बार आकार बदलने की लागत से बचने के लिए, डायनेमिक सरणियों को बड़ी मात्रा में आकार दिया जाता है, जैसे आकार में दोगुना, और भविष्य के विस्तार के लिए आरक्षित स्थान का उपयोग करें। किसी तत्व को अंत में जोड़ने का कार्य निम्नानुसार कार्य कर सकता है:
कई बार आकार बदलने की अधिव्यय से बचने के लिए, गतिशील सरणी को बड़ी मात्रा में आकार दिया जाता है, जैसे आकार में दोगुना, और भविष्य के विस्तार के लिए आरक्षित स्थान का उपयोग करें। किसी तत्व को अंत में जोड़ने का कार्य निम्नानुसार कार्य कर सकता है:
<वाक्यविन्यास प्रकाश लैंग = सी>
 
फंक्शन इन्सर्ट एंड (डायनारे ए, एलिमेंट ई)
प्रकार्य सम्मिलित करें समाप्त करें (डायनेरे a, तत्व e)
     अगर (a.size == a.capacity)
     अगर (a.size == a.capacity)
         // a को उसकी वर्तमान क्षमता से दोगुना आकार दें:
         // a को उसकी वर्तमान क्षमता से दोगुना आकार दें:
         a.क्षमता ← a.क्षमता * 2
         a.क्षमता ← a.क्षमता * 2
         // (सामग्री को यहां नए मेमोरी स्थान पर कॉपी करें)
         // (विषयसूची को यहां नए मेमोरी स्थान पर अनुकरण करें)
     एक [एक आकार] ← ई
     a [a आकार] ← e
     ए.साइज़ ← ए.साइज़ + 1
     a.साइज़ ← a.साइज़ + 1
</वाक्यविन्यास हाइलाइट>
क्योंकि ''n'' तत्व डाले जाते हैं, क्षमता एक ज्यामितीय प्रगति बनाती है। किसी भी स्थिर अनुपात द्वारा सरणी का विस्तार करना सुनिश्चित करता है कि n तत्वों को सम्मिलित करने में समग्र रूप से O(n) समय लगता है, जिसका अर्थ है कि प्रत्येक सम्मिलन में परिशोधित निरंतर समय लगता है। यदि इसका आकार एक निश्चित सीमा से कम हो जाता है, जैसे क्षमता का 30%, तो कई गतिशील सरणियाँ कुछ अंतर्निहित भंडारण को भी हटा देती हैं। [[हिस्टैरिसीस]] प्रदान करने के लिए (बार-बार बढ़ने और संकुचन  से बचने के लिए एक स्थिर बैंड प्रदान करें) और परिशोधित निरंतर लागत के साथ सम्मिलन और निष्कासन के मिश्रित अनुक्रमों का समर्थन करने के लिए यह सीमा 1/a से दृढता से छोटी होनी चाहिए।
चूंकि एन तत्व डाले जाते हैं, क्षमता एक ज्यामितीय प्रगति बनाती है। किसी भी निरंतर अनुपात द्वारा सरणी का विस्तार करना सुनिश्चित करता है कि एन तत्वों को सम्मिलित करने में बिग ओ नोटेशन | ओ (एन) समय समग्र रूप से लगता है, जिसका अर्थ है कि प्रत्येक सम्मिलन [[परिशोधित विश्लेषण]] निरंतर समय लेता है। यदि इसका आकार एक निश्चित सीमा से कम हो जाता है, जैसे क्षमता का 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>
डायनेमिक एरे के लिए ग्रोथ फैक्टर स्पेस-टाइम ट्रेड-ऑफ और मेमोरी एलोकेटर में इस्तेमाल होने वाले एल्गोरिदम सहित कई कारकों पर निर्भर करता है। ग्रोथ फैक्टर ए के लिए, प्रति इंसर्शन ऑपरेशन का औसत समय है {{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>
Line 74: Line 76:
* सरणी के अंत में एक तत्व सम्मिलित करना या हटाना (निरंतर परिशोधन समय)
* सरणी के अंत में एक तत्व सम्मिलित करना या हटाना (निरंतर परिशोधन समय)


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


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


एक [[सेल्फ-बैलेंसिंग बाइनरी सर्च ट्री]] डायनेमिक सरणियों और लिंक्ड सूचियों दोनों के सभी संचालन को यथोचित कुशलता से प्रदान करते हुए एक सूची को संग्रहीत कर सकता है, लेकिन अंत में सम्मिलन और सूची में पुनरावृत्ति दोनों एक गतिशील सरणी की तुलना में धीमी हैं, सिद्धांत और व्यवहार में, गैर-सन्निहित भंडारण और ट्री ट्रैवर्सल/मैनिपुलेशन ओवरहेड के कारण।
एक [[सेल्फ-बैलेंसिंग बाइनरी सर्च ट्री]] डायनेमिक सरणियों और लिंक्ड सूचियों दोनों के सभी संचालन को यथोचित कुशलता से प्रदान करते हुए एक सूची को संग्रहीत कर सकता है, लेकिन अंत में सम्मिलन और सूची में पुनरावृत्ति दोनों एक गतिशील सरणी की तुलना में धीमी हैं, सिद्धांत और व्यवहार में, गैर-सन्निहित भंडारण और ट्री ट्रैवर्सल/मैनिपुलेशन ओवरहेड के कारण।
Line 91: Line 93:
बागवेल (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> VList एल्गोरिथ्म प्रस्तुत किया, जिसे एक गतिशील सरणी को लागू करने के लिए अनुकूलित किया जा सकता है।


नाओव आकार बदलने योग्य सरणी - जिसे आकार बदलने योग्य सरणी का सबसे खराब कार्यान्वयन भी कहा जाता है - सरणी के आवंटित आकार को इसमें शामिल सभी डेटा के लिए पर्याप्त रूप से बड़ा रखें, शायद सरणी में जोड़े गए प्रत्येक आइटम के लिए रीयलोक को कॉल करके। सी में एक आकार बदलने योग्य सरणी को लागू करने का आसान आकार बदलने योग्य सरणी सबसे आसान तरीका है। वे किसी भी स्मृति को बर्बाद नहीं करते हैं, लेकिन सरणी के अंत में संलग्न होने में हमेशा Θ (एन) समय लगता है।<ref name="sitarski96" /><ref>
नाओव आकार बदलने योग्य सरणी - जिसे आकार बदलने योग्य सरणी का सबसे खराब कार्यान्वयन भी कहा जाता है - सरणी के आवंटित आकार को इसमें सम्मिलित  सभी डेटा के लिए पर्याप्त रूप से बड़ा रखें, शायद सरणी में जोड़े गए प्रत्येक आइटम के लिए रीयलोक को कॉल करके। सी में एक आकार बदलने योग्य सरणी को लागू करने का आसान आकार बदलने योग्य सरणी सबसे आसान तरीका है। वे किसी भी स्मृति को बर्बाद नहीं करते हैं, लेकिन सरणी के अंत में संलग्न होने में हमेशा Θ (एन) समय लगता है।<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 103: Line 105:
रैखिक रूप से बढ़ने वाली सरणियाँ पूर्व-आवंटन (अपशिष्ट) Θ (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>
== भाषा समर्थन ==
== भाषा समर्थन ==


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


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


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

Revision as of 00:46, 22 December 2022

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

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

एक गतिशील सरणी गतिशील रूप से आवंटित सरणी या चर-लंबाई सरणी के समान नहीं है, इनमें से कोई भी एक सरणी है जिसका आकार सरणी आवंटित होने पर तय किया गया है, हालांकि एक गतिशील सरणी बैकएंड के रूप में इस तरह के निश्चित आकार के सरणी का उपयोग कर सकती है। Cite error: Closing </ref> missing for <ref> tag

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

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

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

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

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

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

प्रकार्य सम्मिलित करें समाप्त करें (डायनेरे a, तत्व e) 

   अगर (a.size == a.capacity)
       // a को उसकी वर्तमान क्षमता से दोगुना आकार दें:
       a.क्षमता ← a.क्षमता * 2
       // (विषयसूची को यहां नए मेमोरी स्थान पर अनुकरण करें)
   a [a आकार] ← e
   a.साइज़ ← a.साइज़ + 1

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

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

विकास कारक

डायनेमिक एरे के लिए ग्रोथ फैक्टर स्पेस-टाइम ट्रेड-ऑफ और मेमोरी एलोकेटर में इस्तेमाल होने वाले एल्गोरिदम सहित कई कारकों पर निर्भर करता है। ग्रोथ फैक्टर ए के लिए, प्रति इंसर्शन ऑपरेशन का औसत समय है about a/(a−1), while the number of wasted cells is bounded above by (a−1)n[citation needed]. यदि मेमोरी एलोकेटर पहले फिट एल्गोरिदम | फर्स्ट-फिट एलोकेशन एल्गोरिदम का उपयोग करता है, तो वृद्धि कारक मान जैसे कि a = 2 डायनेमिक एरे एक्सपेंशन को मेमोरी से बाहर चलाने का कारण बन सकता है, भले ही मेमोरी की एक महत्वपूर्ण मात्रा अभी भी उपलब्ध हो।[3] स्वर्ण अनुपात के साथ-साथ मूल्य 1.5 के प्रस्तावों सहित आदर्श विकास कारक मूल्यों पर विभिन्न चर्चाएँ हुई हैं।[4] हालाँकि, कई पाठ्यपुस्तकें सरलता और विश्लेषण उद्देश्यों के लिए a = 2 का उपयोग करती हैं।[1][2] नीचे कई लोकप्रिय कार्यान्वयनों द्वारा उपयोग किए जाने वाले विकास कारक हैं:

Implementation Growth factor (a)
Java ArrayList[5] 1.5 (3/2)
Python PyListObject[6] ~1.125 (n + (n >> 3))
Microsoft Visual C++ 2013[7] 1.5 (3/2)
G++ 5.2.0[3] 2
Clang 3.6[3] 2
Facebook folly/FBVector[8] 1.5 (3/2)
Rust Vec[9] 2
Go slices[10] between 1.25 and 2
Nim sequences[11] 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)[12][13] 		Θ(n)
Array Θ(1) — — — 0
Dynamic array Θ(1) Θ(n) Θ(1) amortized Θ(n) Θ(n)[14]
Balanced tree Θ(log n) Θ(log n) Θ(log n) Θ(log n) Θ(n)
Random-access list Θ(log n)[15] Θ(1) —[15] —[15] Θ(n)
Hashed array tree Θ(1) Θ(n) Θ(1) amortized Θ(n) Θ(√n)

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

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

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

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

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

वेरिएंट

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

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

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

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

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

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

भाषा समर्थन

सी ++ का वेक्टर (सी ++) |std::vectorऔर जंग (प्रोग्रामिंग भाषा) की std::vec::Vec गतिशील सरणियों के कार्यान्वयन हैं, जैसा कि हैं ArrayList[25] जावा (प्रोग्रामिंग भाषा) एपीआई और .NET फ्रेमवर्क के साथ प्रदान की जाने वाली कक्षाएं।[26] सामान्य List<> .NET फ्रेमवर्क के संस्करण 2.0 के साथ आपूर्ति की गई क्लास को डायनेमिक सरणियों के साथ भी लागू किया गया है। स्मॉलटॉक OrderedCollection डायनेमिक स्टार्ट और एंड-इंडेक्स के साथ एक डायनेमिक एरे है, जिससे पहले एलिमेंट को भी O (1) हटा दिया जाता है।

पायथन (प्रोग्रामिंग लैंग्वेज)। list डेटाटाइप कार्यान्वयन एक गतिशील सरणी है जिसका विकास पैटर्न है: 0, 4, 8, 16, 24, 32, 40, 52, 64, 76, ...[27] डेल्फी (प्रोग्रामिंग भाषा) और डी (प्रोग्रामिंग भाषा) भाषा के मूल में गतिशील सरणियों को लागू करते हैं।

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

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

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

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

संदर्भ

  1. ↑ 1.0 1.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.
  2. ↑ 2.0 2.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.
  3. ↑ 3.0 3.1 3.2 "सी++ एसटीएल वेक्टर: परिभाषा, विकास कारक, सदस्य कार्य". Archived from the original on 2015-08-06. Retrieved 2015-08-05.
  4. ↑ "1.5 का वेक्टर विकास कारक". comp.lang.c++.moderated. Google Groups. Archived from the original on 2011-01-22. Retrieved 2015-08-05.
  5. ↑ Cite error: Invalid <ref> tag; no text was provided for refs named java_util_ArrayList
  6. ↑ List object implementation from github.com/python/cpython/, retrieved 2020-03-23.
  7. ↑ Brais, Hadi. "Dissecting the C++ STL Vector: Part 3 - Capacity & Size". Micromysteries. Retrieved 2015-08-05.
  8. ↑ "facebook/folly". GitHub. Retrieved 2015-08-05.
  9. ↑ "rust-lang/rust". GitHub (in English). Retrieved 2020-06-09.
  10. ↑ "golang/go". GitHub. Retrieved 2021-09-14.
  11. ↑ "The Nim memory model". zevv.nl. Retrieved 2022-05-24.
  12. ↑ Day 1 Keynote - Bjarne Stroustrup: C++11 Style at GoingNative 2012 on channel9.msdn.com from minute 45 or foil 44
  13. ↑ Number crunching: Why you should never, ever, EVER use linked-list in your code again at kjellkod.wordpress.com
  14. ↑ 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
  15. ↑ 15.0 15.1 15.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.
  16. ↑ 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
  17. ↑ 17.0 17.1 Sitarski, Edward (September 1996), "HATs: Hashed array trees", Algorithm Alley, Dr. Dobb's Journal, 21 (11)
  18. ↑ Brodnik, Andrej; Carlsson, Svante; Sedgewick, Robert; Munro, JI; Demaine, ED (1999), Resizable Arrays in Optimal Time and Space (PDF) (Technical Report CS-99-09), Department of Computer Science, University of Waterloo
  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)


इस पेज में लापता आंतरिक लिंक की सूची

  • स्मृति प्रबंधन
  • रैंडम एक्सेस
  • ज्यामितीय अनुक्रम
  • सुनहरा अनुपात
  • लिंक्ड सूची
  • संदर्भ का इलाका
  • कैश (कंप्यूटिंग)
  • realloc
  • छोटी बात
  • पायथन (प्रोग्रामिंग भाषा)
  • एडा (प्रोग्रामिंग भाषा)
  • फिसलनदार

बाहरी संबंध

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