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

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

त्यहाँ सहभागीहरू पनि थिए जसले फ्लिपचार्टलाई स्लाइडमा भत्काएर आफ्नो निर्णय लेख्न थाले। म मजाक गरिरहेको छैन - तिनीहरूले प्रमाणीकरणको लागि कागजको यो स्ट्याक दिए:

त्यहाँ कुल तीन कार्यहरू थिए:

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

कार्य १. क्लस्टर क्लाइन्ट

वितरित प्रणालीको N भारित प्रतिकृतिहरूबाट K को कुशल चयनको लागि एल्गोरिदम प्रस्ताव गर्न आवश्यक थियो:

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

नोडहरू कुशलतापूर्वक चयन गर्न एल्गोरिदम प्रस्ताव गर्नुहोस्। ठूलो ओ नोटेशन प्रयोग गरेर यसको कम्प्युटेसनल जटिलता अनुमान गर्नुहोस्।

किन सबै कुरा अंग्रेजीमा छ?

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

कागज र पेन्सिल लिनुहोस्, सोच्नुहोस्, तुरुन्तै बिगार्नेहरू खोल्न हतार नगर्नुहोस् 🙂

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

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

र यहाँ कसरी फ्लिपचार्टका साथ केटाहरूले उनीहरूको समाधान पिच गरे:

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

तलको समाधान सतहमा छ: सबै प्रतिकृतिहरूको तौलको योगफल, ० देखि सबै तौलहरूको योगफलमा अनियमित संख्या उत्पन्न गर्नुहोस्, त्यसपछि ० देखि (i-१) औं प्रतिकृति वजनहरूको योगफलको रूपमा i-प्रतिकृति छान्नुहोस्। अनियमित संख्या भन्दा कम छ, र प्रतिकृति वजन को योग ० देखि i-th सम्म - यो भन्दा बढी। त्यसैले एउटा प्रतिकृति चयन गर्न सम्भव हुनेछ, र अर्को चयन गर्न, तपाईंले चयन गरिएको प्रतिकृतिलाई विचार नगरी सम्पूर्ण प्रक्रिया दोहोर्याउन आवश्यक छ। यस्तो एल्गोरिदमको साथ, एउटा प्रतिकृति छनौट गर्ने जटिलता O(N), K प्रतिकृतिहरू छनौट गर्ने जटिलता O(N K) ~ O(N0) हो।

क्वाड्राटिक जटिलता खराब छ, तर यसलाई सुधार गर्न सकिन्छ। यो गर्न, हामी निर्माण गर्नेछौं खण्ड रूख वजन को राशि को लागी। गहिराई lg N को रूख प्राप्त गरिनेछ, जसको पातहरूमा प्रतिकृति वजनहरू हुनेछन्, र बाँकी नोडहरूमा - आंशिक योगफल, रूखको जरामा सबै वजनहरूको योगफलसम्म। त्यसपछि, हामी ० देखि सबै तौलहरूको योगफलमा अनियमित संख्या उत्पन्न गर्छौं, i-th प्रतिकृति फेला पार्छौं, यसलाई रूखबाट हटाउँछौं, र बाँकी प्रतिकृतिहरू फेला पार्न प्रक्रिया दोहोर्याउँछौं। यस एल्गोरिदमको साथ, रूख निर्माण गर्ने जटिलता O(N), i-th प्रतिकृति फेला पार्ने र रूखबाट हटाउने जटिलता O(lg N), K प्रतिकृतिहरू छनौट गर्ने जटिलता O(N + K) हो। lg N) ~ O(N lg N)।

रैखिक-लग जटिलता द्विघात जटिलता भन्दा राम्रो छ, विशेष गरी ठूलो K को लागी।

यो यो एल्गोरिथ्म हो कोडमा लागू गरियो परियोजनाबाट क्लस्टर क्लाइन्ट पुस्तकालयहरू "पूर्व"। (त्यहाँ, रूख O(N lg N) मा बनाइएको छ, तर यसले एल्गोरिथ्मको अन्तिम जटिलतालाई असर गर्दैन।)

कार्य २. जेब्रा

यो एक स्वेच्छाचारी गैर-अनुक्रमणित क्षेत्र द्वारा मेमोरीमा कागजातहरूको कुशल क्रमबद्ध गर्नको लागि एल्गोरिथ्म प्रस्ताव गर्न आवश्यक थियो:

तपाइँको टोलीलाई एक शार्डेड इन-मेमोरी कागजात डाटाबेस विकास गर्ने जिम्मा दिइएको छ। एक सामान्य कार्यभार M (सामान्यतया N <100 << M) साइजको सङ्कलनबाट स्वेच्छाचारी (गैर-अनुक्रमणिका) संख्यात्मक क्षेत्रद्वारा क्रमबद्ध शीर्ष N कागजातहरू चयन गर्नु हो। एक थोरै कम सामान्य कार्यभार शीर्ष S कागजातहरू (S ~ N) छोडे पछि शीर्ष N चयन गर्न हुनेछ।

त्यस्ता प्रश्नहरूलाई प्रभावकारी रूपमा कार्यान्वयन गर्न एल्गोरिदम प्रस्ताव गर्नुहोस्। औसत केस र सबैभन्दा खराब अवस्थाहरूमा ठूलो O नोटेशन प्रयोग गरेर यसको कम्प्युटेसनल जटिलता अनुमान गर्नुहोस्।

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

34:50 मा सुरु, केवल 6 मिनेट:

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

सतह समाधान: सबै कागजातहरू क्रमबद्ध गर्नुहोस् (उदाहरणका लागि quigsort), त्यसपछि N+S कागजातहरू लिनुहोस्। यस अवस्थामा, क्रमबद्ध गर्ने जटिलता औसत O(M lg M), सबैभन्दा खराब O(M2) मा हुन्छ।

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

यद्यपि, तपाइँ यसलाई अझ कुशलतापूर्वक गर्न सक्नुहुन्छ - एल्गोरिथ्म प्रयोग गर्नुहोस् बाइनरी हिप स्ट्रिमिङ। यस अवस्थामा, पहिलो N+S कागजातहरू न्यूनतम- वा अधिकतम-हिप (क्रमबद्ध दिशामा निर्भर गर्दै) मा थपिन्छन्, र त्यसपछि प्रत्येक अर्को कागजातलाई रूखको मूलसँग तुलना गरिन्छ, जसमा हालको न्यूनतम वा अधिकतम कागजात समावेश छ, र आवश्यक भएमा रूखमा थपिन्छ। यस अवस्थामा, सबैभन्दा खराब अवस्थामा जटिलता, जब तपाईले रूखलाई निरन्तर पुन: निर्माण गर्नु पर्छ, O(M lg M) हो, औसतमा जटिलता O(M) हो, जस्तै Quickselect सँग।

यद्यपि, हिप स्ट्रिमिङ अधिक प्रभावकारी हुन जान्छ किनभने व्यवहारमा अधिकांश कागजातहरू यसको मूल तत्वसँग एकल तुलना पछि हिपलाई पुन: निर्माण नगरी खारेज गर्न सकिन्छ। यस्तो क्रमबद्धता कोन्टुरमा विकसित र प्रयोग गरिएको जेब्रा इन-मेमोरी कागजात डेटाबेसमा लागू गरिएको छ।

कार्य 3. राज्य स्वैप

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

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

क्लस्टरमा सबै नोडहरूको राज्यहरू स्थानान्तरण गर्न कति समय लाग्छ?

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

सतह समाधान: पहिलो र दोस्रो तत्वको अवस्थाहरू, त्यसपछि पहिलो र तेस्रो, त्यसपछि पहिलो र चौथो, र यस्तै अन्य। प्रत्येक आदानप्रदान पछि, एक तत्वको अवस्था वांछित स्थितिमा हुनेछ। तपाईंले O(N) क्रमपरिवर्तन गर्नु पर्छ र O(N M) समय खर्च गर्नुपर्छ।

रैखिक समय लामो छ, त्यसैले तपाइँ जोडीहरूमा तत्वहरूको अवस्था आदानप्रदान गर्न सक्नुहुन्छ: पहिलो दोस्रोसँग, तेस्रो चौथोसँग, र यस्तै। प्रत्येक राज्य विनिमय पछि, प्रत्येक दोस्रो तत्व सही स्थितिमा हुनेछ। तपाईंले O(lg N) क्रमपरिवर्तन गर्नु पर्छ र O(M lg N) समय खर्च गर्नुपर्छ।

यद्यपि, यो शिफ्टलाई अझ प्रभावकारी बनाउन सम्भव छ - रैखिकमा होइन, तर निरन्तर समयमा। यो गर्नको लागि, पहिलो चरणमा, तपाईंले पहिलो तत्वको अवस्थालाई अन्तिम एकसँग, दोस्रोलाई उपान्त्यमा, र यस्तै अन्यसँग साटासाट गर्न आवश्यक छ। अन्तिम तत्वको अवस्था सही स्थितिमा हुनेछ। र अब हामीले दोस्रो तत्वको अवस्थालाई अन्तिम एकसँग, तेस्रोलाई उपान्त्यसँग, र यस्तै अन्यसँग साटासाट गर्न आवश्यक छ। आदानप्रदानको यो राउन्ड पछि, सबै तत्वहरूको राज्यहरू सही स्थितिमा हुनेछन्। त्यहाँ जम्मा O(2M) ~ O(1) क्रमपरिवर्तन हुनेछ।

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

के तपाईंलाई पजलहरू मन पर्यो? के तपाईलाई अन्य समाधानहरू थाहा छ? कमेन्टमा सेयर गर्नुहोस्।

र यहाँ अन्तमा केही उपयोगी लिङ्कहरू छन्:

• बारे थप जान्नुहोस् पूर्वाधार विकास समोच्च मा
• आन्तरिक रेकर्डहरू हेर्नुहोस् रिपोर्ट संग फ्लायर वितरण प्रणाली बारे
• भिडियो व्याख्यानको श्रृंखला हेर्नुहोस्साधारण मान्छे को लागि असामान्य एल्गोरिदम»
• हाम्रो सदस्यता लिनुहोस् टेलिग्राममा च्यानल

स्रोत: www.habr.com