💇🏼 👩‍👩‍👧‍👧 ▪️ असहमति की प्रणाली सेट और उसके अनुप्रयोग 🧔🏾 🚷 😛

शुभ दोपहर, हबरहाब। एल्गोरिदम और डेटा संरचनाओं की जानकारी के साथ सबसे बड़े आईटी संसाधन के डेटाबेस को समृद्ध करने के लिए मेरे कार्यक्रम के ढांचे में यह एक और पोस्ट है। जैसा कि अभ्यास से पता चलता है, यह जानकारी कई लोगों के लिए पर्याप्त नहीं है, और आवश्यकता प्रोग्रामिंग जीवन के सबसे विविध क्षेत्रों में पाई जाती है।

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

शर्त

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

हम कार्य को औपचारिक बनाते हैं: एक तेज संरचना बनाने के लिए जो निम्नलिखित कार्यों का समर्थन करती है:

मेकसेट (एक्स) - संरचना में एक नया एक्स तत्व पेश करता है, इसके लिए खुद से आकार 1 का एक सेट बनाएं।

ढूँढें (X) - उस सेट के पहचानकर्ता को लौटाएँ जिसमें तत्व X सम्‍मिलित है। एक पहचानकर्ता के रूप में, हम इस सेट से एक तत्व चुनेंगे - सेट का प्रतिनिधि । यह गारंटी है कि एक ही सेट के लिए प्रतिनिधि एक ही लौटेगा, अन्यथा संरचना के साथ काम करना संभव नहीं होगा: यहां तक कि if (Find(X) == Find(Y))

दो तत्व एक ही सेट से संबंधित हैं, if (Find(X) == Find(Y))

भी जांचें if (Find(X) == Find(Y))

सही नहीं होगी।

यूनाइट (एक्स, वाई) - दो सेटों को मिलाते हैं जिसमें तत्व एक्स और वाई एक नए में झूठ बोलते हैं।

आकृति में मैं ऐसी काल्पनिक संरचना के संचालन का प्रदर्शन करूंगा।

कार्यान्वयन

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

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

शुरू करने के लिए, हमें एक सरणी p की आवश्यकता होती है, जो कि पेड़ के प्रत्येक शीर्ष पर उसके तत्काल पूर्वज (और पेड़ X, स्वयं की जड़ के लिए) को संग्रहीत करता है। अकेले इस सरणी का उपयोग करके, आप पहले दो DSU संचालन को प्रभावी ढंग से लागू कर सकते हैं:

मेकसेट (X)

एक तत्व एक्स से एक नया पेड़ बनाने के लिए, यह इंगित करने के लिए पर्याप्त है कि यह अपने पेड़ की जड़ है, और इसका कोई पूर्वज नहीं है।

 public void MakeSet(int x) { p[x] = x; }

खोजें (X)

एक पेड़ के प्रतिनिधि को इसकी जड़ माना जाएगा। फिर, इस प्रतिनिधि को खोजने के लिए, मूल लिंक तक जाने के लिए पर्याप्त है जब तक कि हम जड़ पर ठोकर नहीं खाते।

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

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

आंकड़ा (3) ऑपरेशन से पहले और बाद में पेड़ को दर्शाता है। लाल पसली - वे जिनके साथ हम जड़ के रास्ते पर चले। अब वे पुनर्निर्देशित हो गए हैं। ध्यान दें कि उसके बाद पेड़ की ऊंचाई कितनी घट गई।

पुनरावर्ती रूप में स्रोत कोड लिखना काफी सरल है:

 public int Find(int x) { if (p[x] == x) return x; return p[x] = Find(p[x]); }

यूनाइट (X, Y)

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

सवाल उठता है: किस पेड़ को लटका देना है? ट्री एक्स कहना हमेशा अच्छा नहीं होता है: यह एक उदाहरण खोजना आसान है, जहां एन यूनियनों के बाद, हमें पतित पेड़ मिलता है - एन तत्वों की एक शाखा। और यहां दूसरा डीएसयू हेयुरिस्टिक आता है, जिसका उद्देश्य पेड़ों की ऊंचाई को कम करना है।

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

अब एक मर्ज निर्णय लेना आसान है: उन शाखाओं को रोकने के लिए जो डीएसयू में बहुत लंबे हैं, हम एक उच्चतर से निचले पेड़ को लटकाएंगे। यदि उनकी ऊंचाइयां समान हैं - इससे कोई फर्क नहीं पड़ता कि किससे किसको लटका दिया जाए। लेकिन बाद के मामले में, नए बने रूट को रैंक बढ़ाने के लिए नहीं भूलना चाहिए।

यह कैसे एक विशिष्ट यूनाइट का उत्पादन किया जाता है (उदाहरण के लिए, 8 और 19 के मापदंडों के साथ):

 public void Unite(int x, int y) { x = Find(x); y = Find(y); if (rank[x] < rank[y]) p[x] = y; else { p[y] = x; if (rank[x] == rank[y]) ++rank[x]; } }

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

सी # कार्यान्वयन:

 public void Unite(int x, int y) { x = Find(x); y = Find(y); if (rand.Next() % 2 == 0) Swap(ref x, ref y); p[x] = y; }

गति

दो अनुमानों के उपयोग के कारण, प्रत्येक ऑपरेशन की गति दृढ़ता से पेड़ की संरचना पर निर्भर करती है, और पहले किए गए संचालन की सूची में पेड़ की संरचना पर निर्भर करती है। एकमात्र अपवाद मेकसेट है - इसका संचालन समय स्पष्ट रूप से हे (1) है :-) अन्य दो के लिए, गति बहुत ही स्पष्ट है।

रॉबर्ट टेरियन ने 1975 में एक उल्लेखनीय तथ्य साबित किया: एन के आकार वन पर फाइंड एंड यूनाइट दोनों का परिचालन समय ओ (α (एन)) है।

गणित में α (N) के तहत उलटा एकरमैन फंक्शन है, अर्थात, f (N) = A (N, N) के लिए फ़ंक्शन व्युत्क्रम है। एकरमैन के कार्य A (N, M) को कोलोसल वृद्धि दर के लिए जाना जाता है। उदाहरण के लिए, ए (4, 4) = 2 ^{2 ^{2 ⁶⁵⁵³⁶}} -3 , यह संख्या वास्तव में बहुत बड़ी है। सामान्य तौर पर, एन के सभी बोधगम्य व्यावहारिक मूल्यों के लिए, इसका व्युत्क्रम एकरमैन फ़ंक्शन 5 से अधिक नहीं होता है। इसलिए, हम इसे एक स्थिर के रूप में ले सकते हैं और ओ (α (एन)) (O (1) मान सकते हैं।

तो हमारे पास है:

मेकसेट (एक्स) - ओ (1)।

ढूँढें (X) - O (1) परिशोधन है।

यूनाइट (X, Y) - O (1) परिशोधन।

मेमोरी खपत - ओ (एन)।

बुरा नहीं है :-)

व्यावहारिक अनुप्रयोग

डीएसयू के लिए बड़ी संख्या में विभिन्न उपयोग हैं। उनमें से अधिकांश ऑफ़लाइन कुछ समस्या को हल करने से संबंधित हैं - अर्थात, जब प्रोग्राम को प्राप्त संरचना के बारे में प्रश्नों की सूची पहले से ज्ञात है। मैं यहाँ समाधान के लिए संक्षिप्त विचारों के साथ इन कार्यों में से कुछ दे दूँगा।

न्यूनतम वजन का कंकाल

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

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

आंकड़ा एक हाइलाइट किए गए न्यूनतम कंकाल के साथ एक भारित ग्राफ दिखाता है।

इस समस्या को हल करने के लिए क्रुस्कल का एल्गोरिथ्म: हम सभी किनारों को वजन के बढ़ते क्रम में क्रमबद्ध करते हैं और हम DSU का उपयोग करके न्यूनतम वजन के वर्तमान जंगल को बनाए रखेंगे। प्रारंभ में, एक डीएसयू में एन पेड़ होते हैं, प्रत्येक में एक शीर्ष। हम आरोही क्रम में पसलियों के साथ जाते हैं; यदि वर्तमान धार अलग-अलग घटकों को जोड़ती है, तो उन्हें एक में मिला दें और किनारे को कोर के एक तत्व के रूप में याद रखें। जैसे ही घटकों की संख्या एकता तक पहुंचती है - हमने वांछित पेड़ का निर्माण किया।

टारजन की एलसीए ऑफ़लाइन खोज एल्गोरिदम

एक पेड़ और फार्म के प्रश्नों का एक सेट दिया गया: दिए गए यू और वी के लिए, अपने निकटतम सामान्य पूर्वज (कम से कम सामान्य पूर्वज, LCA) को वापस करें। प्रश्नों का पूरा सेट अग्रिम में जाना जाता है, अर्थात कार्य ऑफ़लाइन तैयार किया गया है।

चलो एक पेड़ में गहराई से खोज करके शुरू करते हैं। कुछ प्रश्न <u, v> पर विचार करें। खोज को गहराई से ऐसी स्थिति में आने दें कि अनुरोध में से एक वर्टिस (यू कहें) पहले से ही खोज के द्वारा पहले ही देखी जा चुकी है, और अब खोज में वर्तमान शीर्ष v है, पूरे उप-प्रकार v की अभी जांच की गई है। जाहिर है, अनुरोध की प्रतिक्रिया या तो स्वयं वी या उसके पूर्वजों में से कुछ होगी। इसके अलावा, रूट के रास्ते में पूर्वजों में से प्रत्येक v के लिए यू का एक निश्चित वर्ग उत्पन्न करता है, जिसके लिए यह उत्तर है: यह वर्ग ऐसे पूर्वजों के "बाईं ओर" पहले से ही देखी गई पेड़ की शाखा के बराबर है।

आंकड़े में, आप एक पेड़ को कक्षाओं में विभाजन के साथ देख सकते हैं, जबकि सफेद कोने अभी तक नहीं देखे गए हैं।

इस तरह के कोने की कक्षाएं प्रतिच्छेदन नहीं करती हैं, जिसका अर्थ है कि उन्हें डीएसयू में समर्थित किया जा सकता है। जैसे ही गहराई खोज सबट्री से लौटती है, इस वर्ट्री के वर्ग को वर्तमान वर्टेक्स के वर्ग के साथ मिला दें। और एक उत्तर की खोज करने के लिए, पूर्वज सरणी का समर्थन करें - प्रत्येक शीर्ष के लिए, पूर्वज उचित, जिसने इस शीर्ष के वर्ग को उत्पन्न किया। प्रतिनिधि के लिए इस सरणी का सेल मान पेड़ों को विलय करते समय फिर से लिखना नहीं भूलना चाहिए। लेकिन अब, प्रत्येक पूरी तरह से संसाधित शीर्ष v के लिए गहराई से खोज करने की प्रक्रिया में, हम क्वेरी सूची में सभी <u, v>, जहां यू पहले से ही संसाधित है, और उत्तर का उत्पादन कर सकते हैं: Ancestor[Find(u)]

।

मल्टीग्राफ में कनेक्टिविटी घटक

एक मल्टीग्राफ दिया जाता है (एक ग्राफ जिसमें एक जोड़े को एक से अधिक सीधा किनारे से जोड़ा जा सकता है), जिससे फॉर्म के प्रश्न "कुछ किनारे हटाएं" और "ग्राफ में कितने जुड़े घटक हैं?" प्राप्त होते हैं। प्रश्नों की पूरी सूची अग्रिम में जानी जाती है।

इसका समाधान है। सबसे पहले, हम सभी निष्कासन अनुरोधों को निष्पादित करेंगे, अंतिम ग्राफ़ में घटकों की संख्या की गणना करेंगे, और इसे याद रखेंगे। हम परिणामस्वरूप ग्राफ को DSU में धकेलेंगे। अब हम रिवर्स ऑर्डर में हटाने के अनुरोधों पर जाएंगे: पुराने ग्राफ़ से प्रत्येक किनारे को हटाने का मतलब है कि हमारे "फ्लैशबैक ग्राफ" में दो घटकों का संभावित विलय डीएसयू में संग्रहीत है; इस स्थिति में, कनेक्टेड घटकों की वर्तमान संख्या एक से घट जाती है।

छवि विभाजन

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

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

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

भूलभुलैया पीढ़ी

कार्य: एक इनपुट और एक आउटपुट के साथ एक भूलभुलैया उत्पन्न करते हैं।

समाधान एल्गोरिथम:

चलो राज्य के साथ शुरू करते हैं जब प्रवेश और निकास को छोड़कर सभी दीवारें स्थापित होती हैं।

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

हम अभिसरण की एक निश्चित स्थिति में प्रक्रिया जारी रखते हैं: उदाहरण के लिए, जब इनपुट और आउटपुट जुड़े होते हैं; या जब एक घटक रहता है।

एकल पास एल्गोरिदम

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

विकल्प # 1: पथ विभाजन । शीर्ष X से रूट पर जाने पर, अपने पूर्वज से पूर्वज (पूर्वज) के पूर्वज (दादा) के लिए प्रत्येक शीर्ष के मूल कनेक्शन को पुनर्निर्देशित करें।

विकल्प संख्या 2: पथ-निर्माण । पथ विभाजन के बारे में विचार करें, हालाँकि, मार्ग के सभी शीर्षों का पुनर्निर्देशन कनेक्शन नहीं है, लेकिन केवल वे हैं जिन पर हम पुनर्निर्देशित करते हैं - अर्थात् "दादाजी"।

उसी पेड़ को आकृति में लिया गया है, इसमें ढूंढें (3) क्वेरी निष्पादित की गई है। केंद्र में, परिणाम पथ विभाजन का उपयोग करके दिखाया गया है, दाईं ओर पथ पर चल रहा है।

क्रियात्मक कार्यान्वयन

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

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

कार्यान्वयन का मुख्य विचार "लगातार सरणियों" को लागू करने वाले डेटा संरचनाओं का उपयोग है: वे सरणियों के समान संचालन का समर्थन करते हैं, लेकिन वे अभी भी मेमोरी को संशोधित नहीं करते हैं, लेकिन परिवर्तित संरचना को वापस करते हैं। कुछ पेड़ का उपयोग करके इस तरह की एक सरणी को आसानी से लागू किया जा सकता है, हालांकि, इस मामले में, इसके साथ संचालन ओ (लॉग ₂ एन) समय लेगा, और डीएसयू के लिए ऐसा अनुमान पहले से ही अत्यधिक बड़ा है।

आगे के तकनीकी विवरणों के लिए, पाठकों को मूल लेख में संदर्भित किया जाता है।

साहित्य

इस लेख के दायरे में असहमति सेट की प्रणालियों की चर्चा प्रसिद्ध पुस्तक - कोरमेन, लिसेर्सन, रिवेस्ट, स्टीन "एल्गोरिथम: निर्माण और विश्लेषण में की गई है।" वहां आप यह भी सबूत पा सकते हैं कि संचालन के निष्पादन में α (N) समय लगता है।

मैक्सिम इवानोव की साइट पर , आप डीएसयू का पूर्ण कार्यान्वयन सी ++ में पा सकते हैं।

यूनियन-फाइंड प्रॉब्लम लेख के लिए प्रतीक्षा-मुक्त समानांतर एल्गोरिदम डीएसयू कार्यान्वयन के समानांतर संस्करण पर चर्चा करता है। इसमें थ्रेड लॉक नहीं हैं।

आप सभी का ध्यान के लिए धन्यवाद :-)

असहमति की प्रणाली सेट और उसके अनुप्रयोग