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

Revision as of 01:42, 23 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]

विकास कारक

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

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

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

प्रदर्शन

Comparison of list data structures
	Peek (index)	Mutate (insert or delete) at …			Excess space, average
	Peek (index)	Beginning	End	Middle	Excess space, average
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)

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

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

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

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

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

भिन्न

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

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

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

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

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

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

भाषा समर्थन

सी ++std::vector और रस्ट (प्रोग्रामिंग भाषा) std::vec::Vec गतिशील सरणियों के कार्यान्वयन हैं, जैसा कि हैं ^[24] जावा (प्रोग्रामिंग भाषा) API और .NET फ्रेमवर्क के साथ प्रदान की जाने वाली ArrayList कक्षाएं हैं।^[25]

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

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

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

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

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

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

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

संदर्भ

↑ ^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.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.0 ^3.1 ^3.2 "सी++ एसटीएल वेक्टर: परिभाषा, विकास कारक, सदस्य कार्य". Archived from the original on 2015-08-06. Retrieved 2015-08-05.
↑ "1.5 का वेक्टर विकास कारक". comp.lang.c++.moderated. Google Groups. Archived from the original on 2011-01-22. Retrieved 2015-08-05.
↑ Cite error: Invalid <ref> tag; no text was provided for refs named java_util_ArrayList
↑ List object implementation from github.com/python/cpython/, retrieved 2020-03-23.
↑ Brais, Hadi. "Dissecting the C++ STL Vector: Part 3 - Capacity & Size". Micromysteries. Retrieved 2015-08-05.
↑ "facebook/folly". GitHub. Retrieved 2015-08-05.
↑ "rust-lang/rust". GitHub (in English). Retrieved 2020-06-09.
↑ "golang/go". GitHub. Retrieved 2021-09-14.
↑ "The Nim memory model". zevv.nl. Retrieved 2022-05-24.
↑ Day 1 Keynote - Bjarne Stroustrup: C++11 Style at GoingNative 2012 on channel9.msdn.com from minute 45 or foil 44
↑ Number crunching: Why you should never, ever, EVER use linked-list in your code again at kjellkod.wordpress.com
↑ 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.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.
↑ 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.0 ^17.1 Sitarski, Edward (September 1996), "HATs: Hashed array trees", Algorithm Alley, Dr. Dobb's Journal, 21 (11)
↑ Bagwell, Phil (2002), Fast Functional Lists, Hash-Lists, Deques and Variable Length Arrays, EPFL
↑ Mike Lam. "Dynamic Arrays".
↑ "Amortized Time".
↑ "Hashed Array Tree: Efficient representation of Array".
↑ "Different notions of complexity".
↑ Peter Kankowski. "Dynamic arrays in C".
↑ Javadoc on ArrayList
↑ ArrayList Class
↑ listobject.c (github.com)

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

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

बाहरी संबंध

NIST Dictionary of Algorithms and Data Structures: Dynamic array
VPOOL - C language implementation of dynamic array.
CollectionSpy — A Java profiler with explicit support for debugging ArrayList- and Vector-related issues.
Open Data Structures - Chapter 2 - Array-Based Lists, Pat Morin

[gt-ad-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.

[clrs-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.

[:0-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.

[java_util_ArrayList-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

[okasakiComparison-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

[sitarski96-17] 17.0 ^17.1 Sitarski, Edward (September 1996), "HATs: Hashed array trees", Algorithm Alley, Dr. Dobb's Journal, 21 (11)

[18] Bagwell, Phil (2002), Fast Functional Lists, Hash-Lists, Deques and Variable Length Arrays, EPFL

[19] Mike Lam. "Dynamic Arrays".

[20] "Amortized Time".

[21] "Hashed Array Tree: Efficient representation of Array".

[22] "Different notions of complexity".

[23] Peter Kankowski. "Dynamic arrays in C".

[24] Javadoc on ArrayList

[25] ArrayList Class

[26] stobject.c (github.com)

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

[23]

[24]

[25]

[26]

@@ Line 1: / Line 1: @@
 {{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 से क्लास]। </ रेफ>
@@ Line 24: / Line 24: @@
          // a को उसकी वर्तमान क्षमता से दोगुना आकार दें:
          a.क्षमता ← a.क्षमता * 2
-         // (विषयसूची को यहां नए मेमोरी स्थान पर अनुकरण करें)
+         // (विषयसूची को यहां नए स्मृति     स्थान पर अनुकरण करें)
      a [a आकार] ← e
      a.साइज़ ← a.साइज़ + 1
@@ Line 31: / Line 31: @@
 परिशोधित विश्लेषण पढ़ाते समय गतिशील सरणियाँ एक सामान्य उदाहरण हैं।<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"
-!Implementation
+!कार्यान्वयन
-!Growth factor (''a'')
+!विकास कारक (a)
 |-
-|Java ArrayList<ref name="java_util_ArrayList" />
+|जावा ऐरेलिस्ट<ref name="java_util_ArrayList" />
 |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))
 |-
-|[[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)
 |-
@@ Line 49: / Line 50: @@
 |2
 |-
-|[[Clang]] 3.6<ref name=":0" />
+|[[Clang|क्लैंग]] 3.6<ref name=":0" />
 |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)
 |-
-|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
 |-
-|[[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
 |}
 == प्रदर्शन ==
@@ Line 71: / Line 71: @@
 तत्वों को जोड़ने और हटाने के लिए नए कार्यों को जोड़ने के साथ गतिशील सरणी में एक सरणी के समान प्रदर्शन होता है:
-* किसी विशेष इंडेक्स (निरंतर समय) पर मूल्य प्राप्त करना या सेट करना
+* किसी विशेष अनुक्रमणिका (निरंतर समय) पर मूल्य प्राप्त करना या समुच्चयन करना
 * क्रम में तत्वों पर ध्यान देना (रैखिक समय, अच्छा कैश प्रदर्शन)
 * सरणी के बीच में एक तत्व सम्मिलित करना या हटाना (रैखिक समय)
 * सरणी के अंत में एक तत्व सम्मिलित करना या हटाना (निरंतर परिशोधन समय)
-संदर्भ और [[डेटा कैश]] उपयोग, कॉम्पैक्टनेस (कम मेमोरी उपयोग), और यादृच्छिक पहुंच सहित सरणियों के कई लाभों से डायनेमिक सरणियाँ लाभान्वित होती हैं। आकार और क्षमता के बारे में जानकारी संग्रहीत करने के लिए उनके पास सामान्यतया   पर केवल एक छोटा निश्चित अतिरिक्त ओवरहेड होता है। यह गतिशील सरणियों को कैशे (कंप्यूटिंग)-अनुकूल [[डेटा संरचना]] के निर्माण के लिए एक आकर्षक उपकरण बनाता है। हालाँकि, पायथन या जावा जैसी भाषाओं में जो संदर्भ शब्दार्थ को लागू करते हैं, गतिशील सरणी आम तौर पर वास्तविक डेटा को संग्रहीत नहीं करेगी, बल्कि यह स्मृति के अन्य क्षेत्रों में रहने वाले डेटा के [[संदर्भ (कंप्यूटर विज्ञान)]] को संग्रहीत करेगी। इस मामले में, सरणी में वस्तुओं तक क्रमिक रूप से पहुंचने में वास्तव में मेमोरी के कई गैर-सन्निहित क्षेत्रों तक पहुंच सम्मिलित   होगी, इसलिए इस डेटा संरचना के कैश-मित्रता के कई फायदे खो गए हैं।
+संदर्भ और [[डेटा कैश]] उपयोग, कॉम्पैक्टनेस (कम स्मृति उपयोग), और यादृच्छिक पहुंच सहित सरणियों के कई लाभों से गतिशील सरणियाँ लाभान्वित होती हैं। आकार और क्षमता के बारे में जानकारी संग्रहीत करने के लिए उनके पास सामान्यतया पर केवल एक छोटा निश्चित अतिरिक्त उपरिव्यय होता है। यह गतिशील सरणियों को कैश-अनुकूल [[डेटा संरचना]] के निर्माण के लिए एक आकर्षक उपकरण बनाता है। तथापि, पायथन या जावा जैसी भाषाओं में जो संदर्भ शब्दार्थ को प्रवर्तित करते हैं, गतिशील सरणी साधारणतयः पर वास्तविक तथ्य को संग्रहीत नहीं करेगी, बल्कि यह स्मृति के अन्य क्षेत्रों में रहने वाले डेटा के [[संदर्भ (कंप्यूटर विज्ञान)]] को संग्रहीत करेगा। इस मामले में, सरणी में वस्तुओं तक क्रमिक रूप से पहुंचने में वास्तव में स्मृति     के कई गैर-सन्निहित क्षेत्रों तक पहुंच सम्मिलित होगी, इसलिए इस डेटा संरचना के कैश-मित्रता के कई फायदे लुप्त हो गए हैं।
-लिंक की गई सूचियों की तुलना में, गतिशील सरणियों में तेजी से अनुक्रमण (निरंतर समय बनाम रैखिक समय) होता है और संदर्भ के बेहतर इलाके के कारण सामान्यतया   पर तेजी से पुनरावृत्ति होती है; हालाँकि, डायनेमिक सरणियों को मनमाने स्थान पर सम्मिलित करने या हटाने के लिए रैखिक समय की आवश्यकता होती है, क्योंकि निम्नलिखित सभी तत्वों को स्थानांतरित किया जाना चाहिए, जबकि लिंक्ड सूचियाँ निरंतर समय में ऐसा कर सकती हैं। इस नुकसान को [[गैप बफर]] और टियर वेक्टर वेरिएंट द्वारा कम किया गया है, जिसकी चर्चा नीचे वेरिएंट के तहत की गई है। इसके अलावा, एक अत्यधिक [[विखंडन (कंप्यूटर)]] मेमोरी क्षेत्र में, एक बड़े गतिशील सरणी के लिए सन्निहित स्थान खोजना महंगा या असंभव हो सकता है, जबकि लिंक्ड सूचियों को संपूर्ण डेटा संरचना को सन्निहित रूप से संग्रहीत करने की आवश्यकता नहीं होती है।
+श्रृंखलित की गई सूचियों की तुलना में, गतिशील सरणियों में तेजी से अनुक्रमण (निरंतर समय बनाम रैखिक समय) होता है और संदर्भ के बेहतर स्थान के कारण सामान्यतया पर तेजी से पुनरावृत्ति होती है; हालाँकि, गतिशील सरणियों को अव्यवस्थिततः स्थान पर सम्मिलित करने या हटाने के लिए रैखिक समय की आवश्यकता होती है, क्योंकि निम्नलिखित सभी तत्वों को स्थानांतरित किया जाना चाहिए, जबकि श्रृंखलित सूचियाँ निरंतर समय में ऐसा कर सकती हैं। इस असुविधा को [[गैप बफर]] और स्तरीय सदिश भिन्न द्वारा कम किया गया है, जिसकी चर्चा नीचे भिन्न के तहत की गई है। इसके अलावा, एक अत्यधिक खंडित स्मृति क्षेत्र में, एक बड़े गतिशील सरणी के लिए सन्निहित स्थान खोजना महंगा या असंभव हो सकता है, जबकि श्रृंखलित सूचियों को संपूर्ण डेटा संरचना को सन्निहित रूप से संग्रहीत करने की आवश्यकता नहीं होती है।
-एक [[सेल्फ-बैलेंसिंग बाइनरी सर्च ट्री]] डायनेमिक सरणियों और लिंक्ड सूचियों दोनों के सभी संचालन को यथोचित कुशलता से प्रदान करते हुए एक सूची को संग्रहीत कर सकता है, लेकिन अंत में सम्मिलन और सूची में पुनरावृत्ति दोनों एक गतिशील सरणी की तुलना में धीमी हैं, सिद्धांत और व्यवहार में, गैर-सन्निहित भंडारण और ट्री ट्रैवर्सल/मैनिपुलेशन ओवरहेड के कारण।
+एक संतुलित वृक्ष गतिशील सरणियों और श्रृंखलित सूचियों दोनों के सभी संचालन को यथोचित कुशलता से प्रदान करते हुए एक सूची को संग्रहीत कर सकता है, लेकिन अंत में सम्मिलन और सूची में पुनरावृत्ति दोनों एक गतिशील सरणी की तुलना में धीमी होती है, सिद्धांत और व्यवहार में, गैर के कारण - असन्निकट भंडारण के कारण और ट्री ट्रैवर्सल/हस्तोपचार उपरि।
-== वेरिएंट ==
+== भिन्न   ==
-गैप बफ़र डायनेमिक सरणियों के समान हैं, लेकिन एक ही मनमाने स्थान के पास कुशल सम्मिलन और विलोपन संचालन की अनुमति देते हैं। कुछ [[इसलिए]] कार्यान्वयन 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) परिशोधित प्रदर्शन होता है।
-के एक पेपर में,<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> स्थान, और वे यह दिखाते हुए एक निचली सीमा साबित करते हैं कि किसी भी गतिशील सरणी को इतना स्थान बर्बाद करना होगा यदि संचालन को स्थिर समय रहना है। इसके अतिरिक्त, वे एक संस्करण प्रस्तुत करते हैं जहां बफर के बढ़ने और सिकुड़ने से न केवल परिशोधन होता है, बल्कि सबसे खराब समय भी होता है।
+एक स्तरीय गतिशील सरणी डेटा संरचना, जो समय पर किसी भी बिंदु पर 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.
 [https://w3.cs.jmu.edu/lam2mo/cs240_2015_08/files/04-dyn_arrays.pdf "Dynamic Arrays"].
@@ Line 103: / Line 103: @@
 [https://people.ksp.sk/~kuko/gnarley-trees/Complexity2.html "Different notions of complexity"].
 </ref>
-रैखिक रूप से बढ़ने वाली सरणियाँ पूर्व-आवंटन (अपशिष्ट) Θ (1) स्थान हर बार जब वे सरणी को फिर से आकार देती हैं, तो उन्हें भोले आकार देने योग्य सरणियों की तुलना में कई गुना तेज बना देती हैं - सरणी के अंत में संलग्न होने में अभी भी Θ (n) समय लगता है लेकिन साथ बहुत छोटा स्थिरांक।
+रैखिक रूप से बढ़ने वाली सरणियाँ पूर्व-आवंटन (अपशिष्ट) Θ (1) स्थान हर बार जब वे सरणी को फिर से आकार देती हैं, तो उन्हें भोले आकार देने योग्य सरणियों की तुलना में कई गुना तेज बना देती हैं - सरणी के अंत में संलग्न होने में अभी भी Θ (n) समय लगता है लेकिन बहुत छोटे स्थिरांक के साथ।
-भोले आकार बदलने योग्य सरणियाँ और रैखिक रूप से बढ़ने वाली सरणियाँ तब उपयोगी हो सकती हैं जब अंतरिक्ष-बाधित अनुप्रयोग को बहुत से छोटे आकार बदलने योग्य सरणियों की आवश्यकता होती है;
+सरल आकार बदलने योग्य सरणियाँ और रैखिक रूप से बढ़ने वाली सरणियाँ तब उपयोगी हो सकती हैं जब अंतरिक्ष-बाधित अनुप्रयोग को बहुत से सूक्ष्म  आकार बदलने योग्य सरणियों की आवश्यकता होती है;
-वे सामान्यतया   पर एक शैक्षिक उदाहरण के रूप में भी उपयोग किए जाते हैं जो तेजी से बढ़ते गतिशील सरणियों के लिए अग्रणी होते हैं।<ref>
+वे सामान्यतया पर एक शैक्षिक उदाहरण के रूप में भी उपयोग किए जाते हैं जो तेजी से बढ़ते गतिशील सरणियों के लिए अग्रणी होते हैं।<ref>
 Peter Kankowski.
 [https://www.strchr.com/dynamic_arrays "Dynamic arrays in C"].
@@ Line 111: / Line 111: @@
 == भाषा समर्थन ==
-[[सी ++]] का वेक्टर (सी ++) |<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) हटा दिया जाता है।
+[[सी ++|सी ++<code>std::vector</code>]]  और रस्ट  [[जंग (प्रोग्रामिंग भाषा)|(प्रोग्रामिंग भाषा)]] <code>std::vec::Vec</code> गतिशील सरणियों के कार्यान्वयन हैं, जैसा कि हैं <ref>Javadoc on {{Javadoc:SE|java/util|ArrayList}}</ref> [[जावा (प्रोग्रामिंग भाषा)]] API और .NET फ्रेमवर्क के साथ प्रदान की जाने वाली ArrayList कक्षाएं हैं।<ref>[https://msdn.microsoft.com/en-us/library/system.collections.arraylist ArrayList Class]</ref>
+.NET फ्रेमवर्क के संस्करण 2.0 के साथ आपूर्ति की गई सामान्य सूची <> वर्ग को गतिशील सरणियों के साथ भी लागू किया गया है। स्मॉलटॉक का आदेशित संग्रह गतिशील आरम्भ और अंत-सूचकांक के साथ एक गतिशील सरणियों है, जिससे पहले घटक को भी 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>Ada.Containers.Vectors</code>सामान्य संवेष्टन किसी दिए गए उपप्रकार के लिए गतिशील सरणी कार्यान्वयन प्रदान करता है।
-[[पर्ल]] और रूबी_(प्रोग्रामिंग_लैंग्वेज) जैसी कई स्क्रिप्टिंग भाषाएं बिल्ट-इन [[आदिम डेटा प्रकार]] के रूप में गतिशील सरणियाँ प्रदान करती हैं।
+[[पर्ल]] और रूबी_(प्रोग्रामिंग_लैंग्वेज) जैसी कई स्क्रिप्टिंग भाषाएं में निर्मित [[आदिम डेटा प्रकार]] के रूप में गतिशील सरणियाँ प्रदान करती हैं।
-कई क्रॉस-प्लेटफ़ॉर्म ढांचे [[सी (प्रोग्रामिंग भाषा)]] के लिए गतिशील सरणी कार्यान्वयन प्रदान करते हैं, जिनमें सम्मिलित   हैं <code>CFArray</code> तथा <code>CFMutableArray</code> [[कोर फाउंडेशन]] में, और <code>GArray</code> तथा <code>GPtrArray</code> जीएलआईबी में।
+कई क्रॉस-प्लेटफ़ॉर्म ढांचे [[सी (प्रोग्रामिंग भाषा)|C (प्रोग्रामिंग भाषा)]] के लिए गतिशील सरणी कार्यान्वयन प्रदान करते हैं, जिनमें सम्मिलित  हैं <code>CFArray</code> तथा <code>CFMutableArray</code> [[कोर फाउंडेशन]] में, और <code>GArray</code> तथा <code>GPtrArray</code>GLib.में।
-[[सामान्य लिस्प]] बिल्ट-इन को कॉन्फ़िगर करने की अनुमति देकर आकार बदलने योग्य वैक्टर के लिए प्राथमिक समर्थन प्रदान करता है <code>array</code> समायोज्य के रूप में टाइप करें और भरण-सूचक द्वारा सम्मिलन का स्थान।
+[[सामान्य लिस्प]] अंतर्निर्मित सरणी समायोज्य के रूप में और फिल-पॉइंटर द्वारा निवेशन के स्थान को समनुरूप करने की अनुमति देकर आकार बदलने योग्य वैक्टर के लिए एक अल्पविकसित समर्थन प्रदान करता है।
 == संदर्भ ==
@@ Line 134: / Line 138: @@
 *ज्यामितीय अनुक्रम
 *सुनहरा अनुपात
-*लिंक्ड सूची
+*श्रृंखलित    सूची
 *संदर्भ का इलाका
 *कैश (कंप्यूटिंग)

v t e Well-known data structures
Types	Collection Container
Abstract	Associative array Multimap Retrieval Data Structure List Stack Queue Double-ended queue Priority queue Double-ended priority queue Set Multiset Disjoint-set
Arrays	Bit array Circular buffer Dynamic array Hash table Hashed array tree Sparse matrix
Linked	Association list Linked list Skip list Unrolled linked list XOR linked list
Trees	B-tree Binary search tree AA tree AVL tree Red–black tree Self-balancing tree Splay tree Heap Binary heap Binomial heap Fibonacci heap R-tree R* tree R+ tree Hilbert R-tree Trie Hash tree
Graphs	Binary decision diagram Directed acyclic graph Directed acyclic word graph
List of data structures

Anonymous

Search

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

Namespaces

More

Page actions

Revision as of 01:42, 23 December 2022

Contents

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

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

विकास कारक

प्रदर्शन

भिन्न

भाषा समर्थन

संदर्भ

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

बाहरी संबंध

Navigation

Navigation

Wiki tools

Wiki tools

Anonymous

Search

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

Revision as of 01:42, 23 December 2022

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

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

विकास कारक

प्रदर्शन

भिन्न

भाषा समर्थन

संदर्भ

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

बाहरी संबंध

Navigation

Wiki tools

Page tools

Other projects

Categories