एसोसिएशन सूची: Difference between revisions
(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 |
||
| 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> | |||
एसोसिएशन सूची में | |||
एक एसोसिएशन सूची से कुंजी को हटाना भी संभव है, इसके लिए सूची के प्रत्येक घटना को सर्च और सूची से कुंजी वाले नोड को हटाने के लिए अनुमति दी जाती है। स्कैन सूची के अंत तक जारी रहना चाहिए, भले ही कुंजी मिल जाए, इसका अर्थ यह है कि एक ही कुंजी को कई बार सूची में डाला जा सकता है। | |||
==प्रदर्शन== | ==प्रदर्शन== | ||
एसोसिएशन सूचियों का नुकसान यह है कि इसमें | एसोसिएशन सूचियों का नुकसान यह है कि इसमें सर्च का समय लगता है {{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> | ||
| Line 38: | Line 38: | ||
==यह भी देखें== | ==यह भी देखें== | ||
*स्व-व्यवस्थित सूची, बार-बार एक्सेस की जाने वाली कुंजियों की | *स्व-व्यवस्थित सूची, बार-बार एक्सेस की जाने वाली कुंजियों की सर्च को तेज़ करने के लिए एसोसिएशन सूची में कुंजियों को फिर से व्यवस्थित करने की एक रणनीति | ||
*[[संपत्ति सूची]], या प्लिस्ट, लिस्प में प्रयुक्त एक अन्य सहयोगी सरणी प्रारूप।<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> | ||
Revision as of 11:42, 6 August 2023
| Association list | ||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Type | associative array | |||||||||||||||
| Time complexity in big O notation | ||||||||||||||||
| ||||||||||||||||
कंप्यूटर प्रोग्रामिंग में और विशेष रूप से लिस्प में, एक एसोसिएशन सूची, जिसे अक्सर एलिस्ट के रूप में जाना जाता है, एक लिंक की गई सूची है जिसमें प्रत्येक सूची तत्व या नोड में एक विशेषता-मूल्य जोड़ी सम्मिलित होती है। ऐसा कहा जाता है कि एसोसिएशन सूची कुंजी के साथ मूल्य को संबद्ध करती है। एक दिए गए कुंजी के साथ जुड़े मूल्य को सर्च के लिए एक अनुक्रमिक सर्च का उपयोग किया जाता है। सूची के प्रत्येक तत्व को शीर्ष से प्रारंभ करके सर्च की जाती है, जब तक कुंजी मिल नहीं जाती तब तक सहयोगी सूचियाँ एक सहयोगी सरणी को लागू करने का एक सरल विधि प्रदान करती हैं, परंतु केवल तभी कुशल होती हैं जब कुंजियों की संख्या बहुत कम होती है।
संचालन
एक सहयोगी सरणी अभिकल्पित डेटा प्रकार है जिसका उपयोग कुंजी-मूल्य युग्म के संग्रह को बनाए रखने और एक दिए गए कुंजी के साथ जुड़े मूल्य की सर्च करने के लिए किया जा सकता है। एसोसिएशन सूची इस डेटा प्रकार को लागू करने का एक सरल विधि प्रदान करता है।
एक एसोसिएशन सूची में किसी कुंजी के साथ मूल्य का संबंध है या नहीं, इसे जाँचने के लिए सूची के पहले तत्व से सर्च प्रारंभ करें और पुनः तत्व मिल जाने तक या सूची के अंत तक सर्च जारी रखें। एक एसोसिएशन सूची में नई कुंजी-मूल्य युग्म जोड़ने के लिए, उस कुंजी-मूल्य युग्म के लिए एक नया नोड बनाएं, नोड के लिंक को एसोसिएशन सूची के पिछले प्रथम तत्व के साथ सेट करें, और एसोसिएशन सूची का प्रथम तत्व नए नोड से बदल दें। ज्यादातर एसोसिएशन सूची के अनुमानित कार्यनीतियाँ एक्सपेक्टेड विधि से काम करती हैं, लेकिन कुंजी के साथ एक ही तत्व के अनुक्रम में अनुशासन करने की अनुमति नहीं देतीं हैं: सूची के बाद के डुप्लिकेट कुंजी-मूल्य युग्म इस सर्च एल्गोरिदम के लिए कोई समस्या नहीं बनाते हैं।[1]
एक एसोसिएशन सूची से कुंजी को हटाना भी संभव है, इसके लिए सूची के प्रत्येक घटना को सर्च और सूची से कुंजी वाले नोड को हटाने के लिए अनुमति दी जाती है। स्कैन सूची के अंत तक जारी रहना चाहिए, भले ही कुंजी मिल जाए, इसका अर्थ यह है कि एक ही कुंजी को कई बार सूची में डाला जा सकता है।
प्रदर्शन
एसोसिएशन सूचियों का नुकसान यह है कि इसमें सर्च का समय लगता है O(n), कहाँ n सूची की लंबाई है.[2] बड़ी सूचियों के लिए, यह उस समय की तुलना में बहुत धीमा हो सकता है जो एक सहयोगी सरणी को बाइनरी सर्च ट्री या हैश तालिका के रूप में प्रस्तुत करके प्राप्त किया जा सकता है। इसके अतिरिक्त, जब तक डुप्लिकेट कुंजियों वाले तत्वों को हटाने के लिए सूची को नियमित रूप से नहीं काटा जाता है, तब तक एक ही कुंजी से जुड़े कई मान सूची के आकार को बढ़ा देंगे, और इस प्रकार बिना कोई प्रतिपूरक लाभ प्रदान किए सर्च करने का समय बढ़ जाएगा।
एसोसिएशन सूचियों का एक फायदा यह है कि निरंतर समय में एक नया तत्व जोड़ा जा सकता है। इसके अतिरिक्त, जब कुंजियों की संख्या बहुत कम होती है, तो उनके कार्यान्वयन की अधिक सरलता के कारण, बाइनरी सर्च ट्री या हैश तालिका की सर्च करने की तुलना में एसोसिएशन सूची सर्चना अधिक कुशल हो सकता है।[3]
अनुप्रयोग और सॉफ्टवेयर लाइब्रेरी
लिस्प के शुरुआती विकास में, प्रक्रियाओं में मुक्त चर और बाध्य चर के संदर्भों को हल करने के लिए एसोसिएशन सूचियों का उपयोग किया गया था।[4][5] इस एप्लिकेशन में, एक अतिरिक्त ऑपरेशन के साथ एसोसिएशन सूचियों को बढ़ाना सुविधाजनक है, जो उसी कुंजी की अन्य प्रतियों के लिए सूची को स्कैन किए बिना कुंजी-मूल्य जोड़ी के जोड़ को उलट देता है। इस तरह, एसोसिएशन सूची एक स्टैक (अमूर्त डेटा प्रकार) के रूप में कार्य कर सकती है, जो स्थानीय चर को उन अन्य चर के मूल्यों को नष्ट किए बिना, समान नाम वाले अन्य चर को अस्थायी रूप से छाया देने की अनुमति देती है।[6] सहित कई प्रोग्रामिंग भाषाएँ लिस्प,[4]योजना (प्रोग्रामिंग भाषा),[7] ओकैमल,[8] और हास्केल (प्रोग्रामिंग भाषा)[9] उनके मानक पुस्तकालय में एसोसिएशन सूचियों को संभालने के लिए कार्य हैं।
यह भी देखें
- स्व-व्यवस्थित सूची, बार-बार एक्सेस की जाने वाली कुंजियों की सर्च को तेज़ करने के लिए एसोसिएशन सूची में कुंजियों को फिर से व्यवस्थित करने की एक रणनीति
- संपत्ति सूची, या प्लिस्ट, लिस्प में प्रयुक्त एक अन्य सहयोगी सरणी प्रारूप।[10]
संदर्भ
- ↑ Marriott, Kim; Stuckey, Peter J. (1998). Programming with Constraints: An Introduction. MIT Press. pp. 193–195. ISBN 9780262133418.
- ↑ 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.
- ↑ Janes, Calvin (2011). "Using Association Lists for Associative Arrays". Microsoft .NET में संग्रह के लिए डेवलपर की मार्गदर्शिका. Pearson Education. p. 191. ISBN 9780735665279.
- ↑ 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।
- ↑ van de Snepscheut, Jan L. A. (1993). कंप्यूटिंग क्या है?. Monographs in Computer Science. Springer. p. 201. ISBN 9781461227106.
- ↑ Scott, Michael Lee (2000). "3.3.4 Association Lists and Central Reference Tables". प्रोग्रामिंग भाषा व्यावहारिकता. Morgan Kaufmann. p. 137. ISBN 9781558604421.
- ↑ Pearce, Jon (2012). योजना में प्रोग्रामिंग और मेटा-प्रोग्रामिंग. Undergraduate Texts in Computer Science. Springer. p. 214. ISBN 9781461216827.
- ↑ Minsky, Yaron; Madhavapeddy, Anil; Hickey, Jason (2013). Real World OCaml: Functional Programming for the Masses. O'Reilly Media. p. 253. ISBN 9781449324766.
- ↑ 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.1. संपत्ति सूची". Cs.cmu.edu. Retrieved 29 September 2017.
