एसोसिएशन सूची
| 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.
