एसोसिएशन सूची: Difference between revisions

From Vigyanwiki
(Created page with "{{Infobox data structure |name=Association list |type=associative array |invented_by= |invented_year= |space_avg=O(''n'') |space_worst=O(''n'') |search_avg=O(''n'') |searc...")
 
No edit summary
 
(4 intermediate revisions by 3 users not shown)
Line 14: Line 14:
}}
}}


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


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


यह जांचने के लिए कि क्या कोई कुंजी किसी दिए गए एसोसिएशन सूची में किसी मान से जुड़ी हुई है, सूची को उसके पहले नोड से शुरू करके तब तक खोजें जब तक कि कुंजी वाला नोड नहीं मिल जाता या जब तक खोज सूची के अंत तक नहीं पहुंच जाती (जिस स्थिति में कुंजी मौजूद नहीं है)।
एक एसोसिएशन सूची में किसी कुंजी के साथ मूल्य का संबंध है या नहीं, इसे जाँचने के लिए सूची के पहले तत्व से सर्च प्रारंभ करें और पुनः तत्व मिल जाने तक या सूची के अंत तक सर्च जारी रखें। एक एसोसिएशन सूची में नई कुंजी-मूल्य युग्म जोड़ने के लिए, उस कुंजी-मूल्य युग्म के लिए एक नया नोड बनाएं, नोड के लिंक को एसोसिएशन सूची के पिछले प्रथम तत्व के साथ सेट करें, और एसोसिएशन सूची का प्रथम तत्व नए नोड से बदल दें। ज्यादातर एसोसिएशन सूची के अनुमानित कार्यनीतियाँ एक्सपेक्टेड विधि से काम करती हैं, परंतु  कुंजी के साथ एक ही तत्व के अनुक्रम में अनुशासन करने की अनुमति नहीं देतीं हैं, सूची के बाद के डुप्लिकेट कुंजी-मूल्य युग्म  इस सर्च एल्गोरिदम के लिए कोई समस्या नहीं बनाते हैं।<ref name="pwc">{{cite book|title=Programming with Constraints: An Introduction|first1=Kim|last1=Marriott|first2=Peter J.|last2=Stuckey|publisher=MIT Press|year=1998|isbn=9780262133418|pages=193–195|url=https://books.google.com/books?id=jBYAleHTldsC&pg=PA193}}</ref>
एसोसिएशन सूची में एक नई कुंजी-मूल्य जोड़ी जोड़ने के लिए, उस कुंजी-मूल्य जोड़ी के लिए एक नया नोड बनाएं, नोड के लिंक को एसोसिएशन सूची के पिछले पहले तत्व के रूप में सेट करें, और एसोसिएशन सूची के पहले तत्व को नए नोड से बदलें।<ref name="pwc">{{cite book|title=Programming with Constraints: An Introduction|first1=Kim|last1=Marriott|first2=Peter J.|last2=Stuckey|publisher=MIT Press|year=1998|isbn=9780262133418|pages=193–195|url=https://books.google.com/books?id=jBYAleHTldsC&pg=PA193}}</ref> हालाँकि एसोसिएशन सूचियों के कुछ कार्यान्वयन एक-दूसरे के समान कुंजियों के साथ कई नोड्स रखने की अनुमति नहीं देते हैं, इस खोज एल्गोरिदम के लिए ऐसे दोहराव समस्याग्रस्त नहीं हैं: सूची में बाद में दिखाई देने वाली डुप्लिकेट कुंजियों को अनदेखा कर दिया जाता है।<ref>{{cite book|title=तर्क और सूचना का संगठन|first=Martin|last=Frické|publisher=Springer|year=2012|isbn=9781461430872|pages=44–45|contribution-url=https://books.google.com/books?id=HnAmoLBcilIC&pg=PA44|contribution=2.8.3 Association Lists}}</ref>
 
कुंजी की प्रत्येक घटना का पता लगाने के लिए सूची को स्कैन करके और कुंजी वाले नोड्स को सूची से बाहर करके, एसोसिएशन सूची से एक कुंजी को हटाना भी संभव है।<ref name="pwc"/>स्कैन सूची के अंत तक जारी रहना चाहिए, भले ही कुंजी मिल जाए, यदि एक ही कुंजी कई बार डाली गई हो।
एक एसोसिएशन सूची से कुंजी को हटाना भी संभव है, इसके लिए सूची के प्रत्येक घटना को सर्च और सूची से कुंजी वाले नोड को हटाने के लिए अनुमति दी जाती है। स्कैन सूची के अंत तक जारी रहना चाहिए, भले ही कुंजी मिल जाए, इसका अर्थ यह है कि एक ही कुंजी को कई बार सूची में डाला जा सकता है।


==प्रदर्शन==
==प्रदर्शन==
एसोसिएशन सूचियों का नुकसान यह है कि इसमें खोजने का समय लगता है {{math|[[Big O notation|''O''(''n'')]]}}, कहाँ {{mvar|n}} सूची की लंबाई है.<ref>{{cite book|first=Donald|last=Knuth|author-link=Donald Knuth|contribution=6.1 Sequential Searching|title=[[The Art of Computer Programming]], Vol. 3: Sorting and Searching|pages=396–405|publisher=Addison Wesley|edition=2nd|isbn=0-201-89685-0}}</ref> बड़ी सूचियों के लिए, यह उस समय की तुलना में बहुत धीमा हो सकता है जो एक सहयोगी सरणी को [[बाइनरी सर्च ट्री]] या [[हैश तालिका]] के रूप में प्रस्तुत करके प्राप्त किया जा सकता है।
एसोसिएशन सूचियों का हानि यह है कि इसमें सर्च का समय {{math|[[Big O notation|''O''(''n'')]]}} लगता है, जहाँ {{mvar|n}} सूची की लंबाई है। <ref>{{cite book|first=Donald|last=Knuth|author-link=Donald Knuth|contribution=6.1 Sequential Searching|title=[[The Art of Computer Programming]], Vol. 3: Sorting and Searching|pages=396–405|publisher=Addison Wesley|edition=2nd|isbn=0-201-89685-0}}</ref> बड़ी सूचियों के लिए, यह उस समय की तुलना में बहुत धीमा हो सकता है जो एक सहयोगी सरणी को [[बाइनरी सर्च ट्री]] या [[हैश तालिका]] के रूप में प्रस्तुत करके प्राप्त किया जा सकता है। इसके अतिरिक्त, जब तक डुप्लिकेट कुंजियों वाले तत्वों को हटाने के लिए सूची को नियमित रूप से नहीं काटा जाता है, तब तक एक ही कुंजी से जुड़े कई मान सूची के आकार को बढ़ा देंगे, और इस प्रकार बिना कोई प्रतिपूरक लाभ प्रदान किए सर्च करने का समय बढ़ जाता है।
इसके अतिरिक्त, जब तक डुप्लिकेट कुंजियों वाले तत्वों को हटाने के लिए सूची को नियमित रूप से नहीं काटा जाता है, तब तक एक ही कुंजी से जुड़े कई मान सूची के आकार को बढ़ा देंगे, और इस प्रकार बिना कोई प्रतिपूरक लाभ प्रदान किए खोज करने का समय बढ़ जाएगा।


एसोसिएशन सूचियों का एक फायदा यह है कि निरंतर समय में एक नया तत्व जोड़ा जा सकता है। इसके अतिरिक्त, जब कुंजियों की संख्या बहुत कम होती है, तो उनके कार्यान्वयन की अधिक सरलता के कारण, बाइनरी सर्च ट्री या हैश तालिका की खोज करने की तुलना में एसोसिएशन सूची खोजना अधिक कुशल हो सकता है।<ref>{{cite book|title=Microsoft .NET में संग्रह के लिए डेवलपर की मार्गदर्शिका|first=Calvin|last=Janes|publisher=Pearson Education|year=2011|isbn=9780735665279|page=191|contribution-url=https://books.google.com/books?id=-KdCAwAAQBAJ&pg=PT191|contribution=Using Association Lists for Associative Arrays}}</ref>
एसोसिएशन सूचियों का एक लाभ यह है कि निरंतर समय में एक नया तत्व जोड़ा जा सकता है। इसके अतिरिक्त, जब कुंजियों की संख्या बहुत कम होती है, तो उनके कार्यान्वयन की अधिक सरलता के कारण, बाइनरी सर्च ट्री या हैश तालिका की सर्च करने की तुलना में एसोसिएशन सूची सर्चना अधिक कुशल हो सकता है।<ref>{{cite book|title=Microsoft .NET में संग्रह के लिए डेवलपर की मार्गदर्शिका|first=Calvin|last=Janes|publisher=Pearson Education|year=2011|isbn=9780735665279|page=191|contribution-url=https://books.google.com/books?id=-KdCAwAAQBAJ&pg=PT191|contribution=Using Association Lists for Associative Arrays}}</ref>




==अनुप्रयोग और सॉफ्टवेयर लाइब्रेरी==
==अनुप्रयोग और सॉफ्टवेयर लाइब्रेरी==
लिस्प के शुरुआती विकास में, प्रक्रियाओं में [[मुक्त चर और बाध्य चर]] के संदर्भों को हल करने के लिए एसोसिएशन सूचियों का उपयोग किया गया था।<ref name="mccarthy_lisp_1.5">{{cite book | url = https://archive.org/details/lisp15programmer00john | title = एलआईएसपी 1.5 प्रोग्रामर मैनुअल| publisher = [[MIT Press]] | first1 = John | last1 = McCarthy | first2 = Paul W. | last2 = Abrahams | first3 = Daniel J. | last3 = Edwards | first4 = Timothy P. | last4 = Hart | first5 = Michael I. | last5 = Levin | isbn = 0-262-13011-4 | year = 1985 | url-access = registration }} विशेष रूप से पी देखें। 12 उन फ़ंक्शंस के लिए जो एसोसिएशन सूची खोजते हैं और किसी अन्य अभिव्यक्ति में प्रतीकों को प्रतिस्थापित करने के लिए इसका उपयोग करते हैं, और पी। वैरिएबल बाइंडिंग को बनाए रखने में एसोसिएशन सूचियों के अनुप्रयोग के लिए 103।</ref><ref>{{cite book|title=कंप्यूटिंग क्या है?|series=Monographs in Computer Science|first=Jan L. A.|last=van de Snepscheut|publisher=Springer|year=1993|isbn=9781461227106|page=201|url=https://books.google.com/books?id=VXPrBwAAQBAJ&pg=PA201}}</ref> इस एप्लिकेशन में, एक अतिरिक्त ऑपरेशन के साथ एसोसिएशन सूचियों को बढ़ाना सुविधाजनक है, जो उसी कुंजी की अन्य प्रतियों के लिए सूची को स्कैन किए बिना कुंजी-मूल्य जोड़ी के जोड़ को उलट देता है। इस तरह, एसोसिएशन सूची एक स्टैक (अमूर्त डेटा प्रकार) के रूप में कार्य कर सकती है, जो [[स्थानीय चर]] को उन अन्य चर के मूल्यों को नष्ट किए बिना, समान नाम वाले अन्य चर को अस्थायी रूप से छाया देने की अनुमति देती है।<ref>{{cite book|title=प्रोग्रामिंग भाषा व्यावहारिकता|first=Michael Lee|last=Scott|publisher=Morgan Kaufmann|year=2000|isbn=9781558604421|page=137|contribution-url=https://books.google.com/books?id=To3xpkvkPvMC&pg=PA137|contribution=3.3.4 Association Lists and Central Reference Tables}}</ref>
लिस्प के प्रारंभिक विकास में, प्रक्रियाओं में मुक्त चर के संदर्भों को हल करने के लिए एसोसिएशन सूचियों का उपयोग किया गया था<ref name="mccarthy_lisp_1.5">{{cite book | url = https://archive.org/details/lisp15programmer00john | title = एलआईएसपी 1.5 प्रोग्रामर मैनुअल| publisher = [[MIT Press]] | first1 = John | last1 = McCarthy | first2 = Paul W. | last2 = Abrahams | first3 = Daniel J. | last3 = Edwards | first4 = Timothy P. | last4 = Hart | first5 = Michael I. | last5 = Levin | isbn = 0-262-13011-4 | year = 1985 | url-access = registration }} विशेष रूप से पी देखें। 12 उन फ़ंक्शंस के लिए जो एसोसिएशन सूची खोजते हैं और किसी अन्य अभिव्यक्ति में प्रतीकों को प्रतिस्थापित करने के लिए इसका उपयोग करते हैं, और पी। वैरिएबल बाइंडिंग को बनाए रखने में एसोसिएशन सूचियों के अनुप्रयोग के लिए 103।</ref><ref>{{cite book|title=कंप्यूटिंग क्या है?|series=Monographs in Computer Science|first=Jan L. A.|last=van de Snepscheut|publisher=Springer|year=1993|isbn=9781461227106|page=201|url=https://books.google.com/books?id=VXPrBwAAQBAJ&pg=PA201}}</ref> इस एप्लिकेशन में, एक अतिरिक्त ऑपरेशन के साथ एसोसिएशन सूचियों को बढ़ाना सुविधाजनक है, जो उसी कुंजी की अन्य प्रतियों के लिए सूची को स्कैन किए बिना कुंजी-मूल्य जोड़ी के जोड़ को उलट देता है। इस तरह, एसोसिएशन सूची एक स्टैक के रूप में कार्य कर सकती है, जो [[स्थानीय चर]] को उन अन्य चर के मूल्यों को नष्ट किए बिना, समान नाम वाले अन्य चर को अस्थायी रूप से छायांकित करने की अनुमति देते है।<ref>{{cite book|title=प्रोग्रामिंग भाषा व्यावहारिकता|first=Michael Lee|last=Scott|publisher=Morgan Kaufmann|year=2000|isbn=9781558604421|page=137|contribution-url=https://books.google.com/books?id=To3xpkvkPvMC&pg=PA137|contribution=3.3.4 Association Lists and Central Reference Tables}}</ref>
सहित कई प्रोग्रामिंग भाषाएँ
 
लिस्प,<ref name="mccarthy_lisp_1.5"/>[[योजना (प्रोग्रामिंग भाषा)]],<ref>{{cite book|title=योजना में प्रोग्रामिंग और मेटा-प्रोग्रामिंग|series=Undergraduate Texts in Computer Science|first=Jon|last=Pearce|publisher=Springer|year=2012|isbn=9781461216827|page=214|url=https://books.google.com/books?id=uDzaBwAAQBAJ&pg=PA214}}</ref>
सहित कई प्रोग्रामिंग भाषाएँ लिस्प,<ref name="mccarthy_lisp_1.5" />[[योजना (प्रोग्रामिंग भाषा)|योजना]],<ref>{{cite book|title=योजना में प्रोग्रामिंग और मेटा-प्रोग्रामिंग|series=Undergraduate Texts in Computer Science|first=Jon|last=Pearce|publisher=Springer|year=2012|isbn=9781461216827|page=214|url=https://books.google.com/books?id=uDzaBwAAQBAJ&pg=PA214}}</ref>[[ओकैमल]],<ref>{{cite book|title=Real World OCaml: Functional Programming for the Masses|first1=Yaron|last1=Minsky|first2=Anil|last2=Madhavapeddy|first3=Jason|last3=Hickey|publisher=O'Reilly Media|year=2013|isbn=9781449324766|page=253|url=https://books.google.com/books?id=nabtAQAAQBAJ&pg=PA253}}</ref> और [[हास्केल (प्रोग्रामिंग भाषा)|हास्केल]] <ref>{{cite book|title=Real World Haskell: Code You Can Believe In|first1=Bryan|last1=O'Sullivan|first2=John|last2=Goerzen|first3=Donald Bruce|last3=Stewart|publisher=O'Reilly Media|year=2008|isbn=9780596554309|page=299|url=https://books.google.com/books?id=nh0okI1a1sQC&pg=PA299}}</ref> उनके मानक पुस्तकालयों में संबंधीय सूचियों को हैंडल करने के लिए फ़ंक्शन्स या उपकरण प्रदान करती हैं।
[[ओकैमल]],<ref>{{cite book|title=Real World OCaml: Functional Programming for the Masses|first1=Yaron|last1=Minsky|first2=Anil|last2=Madhavapeddy|first3=Jason|last3=Hickey|publisher=O'Reilly Media|year=2013|isbn=9781449324766|page=253|url=https://books.google.com/books?id=nabtAQAAQBAJ&pg=PA253}}</ref> और
[[हास्केल (प्रोग्रामिंग भाषा)]]<ref>{{cite book|title=Real World Haskell: Code You Can Believe In|first1=Bryan|last1=O'Sullivan|first2=John|last2=Goerzen|first3=Donald Bruce|last3=Stewart|publisher=O'Reilly Media|year=2008|isbn=9780596554309|page=299|url=https://books.google.com/books?id=nh0okI1a1sQC&pg=PA299}}</ref> उनके [[मानक पुस्तकालय]] में एसोसिएशन सूचियों को संभालने के लिए कार्य हैं।


==यह भी देखें==
==यह भी देखें==
*स्व-व्यवस्थित सूची, बार-बार एक्सेस की जाने वाली कुंजियों की खोज को तेज़ करने के लिए एसोसिएशन सूची में कुंजियों को फिर से व्यवस्थित करने की एक रणनीति
*स्व-व्यवस्थित सूची, बार-बार एक्सेस की जाने वाली कुंजियों की सर्च को तेज़ करने के लिए एसोसिएशन सूची में कुंजियों को पुनः व्यवस्थित करने की एक रणनीति।
*[[संपत्ति सूची]], या प्लिस्ट, लिस्प में प्रयुक्त एक अन्य सहयोगी सरणी प्रारूप।<ref>{{cite web|url=https://www.cs.cmu.edu/Groups/AI/html/cltl/clm/node108.html|title=10.1. संपत्ति सूची|website=Cs.cmu.edu|accessdate=29 September 2017}}</ref>
*[[संपत्ति सूची|प्रॉपर्टी सूची]], या प्लिस्ट, लिस्प में प्रयुक्त एक अन्य सहयोगी सरणी प्रारूप।<ref>{{cite web|url=https://www.cs.cmu.edu/Groups/AI/html/cltl/clm/node108.html|title=10.1. संपत्ति सूची|website=Cs.cmu.edu|accessdate=29 September 2017}}</ref>




Line 46: Line 43:


{{Data structures}}
{{Data structures}}
[[Category: लिंक की गई सूचियाँ]] [[Category: सहयोगी सरणियाँ]]


[[Category: Machine Translated Page]]
[[Category:Collapse templates]]
[[Category:Created On 25/07/2023]]
[[Category:Created On 25/07/2023]]
[[Category:Machine Translated Page]]
[[Category:Navigational boxes| ]]
[[Category:Navigational boxes without horizontal lists]]
[[Category:Pages with script errors]]
[[Category:Sidebars with styles needing conversion]]
[[Category:Template documentation pages|Documentation/doc]]
[[Category:Templates Vigyan Ready]]
[[Category:Templates generating microformats]]
[[Category:Templates that are not mobile friendly]]
[[Category:Templates using TemplateData]]
[[Category:Wikipedia metatemplates]]
[[Category:लिंक की गई सूचियाँ]]
[[Category:सहयोगी सरणियाँ]]

Latest revision as of 10:30, 11 August 2023

Association list
Typeassociative array
Time complexity in big O notation
Algorithm Average Worst case
Space O(n) O(n)
Search O(n) O(n)
Insert O(1) O(1)
Delete O(n) O(n)

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

संचालन

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

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

एक एसोसिएशन सूची से कुंजी को हटाना भी संभव है, इसके लिए सूची के प्रत्येक घटना को सर्च और सूची से कुंजी वाले नोड को हटाने के लिए अनुमति दी जाती है। स्कैन सूची के अंत तक जारी रहना चाहिए, भले ही कुंजी मिल जाए, इसका अर्थ यह है कि एक ही कुंजी को कई बार सूची में डाला जा सकता है।

प्रदर्शन

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

एसोसिएशन सूचियों का एक लाभ यह है कि निरंतर समय में एक नया तत्व जोड़ा जा सकता है। इसके अतिरिक्त, जब कुंजियों की संख्या बहुत कम होती है, तो उनके कार्यान्वयन की अधिक सरलता के कारण, बाइनरी सर्च ट्री या हैश तालिका की सर्च करने की तुलना में एसोसिएशन सूची सर्चना अधिक कुशल हो सकता है।[3]


अनुप्रयोग और सॉफ्टवेयर लाइब्रेरी

लिस्प के प्रारंभिक विकास में, प्रक्रियाओं में मुक्त चर के संदर्भों को हल करने के लिए एसोसिएशन सूचियों का उपयोग किया गया था[4][5] इस एप्लिकेशन में, एक अतिरिक्त ऑपरेशन के साथ एसोसिएशन सूचियों को बढ़ाना सुविधाजनक है, जो उसी कुंजी की अन्य प्रतियों के लिए सूची को स्कैन किए बिना कुंजी-मूल्य जोड़ी के जोड़ को उलट देता है। इस तरह, एसोसिएशन सूची एक स्टैक के रूप में कार्य कर सकती है, जो स्थानीय चर को उन अन्य चर के मूल्यों को नष्ट किए बिना, समान नाम वाले अन्य चर को अस्थायी रूप से छायांकित करने की अनुमति देते है।[6]

सहित कई प्रोग्रामिंग भाषाएँ लिस्प,[4]योजना,[7]ओकैमल,[8] और हास्केल [9] उनके मानक पुस्तकालयों में संबंधीय सूचियों को हैंडल करने के लिए फ़ंक्शन्स या उपकरण प्रदान करती हैं।

यह भी देखें

  • स्व-व्यवस्थित सूची, बार-बार एक्सेस की जाने वाली कुंजियों की सर्च को तेज़ करने के लिए एसोसिएशन सूची में कुंजियों को पुनः व्यवस्थित करने की एक रणनीति।
  • प्रॉपर्टी सूची, या प्लिस्ट, लिस्प में प्रयुक्त एक अन्य सहयोगी सरणी प्रारूप।[10]


संदर्भ

  1. ↑ Marriott, Kim; Stuckey, Peter J. (1998). Programming with Constraints: An Introduction. MIT Press. pp. 193–195. ISBN 9780262133418.
  2. ↑ Knuth, Donald. "6.1 Sequential Searching". The Art of Computer Programming, Vol. 3: Sorting and Searching (2nd ed.). Addison Wesley. pp. 396–405. ISBN 0-201-89685-0.
  3. ↑ Janes, Calvin (2011). "Using Association Lists for Associative Arrays". Microsoft .NET में संग्रह के लिए डेवलपर की मार्गदर्शिका. Pearson Education. p. 191. ISBN 9780735665279.
  4. ↑ 4.0 4.1 McCarthy, John; Abrahams, Paul W.; Edwards, Daniel J.; Hart, Timothy P.; Levin, Michael I. (1985). एलआईएसपी 1.5 प्रोग्रामर मैनुअल. MIT Press. ISBN 0-262-13011-4. विशेष रूप से पी देखें। 12 उन फ़ंक्शंस के लिए जो एसोसिएशन सूची खोजते हैं और किसी अन्य अभिव्यक्ति में प्रतीकों को प्रतिस्थापित करने के लिए इसका उपयोग करते हैं, और पी। वैरिएबल बाइंडिंग को बनाए रखने में एसोसिएशन सूचियों के अनुप्रयोग के लिए 103।
  5. ↑ van de Snepscheut, Jan L. A. (1993). कंप्यूटिंग क्या है?. Monographs in Computer Science. Springer. p. 201. ISBN 9781461227106.
  6. ↑ Scott, Michael Lee (2000). "3.3.4 Association Lists and Central Reference Tables". प्रोग्रामिंग भाषा व्यावहारिकता. Morgan Kaufmann. p. 137. ISBN 9781558604421.
  7. ↑ Pearce, Jon (2012). योजना में प्रोग्रामिंग और मेटा-प्रोग्रामिंग. Undergraduate Texts in Computer Science. Springer. p. 214. ISBN 9781461216827.
  8. ↑ Minsky, Yaron; Madhavapeddy, Anil; Hickey, Jason (2013). Real World OCaml: Functional Programming for the Masses. O'Reilly Media. p. 253. ISBN 9781449324766.
  9. ↑ O'Sullivan, Bryan; Goerzen, John; Stewart, Donald Bruce (2008). Real World Haskell: Code You Can Believe In. O'Reilly Media. p. 299. ISBN 9780596554309.
  10. ↑ "10.1. संपत्ति सूची". Cs.cmu.edu. Retrieved 29 September 2017.
Retrieved from ‘https://www.vigyanwiki.in/index.php?title=एसोसिएशन_सूची&oldid=244892’