विशुद्ध रूप से कार्यात्मक डेटा संरचना
कंप्यूटर विज्ञान में, पूर्ण रुप से कार्यात्मक डेटा संरचना एक डेटा संरचना है जिसे पूर्ण रुप से कार्यात्मक भाषा में कार्यान्वित किया जा सकता है। एक स्वेच्छाचारी डेटा संरचना और पूर्ण रुप से कार्यात्मक के बीच मुख्य अंतर यह है कि उत्तरार्द्ध (दृढ़ता से) अपरिवर्तनीय वस्तु है। यह प्रतिबंध सुनिश्चित करता है कि डेटा संरचना में अपरिवर्तनीय वस्तुओं के फायदे हैं: (पूर्ण) दृढ़ता, वस्तुओं की त्वरित प्रतिलिपि, और थ्रेड सुरक्षा। कुशल पूर्ण रुप से कार्यात्मक डेटा संरचनाओं को आलसी मूल्यांकन और मेमोइज़ेशन के उपयोग की आवश्यकता हो सकती है।
परिभाषा
स्थायी डेटा संरचनाओं में स्वयं के पिछले संस्करणों को असंशोधित रखने का गुण होता है। दूसरी ओर, सरणी डेटा संरचना जैसी संरचनाएँ विनाशकारी अद्यतन स्वीकार करती हैं,[1] अर्थात्, एक अद्यतन जिसे पूर्ववत नहीं किया जा सकता है। एक बार जब कोई प्रोग्राम सरणी के कुछ सूचकांक में मान लिखता है, तो इसका पिछला मान अब और पुनर्प्राप्त नहीं किया जा सकता है।[citation needed]
औपचारिक रूप से, पूर्ण रुप से कार्यात्मक डेटा संरचना एक डेटा संरचना है जिसे पूर्ण रुप से कार्यात्मक भाषा में लागू किया जा सकता है, जैसे कि हास्केल (प्रोग्रामिंग भाषा)। व्यवहार में, इसका अर्थ है कि डेटा संरचनाओं को केवल निरंतर डेटा संरचनाओं जैसे टुपल्स, योग प्रकार, उत्पाद प्रकार और मूल प्रकार जैसे पूर्णांक, वर्ण, तार का उपयोग करके बनाया जाना चाहिए। ऐसी डेटा संरचना अनिवार्य रूप से स्थायी होती है। हालाँकि, सभी स्थायी डेटा संरचनाएँ पूर्ण रुप से कार्यात्मक नहीं हैं।[1]: 16 उदाहरण के लिए, एक सतत सरणी एक डेटा-संरचना है जो लगातार है और जो एक सरणी का उपयोग करके कार्यान्वित की जाती है, इस प्रकार पूरी तरह कार्यात्मक नहीं है।[citation needed]
पूर्ण रुप से कार्यात्मक डेटा संरचनाओं की पुस्तक में, ओकासाकी विनाशकारी अपडेट की तुलना मास्टर शेफ के चाकू से करता है।[1]: 2 विनाशकारी अद्यतन पूर्ववत नहीं किया जा सकता हैं, और इस प्रकार उनका उपयोग तब तक नहीं किया जाना चाहिए जब तक कि यह निश्चित न हो कि पिछले मान की अब आवश्यकता नहीं है। हालांकि, विनाशकारी अद्यतन दक्षता की अनुमति भी दे सकते हैं जिसे अन्य तकनीकों का उपयोग करके प्राप्त नहीं किया जा सकता है। उदाहरण के लिए, एक सरणी और विनाशकारी अद्यतनों का उपयोग करने वाली एक डेटा संरचना को एक समान डेटा संरचना द्वारा प्रतिस्थापित किया जा सकता है जहां सरणी को मानचित्र (कंप्यूटर विज्ञान), एक यादृच्छिक अभिगम सूची, या एक संतुलित वृक्ष द्वारा प्रतिस्थापित किया जाता है, जो पूर्ण रुप से कार्यात्मक कार्यान्वयन को स्वीकार करता है। लेकिन पहुंच लागत निरंतर समय से लॉगरिदमिक समय तक बढ़ सकती है।[citation needed]
यह सुनिश्चित करना कि डेटा संरचना पूर्ण रुप से कार्यात्मक है
एक डेटा संरचना कभी भी स्वाभाविक रूप से कार्यात्मक नहीं होती है। उदाहरण के लिए, एक स्टैक को एकल-लिंक्ड सूची के रूप में कार्यात्मक किया जा सकता है। यह कार्यान्वयन पूर्ण रुप से कार्यात्मक है जब तक कि स्टैक पर एकमात्र ऑपरेशन पुराने स्टैक को बदले बिना एक नया स्टैक वापस करता है है। हालाँकि, यदि भाषा पूर्ण रुप से कार्यात्मक नहीं है, तो रन-टाइम सिस्टम अपरिवर्तनीयता की गारंटी देने में असमर्थ हो सकता है। यह ओकासाकी द्वारा सचित्र है,[1]: 9–11 जहां वह दिखाता है कि दो एकल-लिंक्ड सूचियों का संयोजन अभी भी अनिवार्य सेटिंग का उपयोग करके किया जा सकता है।[citation needed]
यह सुनिश्चित करने के लिए कि एक अशुद्ध कार्यात्मक भाषा में एक डेटा संरचना का उपयोग पूर्ण रुप से कार्यात्मक तरीके से किया जाता है, मॉड्यूलर प्रोग्रामिंग या क्लास (कंप्यूटर प्रोग्रामिंग) का उपयोग केवल अधिकृत कार्यों के माध्यम से हेरफेर सुनिश्चित करने के लिए किया जा सकता है।[citation needed]
पूर्ण रुप से कार्यात्मक डेटा संरचनाओं का उपयोग करना
पूर्ण रुप से कार्यात्मक डेटा संरचनाओं का उपयोग करने के लिए मौजूदा कोड को अपनाने में केंद्रीय चुनौतियों में से एक यह तथ्य है कि परिवर्तनशील डेटा संरचनाएं उन कार्यों के लिए छिपे हुए आउटपुट प्रदान करती हैं जो उनका उपयोग करते हैं। पूर्ण रुप से कार्यात्मक डेटा संरचनाओं का उपयोग करने के लिए इन कार्यों को पुनर्लेखन इन डेटा संरचनाओं को स्पष्ट आउटपुट के रूप में जोड़ने की आवश्यकता है।
उदाहरण के लिए, एक फलन पर विचार करें जो एक परिवर्तनशील सूची को स्वीकार करता है, सूची से पहले तत्व को हटाता है और उस तत्व को वापस करता है। पूर्ण रुप से कार्यात्मक सेटिंग में, सूची से किसी तत्व को हटाने से एक नई और छोटी सूची बनती है, लेकिन मूल को अपडेट नहीं करता है।एक ज़िप एक समग्र डेटा संरचना का प्रतिनिधित्व करने की एक तकनीक है ताकि यह प्रोग्राम लिखने के लिए सुविधाजनक हो जो संरचना को मनमाने ढंग से पार करता है और इसकी सामग्री को अद्यतन करता है, विशेष रूप से विशुद्ध रूप से कार्यात्मक प्रोग्रामिंग भाषाओं में। ज़िपर का वर्णन 1997 में जेरार्ड ह्यूएट द्वारा किया गया था। [1] इसमें कभी-कभी सरणियों के साथ उपयोग की जाने वाली गैप बफर तकनीक को सम्मिलित और सामान्यीकृत किया जाता है। उपयोगी होने के लिए, इसलिए, इस फलन के पूरी तरह कार्यात्मक संस्करण को हटाए गए तत्व के साथ नई सूची वापस करने की संभावना है। ज़िपर तकनीक इस मायने में सामान्य है कि इसे सूचियों, पेड़ों और अन्य पुनरावर्ती रूप से परिभाषित डेटा संरचनाओं के लिए अनुकूलित किया जा सकता है। इस तरह की संशोधित डेटा संरचनाओं को सामान्यतः "जिपर के साथ एक पेड़" या "जिपर के साथ एक सूची" के रूप में संदर्भित किया जाता है ताकि यह जोर दिया जा सके कि संरचना वैचारिक रूप से एक पेड़ या सूची है, जबकि ज़िपर कार्यान्वयन का एक विवरण है। सबसे सामान्य मामले में, इस तरह से परिवर्तित प्रोग्राम को प्रत्येक फलन कॉल से अतिरिक्त परिणाम के रूप में प्रोग्राम की स्थिति या स्टोर को वापस करना होगा। ऐसा कहा जाता है कि इस तरह के प्रोग्राम को स्टोर-पासिंग स्टाइल में लिखा जाता है।
उदाहरण
यहाँ पूर्ण रुप से कार्यात्मक कार्यान्वयन के साथ सार डेटा संरचनाओं की एक सूची है:
- स्टैक (फर्स्ट इन, लास्ट आउट) सिंगल लिंक की गई सूची के रूप में लागू किया गया,
- कतार, एक वास्तविक समय कतार के रूप में कार्यान्वित,
- डबल-एंडेड कतार, रीयल-टाइम डेक के रूप में लागू की गई| रीयल-टाइम डबल-एंडेड कतार,
- सेट (सार डेटा प्रकार) | (बहु) ऑर्डर किए गए तत्वों का सेट और ऑर्डर की गई चाबियों द्वारा अनुक्रमित मानचित्र (कंप्यूटर विज्ञान), लाल-काले पेड़ के रूप में कार्यान्वित किया जाता है, या सामान्यतः एक खोज पेड़ द्वारा लागू किया जाता है,
- प्राथमिकता कतार, ब्रोडल कतार के रूप में कार्यान्वित
- रैंडम एक्सेस लिस्ट, स्क्यू-बाइनरी रैंडम एक्सेस लिस्ट के रूप में लागू की गई
- हैश कंसिंग
- जिपर (डेटा संरचना)
डिजाइन और कार्यान्वयन
कंप्यूटर वैज्ञानिक क्रिस ओकासाकी ने अपनी पुस्तक प्योर्ली फंक्शनल डेटा स्ट्रक्चर्स में पूर्ण रुप से कार्यात्मक डेटा संरचनाओं को डिजाइन और कार्यान्वित करने के लिए उपयोग की जाने वाली तकनीकों का वर्णन किया है, जिनमें से एक छोटे उपसमुच्चय का सारांश नीचे दिया गया है।
आलस्य और संस्मरण
पूर्ण रुप से कार्यात्मक भाषा में आलसी मूल्यांकन विशेष रूप से दिलचस्प है[1]: 31 क्योंकि मूल्यांकन का क्रम किसी फलन के परिणाम को कभी नहीं बदलता है। इसलिए, आलसी मूल्यांकन स्वाभाविक रूप से पूर्ण रुप से कार्यात्मक डेटा संरचनाओं के निर्माण का एक महत्वपूर्ण हिस्सा बन जाता है। यह केवल एक गणना करने की अनुमति देता है जब इसके परिणाम की वास्तव में आवश्यकता होती है। इसलिए, पूर्ण रुप से कार्यात्मक डेटा संरचना का कोड, दक्षता के नुकसान के बिना, इसी तरह के डेटा पर विचार कर सकता है जो प्रभावी रूप से उपयोग किया जाएगा और डेटा जिसे अनदेखा किया जाएगा। पहली तरह के डेटा के लिए केवल आवश्यक गणना है; वास्तव में यही किया जाएगा।[citation needed]
कुशल, पूर्ण रुप से कार्यात्मक डेटा संरचनाओं के निर्माण में प्रमुख उपकरणों में से एक मेमोइज़ेशन है।[1]: 31 जब कोई संगणना की जाती है, तो इसे सहेजा जाता है और इसे दूसरी बार करने की आवश्यकता नहीं होती है। आलसी कार्यान्वयन में यह विशेष रूप से महत्वपूर्ण है; अतिरिक्त मूल्यांकन के लिए समान परिणाम की आवश्यकता हो सकती है, लेकिन यह जानना असंभव है कि किस मूल्यांकन के लिए पहले इसकी आवश्यकता होगी।[citation needed]
परिशोधित विश्लेषण और नियोजन
कुछ डेटा संरचनाएं, यहां तक कि वे जो पूर्ण रुप से कार्यात्मक नहीं हैं जैसे कि डायनेमिक सरणियाँ, उन ऑपरेशनों को स्वीकार करती हैं जो अधिकांश समय कुशल होते हैं (जैसे, डायनेमिक सरणियों के लिए निरंतर समय), और शायद ही कभी अक्षम (जैसे, डायनेमिक सरणियों के लिए रैखिक समय)। परिशोधित विश्लेषण का उपयोग यह साबित करने के लिए किया जा सकता है कि संचालन का औसत चलने का समय कुशल है।[1]: 39 अर्थात्, कुछ अकुशल संचालन काफी दुर्लभ हैं, और जब संचालन के अनुक्रम पर विचार किया जाता है तो समय की जटिलता के स्पर्शोन्मुख विकास को नहीं बदलते हैं।[citation needed]
सामान्यतः, लगातार डेटा संरचनाओं के लिए अक्षम संचालन स्वीकार्य नहीं है, क्योंकि यह बहुत ही ऑपरेशन को कई बार कहा जा सकता है। यह या तो वास्तविक समय या अनिवार्य प्रणालियों के लिए स्वीकार्य नहीं है, जहां उपयोगकर्ता को अनुमान लगाने योग्य होने के लिए ऑपरेशन में लगने वाले समय की आवश्यकता हो सकती है। इसके अलावा, यह अप्रत्याशितता समानांतर कंप्यूटिंग के उपयोग को जटिल बनाती है।[1]: 83 [citation needed]
उन समस्याओं से बचने के लिए, कुछ डेटा संरचनाएं अक्षम संचालन को स्थगित करने की अनुमति देती हैं- इसे निर्धारण (कंप्यूटिंग) कहा जाता है।[1]: 84 एकमात्र आवश्यकता यह है कि अक्षम संचालन की गणना इसके परिणाम की वास्तव में आवश्यकता होने से पहले ही समाप्त हो जानी चाहिए। एक कुशल संचालन के लिए निम्नलिखित कॉल के साथ अक्षम संचालन का एक निरंतर हिस्सा एक साथ किया जाता है, ताकि जब आवश्यक हो तो अक्षम संचालन पूरी तरह से किया जा सके, और प्रत्येक व्यक्तिगत ऑपरेशन कुशल बना रहे।[clarification needed]
उदाहरण: पंक्ति
परिशोधित पंक्ति[1]: 65 [1]: 73 दो एकल-लिंक्ड सूचियों से बनी है: आगे और पीछे का उलटा। तत्वों को पीछे की सूची में जोड़ा जाता है और सामने की सूची से हटा दिया जाता है। इसके अलावा, जब भी सामने की कतार खाली होती है, तो पीछे की कतार उलट जाती है और सामने हो जाती है, जबकि पीछे की कतार खाली हो जाती है। प्रत्येक ऑपरेशन की परिशोधित समय जटिलता स्थिर है। सूची के प्रत्येक सेल को एक बार जोड़ा, उलटा और हटाया जाता है। एक अकुशल संचालन से बचने के लिए जहां पिछली सूची को उलट दिया जाता है, रीयल-टाइम कतारें प्रतिबंध जोड़ती हैं कि पीछे की सूची केवल सामने की सूची जितनी लंबी होती है। यह सुनिश्चित करने के लिए कि पीछे की सूची सामने की सूची से अधिक लंबी हो जाती है, सामने की सूची को पीछे की सूची में जोड़ दिया जाता है और उलट दिया जाता है। चूंकि यह ऑपरेशन अक्षम है, इसलिए इसे तुरंत नहीं किया जाता है। इसके बजाय, यह बाद के कार्यों में फैला हुआ है। इस प्रकार, प्रत्येक सेल की आवश्यकता होने से पहले उसकी गणना की जाती है, और एक नए अक्षम ऑपरेशन को बुलाए जाने से पहले नई फ्रंट सूची पूरी तरह से गणना की जाती है।[citation needed]
यह भी देखें
- लगातार डेटा संरचना
संदर्भ
बाहरी संबंध
- Purely Functional Data Structures thesis by Chris Okasaki (PDF format)
- Making Data-Structures Persistent by James R. Driscoll, Neil Sarnak, Daniel D. Sleator, Robert E. Tarjan (PDF)
- Fully Persistent Lists with Catenation by James R. Driscoll, Daniel D. Sleator, Robert E. Tarjan (PDF)
- Persistent Data Structures from the MIT OpenCourseWare course Advanced Algorithms
- What's new in purely functional data structures since Okasaki? on Theoretical Computer Science Stack Exchange
