विशुद्ध रूप से कार्यात्मक डेटा संरचना
 | This article needs additional citations for verification. (January 2017) (Learn how and when to remove this template message) |
कंप्यूटर विज्ञान में, विशुद्ध रूप से कार्यात्मक डेटा संरचना एक डेटा संरचना है जिसे विशुद्ध रूप से कार्यात्मक भाषा में लागू किया जा सकता है। एक मनमाना डेटा संरचना और विशुद्ध रूप से कार्यात्मक एक के बीच मुख्य अंतर यह है कि उत्तरार्द्ध (दृढ़ता से) अपरिवर्तनीय वस्तु है। यह प्रतिबंध सुनिश्चित करता है कि डेटा संरचना में अपरिवर्तनीय वस्तुओं के फायदे हैं: (पूर्ण) लगातार डेटा संरचना, वस्तुओं की त्वरित प्रतिलिपि, और थ्रेड सुरक्षा। कुशल विशुद्ध रूप से कार्यात्मक डेटा संरचनाओं को आलसी मूल्यांकन और memoization के उपयोग की आवश्यकता हो सकती है।
परिभाषा
स्थायी डेटा संरचनाओं में स्वयं के पिछले संस्करणों को असंशोधित रखने का गुण होता है। दूसरी ओर, सरणी डेटा संरचना जैसी संरचनाएँ विनाशकारी अद्यतन स्वीकार करती हैं,[1] अर्थात्, एक अद्यतन जिसे पूर्ववत नहीं किया जा सकता है। एक बार जब कोई प्रोग्राम सरणी के कुछ इंडेक्स में मान लिखता है, तो इसका पिछला मान अब और पुनर्प्राप्त नहीं किया जा सकता है।[citation needed]
औपचारिक रूप से, विशुद्ध रूप से कार्यात्मक डेटा संरचना एक डेटा संरचना है जिसे विशुद्ध रूप से कार्यात्मक भाषा में लागू किया जा सकता है, जैसे कि हास्केल (प्रोग्रामिंग भाषा)। व्यवहार में, इसका अर्थ है कि डेटा संरचनाओं को केवल निरंतर डेटा संरचनाओं जैसे टुपल्स, योग प्रकार, उत्पाद प्रकार और मूल प्रकार जैसे पूर्णांक, वर्ण, तार का उपयोग करके बनाया जाना चाहिए। ऐसी डेटा संरचना अनिवार्य रूप से स्थायी होती है। हालाँकि, सभी स्थायी डेटा संरचनाएँ विशुद्ध रूप से कार्यात्मक नहीं हैं।[1]: 16 उदाहरण के लिए, एक सतत सरणी एक डेटा-संरचना है जो लगातार है और जो एक सरणी का उपयोग करके कार्यान्वित की जाती है, इस प्रकार पूरी तरह कार्यात्मक नहीं है।[citation needed]
विशुद्ध रूप से कार्यात्मक डेटा संरचनाओं की पुस्तक में, ओकासाकी मास्टर शेफ के चाकू के विनाशकारी अद्यतनों की तुलना करता है।[1]: 2 विनाशकारी अद्यतन पूर्ववत नहीं किए जा सकते हैं, और इस प्रकार उनका उपयोग तब तक नहीं किया जाना चाहिए जब तक कि यह निश्चित न हो कि पिछले मान की अब आवश्यकता नहीं है। हालांकि, विनाशकारी अद्यतन दक्षता की अनुमति भी दे सकते हैं जिसे अन्य तकनीकों का उपयोग करके प्राप्त नहीं किया जा सकता है। उदाहरण के लिए, एक सरणी और विनाशकारी अद्यतनों का उपयोग करने वाली एक डेटा संरचना को एक समान डेटा संरचना द्वारा प्रतिस्थापित किया जा सकता है जहां सरणी को मानचित्र (कंप्यूटर विज्ञान), एक यादृच्छिक अभिगम सूची, या एक संतुलित वृक्ष द्वारा प्रतिस्थापित किया जाता है, जो विशुद्ध रूप से कार्यात्मक कार्यान्वयन को स्वीकार करता है। लेकिन पहुंच लागत निरंतर समय से लॉगरिदमिक समय तक बढ़ सकती है।[citation needed]
यह सुनिश्चित करना कि डेटा संरचना विशुद्ध रूप से कार्यात्मक है
एक डेटा संरचना कभी भी स्वाभाविक रूप से कार्यात्मक नहीं होती है। उदाहरण के लिए, एक स्टैक को एकल-लिंक्ड सूची के रूप में लागू किया जा सकता है। यह कार्यान्वयन विशुद्ध रूप से कार्यात्मक है जब तक कि स्टैक पर एकमात्र ऑपरेशन पुराने स्टैक को बदले बिना एक नया स्टैक लौटाता है। हालाँकि, यदि भाषा विशुद्ध रूप से कार्यात्मक नहीं है, तो रन-टाइम सिस्टम अपरिवर्तनीयता की गारंटी देने में असमर्थ हो सकता है। यह ओकासाकी द्वारा सचित्र है,[1]: 9–11 जहां वह दिखाता है कि दो एकल-लिंक्ड सूचियों का संयोजन अभी भी अनिवार्य सेटिंग का उपयोग करके किया जा सकता है।[citation needed]
यह सुनिश्चित करने के लिए कि एक अशुद्ध कार्यात्मक भाषा में एक डेटा संरचना का उपयोग विशुद्ध रूप से कार्यात्मक तरीके से किया जाता है, मॉड्यूलर प्रोग्रामिंग या क्लास (कंप्यूटर प्रोग्रामिंग) का उपयोग केवल अधिकृत कार्यों के माध्यम से हेरफेर सुनिश्चित करने के लिए किया जा सकता है।[citation needed]
विशुद्ध रूप से कार्यात्मक डेटा संरचनाओं का उपयोग करना
विशुद्ध रूप से कार्यात्मक डेटा संरचनाओं का उपयोग करने के लिए मौजूदा कोड को अपनाने में केंद्रीय चुनौतियों में से एक यह तथ्य है कि परिवर्तनशील डेटा संरचनाएं उन कार्यों के लिए छिपे हुए आउटपुट प्रदान करती हैं जो उनका उपयोग करते हैं। विशुद्ध रूप से कार्यात्मक डेटा संरचनाओं का उपयोग करने के लिए इन कार्यों को पुनर्लेखन इन डेटा संरचनाओं को स्पष्ट आउटपुट के रूप में जोड़ने की आवश्यकता है।
उदाहरण के लिए, एक फ़ंक्शन पर विचार करें जो एक परिवर्तनशील सूची को स्वीकार करता है, सूची से पहले तत्व को हटाता है और उस तत्व को वापस करता है। विशुद्ध रूप से कार्यात्मक सेटिंग में, सूची से किसी तत्व को हटाने से एक नई और छोटी सूची बनती है, लेकिन मूल को अपडेट नहीं करता है। उपयोगी होने के लिए, इसलिए, इस फ़ंक्शन के पूरी तरह कार्यात्मक संस्करण को हटाए गए तत्व के साथ नई सूची वापस करने की संभावना है। सबसे सामान्य मामले में, इस तरह से परिवर्तित प्रोग्राम को प्रत्येक फ़ंक्शन कॉल से अतिरिक्त परिणाम के रूप में प्रोग्राम की स्थिति या स्टोर को वापस करना होगा। ऐसा कहा जाता है कि इस तरह के प्रोग्राम को स्टोर-पासिंग स्टाइल में लिखा जाता है।
उदाहरण
यहाँ विशुद्ध रूप से कार्यात्मक कार्यान्वयन के साथ सार डेटा संरचनाओं की एक सूची है:
- स्टैक (फर्स्ट इन, लास्ट आउट) अकेले लिंक की गई सूची के रूप में लागू किया गया,
- कतार, एक वास्तविक समय कतार के रूप में कार्यान्वित,
- डबल-एंडेड कतार, रीयल-टाइम डेक के रूप में लागू की गई| रीयल-टाइम डबल-एंडेड कतार,
- सेट (सार डेटा प्रकार) | (बहु) ऑर्डर किए गए तत्वों का सेट और ऑर्डर की गई चाबियों द्वारा अनुक्रमित मानचित्र (कंप्यूटर विज्ञान), लाल-काले पेड़ के रूप में कार्यान्वित किया जाता है, या आमतौर पर एक खोज पेड़ द्वारा लागू किया जाता है,
- प्राथमिकता कतार, ब्रोडल कतार के रूप में कार्यान्वित
- रैंडम एक्सेस लिस्ट, स्क्यू-बाइनरी रैंडम एक्सेस लिस्ट के रूप में लागू की गई
- हैश कंसिंग
- जिपर (डेटा संरचना)
डिजाइन और कार्यान्वयन
कंप्यूटर वैज्ञानिक क्रिस ओकासाकी ने अपनी पुस्तक प्योर्ली फंक्शनल डेटा स्ट्रक्चर्स में विशुद्ध रूप से कार्यात्मक डेटा संरचनाओं को डिजाइन और कार्यान्वित करने के लिए उपयोग की जाने वाली तकनीकों का वर्णन किया है, जिनमें से एक छोटे उपसमुच्चय का सारांश नीचे दिया गया है।
आलस्य और संस्मरण
विशुद्ध रूप से कार्यात्मक भाषा में आलसी मूल्यांकन विशेष रूप से दिलचस्प है[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
