एसोसिएशन सूची
| Association list | ||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Type | associative array | |||||||||||||||
| Time complexity in big O notation | ||||||||||||||||
| ||||||||||||||||
कंप्यूटर प्रोग्रामिंग में और विशेष रूप से लिस्प (प्रोग्रामिंग भाषा) में, एक एसोसिएशन सूची, जिसे अक्सर एलिस्ट के रूप में जाना जाता है, एक लिंक की गई सूची है जिसमें प्रत्येक सूची तत्व (या नोड (कंप्यूटर विज्ञान)) में एक विशेषता-मूल्य जोड़ी शामिल होती है। ऐसा कहा जाता है कि एसोसिएशन सूची कुंजी के साथ मूल्य को संबद्ध करती है। किसी दी गई कुंजी से जुड़े मूल्य को खोजने के लिए, एक अनुक्रमिक खोज का उपयोग किया जाता है: सूची के प्रत्येक तत्व को बारी-बारी से खोजा जाता है, शीर्ष से शुरू करके, जब तक कि कुंजी नहीं मिल जाती। सहयोगी सूचियाँ एक सहयोगी सरणी को लागू करने का एक सरल तरीका प्रदान करती हैं, लेकिन केवल तभी कुशल होती हैं जब कुंजियों की संख्या बहुत कम होती है।
संचालन
एक सहयोगी सरणी एक अमूर्त डेटा प्रकार है जिसका उपयोग विशेषता-मूल्य जोड़ी | कुंजी-मूल्य जोड़े के संग्रह को बनाए रखने और किसी दिए गए कुंजी से जुड़े मूल्य को देखने के लिए किया जा सकता है। एसोसिएशन सूची इस डेटा प्रकार को लागू करने का एक सरल तरीका प्रदान करती है।
यह जांचने के लिए कि क्या कोई कुंजी किसी दिए गए एसोसिएशन सूची में किसी मान से जुड़ी हुई है, सूची को उसके पहले नोड से शुरू करके तब तक खोजें जब तक कि कुंजी वाला नोड नहीं मिल जाता या जब तक खोज सूची के अंत तक नहीं पहुंच जाती (जिस स्थिति में कुंजी मौजूद नहीं है)। एसोसिएशन सूची में एक नई कुंजी-मूल्य जोड़ी जोड़ने के लिए, उस कुंजी-मूल्य जोड़ी के लिए एक नया नोड बनाएं, नोड के लिंक को एसोसिएशन सूची के पिछले पहले तत्व के रूप में सेट करें, और एसोसिएशन सूची के पहले तत्व को नए नोड से बदलें।[1] हालाँकि एसोसिएशन सूचियों के कुछ कार्यान्वयन एक-दूसरे के समान कुंजियों के साथ कई नोड्स रखने की अनुमति नहीं देते हैं, इस खोज एल्गोरिदम के लिए ऐसे दोहराव समस्याग्रस्त नहीं हैं: सूची में बाद में दिखाई देने वाली डुप्लिकेट कुंजियों को अनदेखा कर दिया जाता है।[2] कुंजी की प्रत्येक घटना का पता लगाने के लिए सूची को स्कैन करके और कुंजी वाले नोड्स को सूची से बाहर करके, एसोसिएशन सूची से एक कुंजी को हटाना भी संभव है।[1]स्कैन सूची के अंत तक जारी रहना चाहिए, भले ही कुंजी मिल जाए, यदि एक ही कुंजी कई बार डाली गई हो।
प्रदर्शन
एसोसिएशन सूचियों का नुकसान यह है कि इसमें खोजने का समय लगता है O(n), कहाँ n सूची की लंबाई है.[3] बड़ी सूचियों के लिए, यह उस समय की तुलना में बहुत धीमा हो सकता है जो एक सहयोगी सरणी को बाइनरी सर्च ट्री या हैश तालिका के रूप में प्रस्तुत करके प्राप्त किया जा सकता है। इसके अतिरिक्त, जब तक डुप्लिकेट कुंजियों वाले तत्वों को हटाने के लिए सूची को नियमित रूप से नहीं काटा जाता है, तब तक एक ही कुंजी से जुड़े कई मान सूची के आकार को बढ़ा देंगे, और इस प्रकार बिना कोई प्रतिपूरक लाभ प्रदान किए खोज करने का समय बढ़ जाएगा।
एसोसिएशन सूचियों का एक फायदा यह है कि निरंतर समय में एक नया तत्व जोड़ा जा सकता है। इसके अतिरिक्त, जब कुंजियों की संख्या बहुत कम होती है, तो उनके कार्यान्वयन की अधिक सरलता के कारण, बाइनरी सर्च ट्री या हैश तालिका की खोज करने की तुलना में एसोसिएशन सूची खोजना अधिक कुशल हो सकता है।[4]
अनुप्रयोग और सॉफ्टवेयर लाइब्रेरी
लिस्प के शुरुआती विकास में, प्रक्रियाओं में मुक्त चर और बाध्य चर के संदर्भों को हल करने के लिए एसोसिएशन सूचियों का उपयोग किया गया था।[5][6] इस एप्लिकेशन में, एक अतिरिक्त ऑपरेशन के साथ एसोसिएशन सूचियों को बढ़ाना सुविधाजनक है, जो उसी कुंजी की अन्य प्रतियों के लिए सूची को स्कैन किए बिना कुंजी-मूल्य जोड़ी के जोड़ को उलट देता है। इस तरह, एसोसिएशन सूची एक स्टैक (अमूर्त डेटा प्रकार) के रूप में कार्य कर सकती है, जो स्थानीय चर को उन अन्य चर के मूल्यों को नष्ट किए बिना, समान नाम वाले अन्य चर को अस्थायी रूप से छाया देने की अनुमति देती है।[7] सहित कई प्रोग्रामिंग भाषाएँ लिस्प,[5]योजना (प्रोग्रामिंग भाषा),[8] ओकैमल,[9] और हास्केल (प्रोग्रामिंग भाषा)[10] उनके मानक पुस्तकालय में एसोसिएशन सूचियों को संभालने के लिए कार्य हैं।
यह भी देखें
- स्व-व्यवस्थित सूची, बार-बार एक्सेस की जाने वाली कुंजियों की खोज को तेज़ करने के लिए एसोसिएशन सूची में कुंजियों को फिर से व्यवस्थित करने की एक रणनीति
- संपत्ति सूची, या प्लिस्ट, लिस्प में प्रयुक्त एक अन्य सहयोगी सरणी प्रारूप।[11]
संदर्भ
- ↑ 1.0 1.1 Marriott, Kim; Stuckey, Peter J. (1998). Programming with Constraints: An Introduction. MIT Press. pp. 193–195. ISBN 9780262133418.
- ↑ Frické, Martin (2012). "2.8.3 Association Lists". तर्क और सूचना का संगठन. Springer. pp. 44–45. ISBN 9781461430872.
- ↑ 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.
- ↑ 5.0 5.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.
