👨🏾‍⚖️ 🚘 ⛷️ विशुद्ध रूप से कार्यात्मक डेटा संरचनाएं 🛬 🧑🏽‍🤝‍🧑🏽 🔒

मैं इसे स्वीकार करता हूं। मुझे वास्तव में विश्वविद्यालय में डेटा संरचनाओं और एल्गोरिदम का कोर्स पसंद नहीं था। ये सभी ढेर, कतारें, ढेर, पेड़, ग्राफ (वे ठीक नहीं हैं) और अस्पष्ट और जटिल डेटा संरचनाओं के अन्य "मजाकिया" नाम मेरे सिर में तय नहीं करना चाहते हैं। एक सच्चे "व्यावहारिक" के रूप में, पहले से ही मेरे दूसरे और तीसरे वर्ष में मैं मानक कक्षा पुस्तकालय में दृढ़ता से विश्वास करता था और हमारे लिए दिए गए संग्रह और कंटेनरों (मात्र नश्वर द्वारा) की प्रार्थना करता था जो कि पिता और महान सीएस दाताओं द्वारा सावधानीपूर्वक बेचे जाते थे। ऐसा लगता था कि जो कुछ भी आविष्कार किया जा सकता था वह लंबे समय से आविष्कार और कार्यान्वित किया गया था।

लगभग एक साल पहले सब कुछ बदल गया जब मुझे पता चला कि एक और दुनिया है। दुनिया हमारे साथ तुमसे अलग है। एक क्लीनर और अधिक पूर्वानुमानित दुनिया। दुष्प्रभावों, उत्परिवर्तन, सरणियों और विनाशकारी अपडेट के बिना एक दुनिया (एक चर के लिए पुनर्मूल्यांकन)। एक ऐसी दुनिया, जहाँ दृढ़ता की सबसे बुद्धिमान रानी उसके और उसकी खूबसूरत बहनों के लिए काम करती है - समारोह और पुनरावृत्ति। मैं एक विशुद्ध रूप से कार्यात्मक दुनिया के बारे में बात कर रहा हूं जहां लगभग सभी ज्ञात डेटा संरचनाओं के अनुमान सामंजस्यपूर्ण रूप से मौजूद हैं, या यहां तक कि जीवित भी हैं।

और अब, मैं आपको इस दुनिया का एक छोटा सा कण दिखाना चाहता हूं। कीहोल के माध्यम से, हम अपने सबसे हड़ताली निवासियों - कार्यात्मक लाल-काले पेड़ (सीपीडी) में से एक की जांच करने के लिए इस अद्भुत दुनिया में एक दूसरे के लिए देखेंगे।

विशुद्ध रूप से कार्यात्मक डेटा संरचनाओं के बारे में

एक वर्ग के रूप में विशुद्ध रूप से कार्यात्मक डेटा संरचनाएं (सीएफएसडी) दो कारणों से मौजूद हैं। सबसे पहले, 99% अनिवार्य कार्यान्वयन के लिए, तथाकथित विनाशकारी अपडेट ठोकर के ब्लॉक हैं (पिछले मूल्य के नुकसान के साथ एक चर के लिए असाइनमेंट)। यह स्पष्ट है कि कार्यात्मक दुनिया में ऐसा परिदृश्य असंभव है, क्योंकि हम हमेशा अपरिवर्तनीय वस्तुओं से निपटते हैं। दूसरे, कार्यात्मक दुनिया में, संग्रह को बदलने के बाद, हम उम्मीद करते हैं कि इसका पिछला संस्करण हमारे पास उपलब्ध रहे। इसलिए शब्द "लगातार वस्तु" - एक वस्तु के कई संस्करणों के लिए समर्थन।

इस प्रकार, एक बस एक कार्यात्मक दुनिया में एक प्रसिद्ध अनिवार्यता को नहीं ले सकता है और पोर्ट कर सकता है। इसकी सीमाओं (कोई अद्यतन नहीं) और आवश्यकताओं (दृढ़ता) के बारे में याद रखना आवश्यक है। इसलिए, कार्यात्मक वातावरण में अनिवार्य कार्यान्वयन को लागू करने की प्रक्रिया कुछ अधिक जटिल और रहस्यमय भी है। और क्रिस ओकासाकी अपने मौलिक काम के साथ - विशुद्ध रूप से कार्यात्मक डेटा संरचनाएं इस कठिन मामले में 15 वर्षों के लिए एक नायाब मास्टर मानी गई हैं।

क्रिस और उनकी किताब के बारे में

1998 में, क्रिस ने सीएफपीएस के विषय पर अपने शोध प्रबंध का बचाव किया और एक साल बाद एक पुस्तक के रूप में शोध प्रकाशित किया। क्रिस की पुस्तक बहुत घनी (सूचनात्मक) और आकर्षक पठन के 200 पृष्ठ हैं। पाठ, जिसकी शैली वैज्ञानिक कार्य और एक बार में एक दोस्त के साथ एक अनौपचारिक बातचीत के बीच की सीमा, सचमुच एक कलात्मक उपन्यास की तरह पढ़ती है। क्रिस का काम सीएफएसडी के क्रियान्वयन में सर्वोत्तम प्रथाओं और दृष्टिकोणों को जोड़ता है, जो कि मानक एमएल और हास्केल में प्रसिद्ध डेटा संरचनाओं के उदाहरणों द्वारा समर्थित है।

दो चाबियों के बारे में

एक चौकस पाठक कहेगा कि ऐसी आवश्यकताओं और सीमाओं के साथ सब कुछ बहुत धीमी गति से होगा। ऐसा लगता है कि दृढ़ता बनाए रखने के लिए कार्यात्मक संग्रह में कोई भी बदलाव इसकी पूरी नकल के साथ है। यह पूरी तरह सच नहीं है। अधिक सटीक - ऐसा बिल्कुल नहीं। नकल वास्तव में मौजूद है, लेकिन बहुत न्यूनतम पैमाने पर। औपचारिक रूप से - केवल जो वास्तव में बदल रहा है उसकी नकल की जाती है। शेष संग्रह (एक बड़े नियम के रूप में) को संस्करणों के बीच साझा किया गया है। ये दो वाक्य विशुद्ध रूप से कार्यात्मक डेटा संरचनाओं को समझने की कुंजी हैं। ये अद्वितीय उपकरण हैं जो एफपी के तेज दिमागों द्वारा आविष्कार और सिद्ध किए गए थे। इन साधनों का नाम पथ की नकल है (केवल संचालन से प्रभावित होता है) और संरचनात्मक साझाकरण (सामान्य भागों को संस्करणों के बीच सुरक्षित रूप से साझा किया जा सकता है, क्योंकि इस तरह का प्रत्येक भाग स्वयं अपरिवर्तनीय है)।

बाइनरी सर्च ट्री के बारे में

शुरू करने के लिए, सामान्य असंतुलित बाइनरी सर्च ट्री (डीबीपी) पर विचार करें, जो कार्यात्मक दुनिया के लिए पोर्ट करना बहुत आसान है। उनकी संरचना इस तरह दिखती है:

abstract sealed class Tree { def value: Int def left: Tree def right: Tree def isEmpty: Boolean } case object Leaf extends Tree { def value: Int = fail("Empty tree.") def left: Tree = fail("Empty tree.") def right: Tree = fail("Empty tree.") def isEmpty: Boolean = true } case class Branch(value: Int, left: Tree = Leaf, right: Tree = Leaf) extends Tree { def isEmpty: Boolean = false }

हम पेस्ट ऑपरेशन में रुचि रखते हैं, जो हमें पथ की नकल और संरचनात्मक साझाकरण उपकरण की ताकत और सुंदरता की पूरी तरह से सराहना करने की अनुमति देगा।

 def add(x: Int): Tree = if (isEmpty) Branch(x) else if (x < value) Branch(value, left.add(x), right) else if (x > value) Branch(value, left, right.add(x)) else this

जैसा कि अनिवार्य एल्गोरिथ्म में, सम्मिलन कार्य एक नए नोड के लिए एक उपयुक्त स्थान खोजने के कार्य को कम कर दिया जाता है। हालांकि, हमारा कार्यात्मक कार्यान्वयन थोड़ा अधिक दिलचस्प होगा। फंक्शन ट्री में इंसर्ट ऑपरेशन दो पास को जोड़ता है - कॉल करने के लिए ऊपर-नीचे की चेन (डालने के लिए जगह की खोज करें) और ब्रांच कंस्ट्रक्टर को कॉल की अप (बॉटम-अप) चेन (सर्च पथ के साथ पेड़ के बदले हुए हिस्से की नकल)। पहला पास (प्रविष्टि बिंदु के लिए शीर्ष-डाउन खोज) अनिवार्य एल्गोरिथ्म का एक स्पष्ट प्रक्षेपण है। हम दूसरी पास (अपस्ट्रीम पथ कॉपी) में रुचि रखते हैं, जो हमारे कार्यान्वयन को पूरी तरह कार्यात्मक (लगातार) बनाता है।

दृढ़ता संपत्ति को संरक्षित करने के लिए, संग्रह के दो संस्करणों का समर्थन करना आवश्यक है - "पहले" और "बाद में" आवेषण। इसलिए, नोड्स की आंतरिक संरचना में कोई भी परिवर्तन उनकी प्रतियों के ऊपर किया जाना चाहिए। पेड़ में सम्मिलन के परिणामस्वरूप, नोड अपडेटिंग (बाएं / दाएं वंश के लिंक को बदलने) की "श्रृंखला प्रतिक्रिया" का एक प्रकार होता है, जो सम्मिलन बिंदु से पेड़ की जड़ तक खोज पथ के साथ फैलता है। यह है कि कोई भी "जादू" का वर्णन कर सकता है कि ऊपर वाला मार्ग लागू करता है, विचारों के संयोजन और पथ की नकल (नोड्स "5" और "7" की नकल करता है) और संरचनात्मक साझाकरण ("1", "2", "3" के साथ सबट्री) संग्रह के दोनों संस्करणों में निहित)।

लाल-काले पेड़ों के बारे में

लाल-काला पेड़ (QCD) एक स्व-संतुलन द्विआधारी खोज वृक्ष है, जिसके लिए दो आक्रमणकारी मान्य हैं:

लाल अपरिवर्तनीय : कोई लाल नोड का लाल पूर्वज नहीं है
ब्लैक इनवेरिएंट : जड़ से पत्ती तक प्रत्येक पथ में काले नोड्स की समान संख्या होती है

इन आक्रमणकारियों की पूर्ति यह सुनिश्चित करती है कि पेड़ लॉग एन की ऊंचाई के साथ संतुलित है, जहां एन पेड़ में नोड्स की संख्या है। दूसरे शब्दों में, PSP पर मुख्य संचालन को लघुगणकीय समय में प्रदर्शन करने की गारंटी है।

1999 तक, कार्यात्मक दुनिया में क्यूसीडी का कोई सवाल नहीं था। अनिवार्य कार्यान्वयन बंदरगाह के लिए बहुत मुश्किल था, क्योंकि यह पूरी तरह से पॉइंटर्स (पॉइंटर्स नरक) के साथ जटिल जोड़तोड़ पर बनाया गया था। इसलिए, उदाहरण के लिए, कॉर्मेन ने आक्रमणकारियों के उल्लंघन के आठ संभावित मामलों और उन्हें खत्म करने के लिए संबंधित उपायों की जांच की। विषय से थोड़ा विचलित होकर, हम यह जोड़ सकते हैं कि अत्यधिक जटिलता के कारण यह ठीक था कि सीपीएच ने वैकल्पिक चीजों के साथ बदलने के लिए हर संभव तरीके से प्रयास किया। उदाहरण के लिए, सेजविक ने एलएलआरबी पेड़ को क्यूसीडी के सरलीकृत संस्करण के रूप में प्रस्तावित किया।

हालांकि, 1999 में, क्रिस ओकासाकी ने एक लेख प्रकाशित किया था जिसमें उन्होंने क्यूसीडी के एक विशुद्ध रूप से कार्यात्मक कार्यान्वयन की शुरुआत की थी। यह लेख अभी भी कार्यात्मक और अनिवार्य प्रोग्रामर दोनों के बीच बहुत मांग में है। तथ्य यह है कि लेख एक बहुत ही सरल और समझने योग्य कार्यान्वयन विचार प्रस्तुत करता है जिसे कोई भी प्रोग्रामर 15 मिनट में समझ सकता है और कार्यक्रम कर सकता है। क्रिस ने कहा कि केवल 4 पैटर्न हैं (नीचे दी गई तस्वीर देखें) जो किसी एक आक्रमणकारी का उल्लंघन करते हैं। और हमारा काम इन पैटर्नों को ढूंढना है और उन्हें एक लाल रंग की जड़ और दो काले बच्चों (चित्र देखें) के साथ एक ही डिज़ाइन में पुनर्निर्माण करना है। और वह सब है। यानी DBP से PSR प्राप्त करने के लिए, यह हमारे लिए इन्सर्ट एल्गोरिथम के दूसरे (अपस्ट्रीम) पास को बदलने के लिए पर्याप्त है। अब दूसरा पास न केवल खोज पथ के साथ नोड्स की प्रतिलिपि बनाना चाहिए, बल्कि यह भी कि अगर सबट्री चार पैटर्न में से एक से मेल खाती है, तो इसे एक सुरक्षित संरचना में पुनर्निर्माण करें। दूसरे शब्दों में, एल्गोरिथ्म में प्रतिलिपि चरण संतुलन चरण के साथ संयुक्त है।

इस दो सरल तथ्यों को जोड़ना कि PSD की जड़ हमेशा काली होती है, और नया नोड हमेशा लाल होता है, हमें निम्नलिखित कोड मिलते हैं:

 def add(x: Int): Tree = { def balancedAdd(t: Tree): Tree = if (t.isEmpty) Tree.make(Red, x) else if (x < t.value) balanceLeft(t.color, t.value, balancedAdd(t.left), t.right) else if (x > t.value) balanceRight(t.color, t.value, t.left, balancedAdd(t.right)) else t def balanceLeft(c: Color, x: Int, l: Tree, r: Tree) = (c, l, r) match { case (Black, Branch(Red, y, Branch(Red, z, a, b), c), d) => Tree.make(Red, y, Tree.make(Black, z, a, b), Tree.make(Black, x, c, d)) case (Black, Branch(Red, z, a, Branch(Red, y, b, c)), d) => Tree.make(Red, y, Tree.make(Black, z, a, b), Tree.make(Black, x, c, d)) case _ => Tree.make(c, x, l, r) } def balanceRight(c: Color, x: A, l: Tree, r: Tree) = (c, l, r) match { case (Black, a, Branch(Red, y, b, Branch(Red, z, c, d))) => Tree.make(Red, y, Tree.make(Black, x, a, b), Tree.make(Black, z, c, d)) case (Black, a, Branch(Red, z, Branch(Red, y, b, c), d)) => Tree.make(Red, y, Tree.make(Black, x, a, b), Tree.make(Black, z, c, d)) case _ => Tree.make(c, x, l, r) } def blacken(t: Tree) = Tree.make(Black, t.value, t.left, t.right) blacken(balancedAdd(this)) }

विचारित कार्यान्वयन में, कुछ और बिंदु होते हैं जिन्हें अतिरिक्त टिप्पणियों की आवश्यकता होती है। सबसे पहले, प्रत्येक ट्री नोड में अतिरिक्त जानकारी होती है - इसका अपना रंग ( color फ़ंक्शन)। दूसरे, balance फ़ंक्शन, जो संतुलन और नकल को लागू करता है, को दो कार्यों ( balanceLeft और balanceRight ) में विभाजित किया जाता है, जो balanceRight बाएं या दाएं सबट्री (केवल खोज पैच के साथ) में balanceRight उल्लंघन का पता लगाने और प्रत्येक पक्ष के लिए दो पैटर्न की प्रक्रिया करने की उम्मीद करता है।

अनिवार्य कार्यान्वयन की जटिलता पर

एक निष्पक्ष सवाल उठता है - क्यों अनिवार्य दुनिया में क्यूसीडी का कार्यान्वयन अधिक जटिल दिखता है? जवाब काफी सरल है - प्रदर्शन दोष देना है। पॉइंटर्स और म्यूटेबल वैरिएबल से निपटने के लिए, हम इसकी शुरुआती पुनरावृत्तियों (कुछ शर्तों के तहत) में संतुलन प्रक्रिया को रोक सकते हैं, जिससे एल्गोरिथ्म का समय कम हो जाएगा। कार्यात्मक वातावरण में, हम सभी प्रभावित नोड्स को कॉपी करने के लिए मजबूर होते हैं, इसलिए उपप्रकार में पैटर्न की उपस्थिति के लिए अनावश्यक जांच हमें ज्यादा परेशान नहीं करती है। निष्पक्षता में, यह प्रतिस्थापित करने योग्य है कि कार्यात्मक क्यूसीडी में डालने के लिए प्रस्तावित एल्गोरिथ्म में समान विषमता है जैसा कि मूल दुनिया से मूल एल्गोरिथ्म - ओ (लॉग एन)।

अगले चरणों के बारे में

मैंने विषय में रुचि रखने वालों के लिए कुछ बेहतरीन लिंक दिए।

शोधकर्ताओं के लिए:

Scala पर उदाहरण के साथ CFSD की मेरी समीक्षा प्रस्तुति (नोवोसिबिर्स्क स्काला बैठक के लिए वीडियो रिपोर्ट)
एक कार्यात्मक दुनिया में एक बाइनरी हीप को पोर्ट करने का मेरा प्रयास
GCDHub पर QCD और अन्य संरचनाओं का कोड
मैट मेयट द्वारा PSD से हटाना
क्रिस ओकासाकी का ब्लॉग

चिकित्सकों के लिए:

इस लेख में एनर एंडरसन ने "2 * d" से "d + 1" तक की तुलना को कम करने का सुझाव दिया, जहां d वृक्ष की गहराई (खोज पथ की लंबाई) है। डीबीपी में सम्मिलित ऑपरेशन को संशोधित करें ताकि यह कम तुलना का उपयोग करे।
एक फ़ंक्शन fromOrderedList जो एक सॉर्ट की गई सूची से एक संतुलित डीबीपी बनाता है। संकेत: हिंज, राल्फ। 1999 "लाल-काले पेड़ों का निर्माण"।

विशुद्ध रूप से कार्यात्मक डेटा संरचनाएं