कुछ दिन पहले हुआ था हाइड्रा सम्मेलन. JUG.ru ग्रुप के लोगों ने ड्रीम स्पीकर्स (लेस्ली लैमपोर्ट! क्लिफ क्लिक! मार्टिन क्लेपमैन!) को आमंत्रित किया और वितरित सिस्टम और कंप्यूटिंग के लिए दो दिन समर्पित किए। कोंटूर सम्मेलन के तीन भागीदारों में से एक था। हमने बूथ पर बात की, अपने वितरित भंडारण के बारे में बात की, बिंगो खेला और पहेलियाँ सुलझाईं।

यह उनके पाठ के लेखक द्वारा कोंटूर स्टैंड पर कार्यों के विश्लेषण के साथ एक पोस्ट है। हाइड्रा पर कौन था - यह सुखद अनुभव को याद करने का आपका कारण है, कौन नहीं था - अपने दिमाग को फैलाने का मौका बड़ा हे-नोटेशन.

ऐसे प्रतिभागी भी थे जिन्होंने अपना निर्णय लिखने के लिए फ्लिपचार्ट को स्लाइडों में तोड़ दिया। मैं मजाक नहीं कर रहा हूं - उन्होंने सत्यापन के लिए कागज का यह ढेर सौंप दिया:

कुल तीन कार्य थे:

• भार संतुलन के लिए वजन के आधार पर प्रतिकृतियां चुनने के बारे में
• इन-मेमोरी डेटाबेस के विरुद्ध क्वेरी परिणामों को क्रमबद्ध करने के बारे में
• रिंग टोपोलॉजी के साथ वितरित प्रणाली में राज्य स्थानांतरण पर

कार्य 1. क्लस्टरक्लाइंट

वितरित प्रणाली के एन भारित प्रतिकृतियों से के के कुशल चयन के लिए एक एल्गोरिदम प्रस्तावित करना आवश्यक था:

आपकी टीम को एन नोड्स के व्यापक रूप से वितरित क्लस्टर के लिए क्लाइंट लाइब्रेरी विकसित करने का काम सौंपा गया है। लाइब्रेरी नोड्स से जुड़े विभिन्न मेटाडेटा (उदाहरण के लिए, उनकी विलंबता, 4xx/5xx प्रतिक्रिया दर, आदि) का ट्रैक रखेगी और उन्हें फ़्लोटिंग पॉइंट वेट W1..WN असाइन करेगी। समवर्ती निष्पादन रणनीति का समर्थन करने के लिए, लाइब्रेरी को N नोड्स में से K को यादृच्छिक रूप से चुनने में सक्षम होना चाहिए - चयनित होने की संभावना नोड के वजन के अनुपात में होनी चाहिए।

नोड्स को कुशलतापूर्वक चुनने के लिए एक एल्गोरिदम का प्रस्ताव करें। बड़े O नोटेशन का उपयोग करके इसकी कम्प्यूटेशनल जटिलता का अनुमान लगाएं।

सब कुछ अंग्रेजी में क्यों है?

क्योंकि इस रूप में सम्मेलन के प्रतिभागियों ने उनसे लड़ाई की और क्योंकि अंग्रेजी हाइड्रा की आधिकारिक भाषा थी। कार्य इस प्रकार दिखे:

कागज और पेंसिल लें, सोचें, तुरंत स्पॉइलर खोलने में जल्दबाजी न करें 🙂

समाधान का विश्लेषण (वीडियो)

5:53 से शुरू, केवल 4 मिनट:

और यहां बताया गया है कि फ्लिपचार्ट वाले लोगों ने अपना समाधान कैसे पेश किया:

समाधान का विश्लेषण (पाठ)

निम्नलिखित समाधान सतह पर है: सभी प्रतिकृतियों के वजन का योग करें, सभी वजनों के योग के लिए 0 से एक यादृच्छिक संख्या उत्पन्न करें, फिर एक आई-प्रतिकृति चुनें जैसे कि प्रतिकृति वजन का योग 0 से (i-1) वें तक हो एक यादृच्छिक संख्या से कम है, और 0 से i-वें तक प्रतिकृति भार का योग - इससे अधिक है। इसलिए एक प्रतिकृति का चयन करना संभव होगा, और अगले का चयन करने के लिए, आपको चयनित प्रतिकृति पर विचार किए बिना पूरी प्रक्रिया को दोहराना होगा। ऐसे एल्गोरिदम के साथ, एक प्रतिकृति चुनने की जटिलता O(N) है, K प्रतिकृतियां चुनने की जटिलता O(N K) ~ O(N2) है।

द्विघात जटिलता ख़राब है, लेकिन इसमें सुधार किया जा सकता है। ऐसा करने के लिए, हम निर्माण करेंगे खंड वृक्ष वज़न के योग के लिए. गहराई एलजी एन का एक पेड़ प्राप्त किया जाएगा, जिसकी पत्तियों में प्रतिकृति भार होंगे, और शेष नोड्स में - आंशिक योग, पेड़ की जड़ पर सभी भारों के योग तक। इसके बाद, हम सभी भारों के योग के लिए 0 से एक यादृच्छिक संख्या उत्पन्न करते हैं, i-वें प्रतिकृति ढूंढते हैं, इसे पेड़ से हटाते हैं, और शेष प्रतिकृतियां ढूंढने के लिए प्रक्रिया दोहराते हैं। इस एल्गोरिथ्म के साथ, एक पेड़ बनाने की जटिलता O(N) है, i-th प्रतिकृति खोजने और उसे पेड़ से हटाने की जटिलता O(lg N) है, K प्रतिकृतियां चुनने की जटिलता O(N + K) है एलजी एन) ~ ओ(एन एलजी एन)।

रैखिक-लॉग जटिलता द्विघात जटिलता से बेहतर है, विशेष रूप से बड़े K के लिए।

यह यह एल्गोरिथम है कोड में लागू किया गया प्रोजेक्ट से क्लस्टरक्लाइंट लाइब्रेरीज़ "पूर्व". (वहां, पेड़ O(N lg N) में बनाया गया है, लेकिन यह एल्गोरिदम की अंतिम जटिलता को प्रभावित नहीं करता है।)

कार्य 2. ज़ेबरा

मनमाने ढंग से गैर-अनुक्रमित फ़ील्ड द्वारा स्मृति में दस्तावेज़ों की कुशल सॉर्टिंग के लिए एक एल्गोरिदम प्रस्तावित करना आवश्यक था:

आपकी टीम को एक साझा इन-मेमोरी दस्तावेज़ डेटाबेस विकसित करने का काम सौंपा गया है। एक सामान्य कार्यभार आकार M (आमतौर पर N <100 << M) के संग्रह से एक मनमाने ढंग से (गैर-अनुक्रमित) संख्यात्मक फ़ील्ड द्वारा क्रमबद्ध शीर्ष N दस्तावेज़ों का चयन करना होगा। शीर्ष एस दस्तावेज़ों (एस ~ एन) को छोड़ने के बाद शीर्ष एन का चयन करना थोड़ा कम सामान्य कार्यभार होगा।

ऐसे प्रश्नों को कुशलतापूर्वक निष्पादित करने के लिए एक एल्गोरिदम का प्रस्ताव करें। औसत मामले और सबसे खराब स्थिति में बड़े O नोटेशन का उपयोग करके इसकी कम्प्यूटेशनल जटिलता का अनुमान लगाएं।

समाधान का विश्लेषण (वीडियो)

34:50 से शुरू होकर, केवल 6 मिनट:

समाधान का विश्लेषण (पाठ)

सतही समाधान: सभी दस्तावेज़ों को क्रमबद्ध करें (उदाहरण के लिए जल्दी से सुलझाएं), फिर एन+एस दस्तावेज़ लें। इस मामले में, सॉर्टिंग की जटिलता औसतन O(M lg M) है, सबसे खराब स्थिति में O(M2) है।

यह स्पष्ट है कि सभी एम दस्तावेजों को छांटना और फिर उनका केवल एक छोटा सा हिस्सा लेना अक्षम्य है। सभी दस्तावेज़ों को क्रमबद्ध न करने के लिए, एक एल्गोरिदम उपयुक्त है quickselect, जो आवश्यक दस्तावेज़ों में से N+S का चयन करेगा (इन्हें किसी भी एल्गोरिथम द्वारा क्रमबद्ध किया जा सकता है)। इस मामले में, जटिलता औसतन घटकर O(M) हो जाएगी, जबकि सबसे खराब स्थिति वही रहेगी।

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

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

कार्य 3. राज्य की अदला-बदली

राज्यों को स्थानांतरित करने के लिए सबसे कुशल एल्गोरिदम प्रस्तावित करना आवश्यक था:

आपकी टीम को एन नोड्स के वितरित क्लस्टर के लिए एक फैंसी राज्य विनिमय तंत्र विकसित करने का काम सौंपा गया है। i-वें नोड की स्थिति को (i+1)-वें नोड में स्थानांतरित किया जाना चाहिए, N-वें नोड की स्थिति को पहले नोड में स्थानांतरित किया जाना चाहिए। एकमात्र समर्थित ऑपरेशन राज्य स्वैप है जब दो नोड्स परमाणु रूप से अपने राज्यों का आदान-प्रदान करते हैं। यह ज्ञात है कि एक राज्य स्वैप में एम मिलीसेकंड लगते हैं। प्रत्येक नोड किसी भी समय एकल राज्य स्वैप में भाग लेने में सक्षम है।

एक क्लस्टर में सभी नोड्स की स्थिति को स्थानांतरित करने में कितना समय लगता है?

समाधान का विश्लेषण (पाठ)

सतही समाधान: पहले और दूसरे तत्व की अवस्थाओं का आदान-प्रदान करें, फिर पहले और तीसरे का, फिर पहले और चौथे का, इत्यादि। प्रत्येक आदान-प्रदान के बाद, एक तत्व की स्थिति वांछित स्थिति में होगी। आपको O(N) क्रमपरिवर्तन करना होगा और O(N M) समय व्यतीत करना होगा।

रैखिक समय लंबा है, इसलिए आप जोड़े में तत्वों की स्थिति का आदान-प्रदान कर सकते हैं: पहला दूसरे के साथ, तीसरा चौथे के साथ, और इसी तरह। प्रत्येक राज्य विनिमय के बाद, प्रत्येक दूसरा तत्व सही स्थिति में होगा। आपको O(lg N) क्रमपरिवर्तन करना होगा और O(M lg N) समय व्यतीत करना होगा।

हालाँकि, बदलाव को और भी अधिक कुशल बनाना संभव है - रैखिक में नहीं, बल्कि निरंतर समय में। ऐसा करने के लिए, पहले चरण में, आपको पहले तत्व की स्थिति को अंतिम के साथ, दूसरे को अंतिम के साथ, और इसी तरह से बदलना होगा। अंतिम तत्व की स्थिति सही स्थिति में होगी. और अब हमें दूसरे तत्व की स्थिति को अंतिम के साथ, तीसरे को अंतिम के साथ, और इसी तरह से बदलना होगा। आदान-प्रदान के इस दौर के बाद, सभी तत्वों की स्थिति सही स्थिति में होगी। कुल मिलाकर O(2M) ~ O(1) क्रमपरिवर्तन होंगे।

ऐसा समाधान किसी गणितज्ञ को बिल्कुल भी आश्चर्यचकित नहीं करेगा जो अभी भी याद रखता है कि एक घूर्णन दो अक्षीय समरूपताओं का एक संयोजन है। वैसे, इसे एक बदलाव के लिए नहीं, बल्कि K <N पदों द्वारा बदलाव के लिए तुच्छ रूप से सामान्यीकृत किया गया है। (टिप्पणियों में लिखें कि वास्तव में कैसे।)

क्या आपको पहेलियाँ पसंद आईं? क्या आप अन्य समाधान जानते हैं? टिप्पणियों में साझा करें.

और अंत में यहां कुछ उपयोगी लिंक दिए गए हैं:

• बारे में और सीखो बुनियादी ढांचे का विकास समोच्च में
• आंतरिक के रिकॉर्ड देखें रिपोर्ट के साथ फ़्लायर वितरित प्रणालियों के बारे में
• वीडियो व्याख्यान की श्रृंखला देखेंआम लोगों के लिए असामान्य एल्गोरिदम»
• हमारी सदस्यता लें टेलीग्राम में चैनल

स्रोत: www.habr.com