गतिशील सरणी

From Vigyanwiki
Revision as of 07:00, 15 December 2022 by alpha>Indicwiki (Created page with "{{Short description|List data structure to which elements can be added/removed}} File:Dynamic array.svg|thumb|ज्यामितीय विस्तार का उप...")
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
ज्यामितीय विस्तार का उपयोग करके गतिशील सरणी के अंत में कई मान डाले गए हैं। ग्रे सेल विस्तार के लिए आरक्षित स्थान का संकेत देते हैं। अधिकांश सम्मिलन तेज़ (निरंतर समय) होते हैं, जबकि कुछ मेमोरी प्रबंधन की आवश्यकता के कारण धीमे होते हैं (Θ(n) समय, कछुओं के साथ लेबल)। अंतिम सरणी का तार्किक आकार और क्षमता दिखाई जाती है।

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

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

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

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

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

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

</वाक्यविन्यास हाइलाइट> चूंकि एन तत्व डाले जाते हैं, क्षमता एक ज्यामितीय प्रगति बनाती है। किसी भी निरंतर अनुपात द्वारा सरणी का विस्तार करना सुनिश्चित करता है कि एन तत्वों को सम्मिलित करने में बिग ओ नोटेशन | ओ (एन) समय समग्र रूप से लगता है, जिसका अर्थ है कि प्रत्येक सम्मिलन परिशोधित विश्लेषण निरंतर समय लेता है। यदि इसका आकार एक निश्चित सीमा से कम हो जाता है, जैसे क्षमता का 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=58238’