काही दिवसांपूर्वी घडली हायड्रा परिषद. JUG.ru ग्रुपच्या मुलांनी ड्रीम स्पीकर (लेस्ली लॅम्पोर्ट! क्लिफ क्लिक! मार्टिन क्लेपमन!) आमंत्रित केले आणि दोन दिवस वितरित प्रणाली आणि संगणनासाठी समर्पित केले. कोंटूर हे परिषदेच्या तीन भागीदारांपैकी एक होते. आम्ही बूथवर बोललो, आमच्या वितरित स्टोरेजबद्दल बोललो, बिंगो खेळलो आणि कोडी सोडवली.

त्यांच्या मजकूराच्या लेखकाकडून कोंटूर स्टँडवरील कार्यांचे विश्लेषण असलेली ही पोस्ट आहे. हायड्रावर कोण होते - हे आनंददायी अनुभव लक्षात ठेवण्याचे तुमचे कारण आहे, कोण नव्हते - तुमचा मेंदू ताणण्याची संधी मोठा ओ-नोटेशन.

असेही सहभागी होते ज्यांनी त्यांचा निर्णय लिहिण्यासाठी फ्लिपचार्टला स्लाइड्समध्ये मोडून काढले. मी मस्करी करत नाही - त्यांनी कागदाचा हा स्टॅक पडताळणीसाठी दिला:

एकूण तीन कार्ये होती:

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

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

वितरित प्रणालीच्या N भारित प्रतिकृतींमधून K च्या कार्यक्षम निवडीसाठी अल्गोरिदम प्रस्तावित करणे आवश्यक होते:

तुमच्या टीमला N नोड्सच्या मोठ्या प्रमाणात वितरित क्लस्टरसाठी क्लायंट लायब्ररी विकसित करण्याचे काम देण्यात आले आहे. लायब्ररी नोड्सशी संबंधित विविध मेटाडेटांचा मागोवा ठेवेल (उदा. त्यांची लेटेंसी, 4xx/5xx प्रतिसाद दर इ.) आणि त्यांना फ्लोटिंग पॉइंट वजन W1..WN नियुक्त करेल. समवर्ती अंमलबजावणी धोरणाचे समर्थन करण्यासाठी, लायब्ररी यादृच्छिकपणे N नोड्सचे K निवडण्यास सक्षम असावी—निवड होण्याची संधी नोडच्या वजनाच्या प्रमाणात असावी.

कार्यक्षमतेने नोड्स निवडण्यासाठी अल्गोरिदम सुचवा. मोठ्या O नोटेशन वापरून त्याच्या संगणकीय जटिलतेचा अंदाज लावा.

सर्व काही इंग्रजीत का आहे?

कारण या फॉर्ममध्ये कॉन्फरन्समधील सहभागी त्यांच्याशी लढले आणि कारण इंग्रजी ही हायड्राची अधिकृत भाषा होती. कार्ये असे दिसली:

कागद आणि पेन्सिल घ्या, विचार करा, लगेच स्पॉयलर उघडण्यासाठी घाई करू नका 🙂

समाधानाचे विश्लेषण (व्हिडिओ)

5:53 वाजता सुरू होत आहे, फक्त 4 मिनिटे:

आणि फ्लिपचार्ट असलेल्या मुलांनी त्यांचे निराकरण कसे केले ते येथे आहे:

समाधानाचे विश्लेषण (मजकूर)

खालील सोल्यूशन पृष्ठभागावर आहे: सर्व प्रतिकृतींच्या वजनांची बेरीज करा, 0 ते सर्व वजनांच्या बेरजेपर्यंत एक यादृच्छिक संख्या तयार करा, नंतर एक i-प्रतिकृती निवडा की 0 ते (i-1)व्या प्रतिकृती वजनांची बेरीज यादृच्छिक संख्येपेक्षा कमी आहे, आणि प्रतिकृतीची बेरीज 0 ते i-th - त्यापेक्षा जास्त आहे. त्यामुळे एक प्रतिकृती निवडणे शक्य होईल आणि पुढील निवडण्यासाठी, तुम्हाला निवडलेल्या प्रतिकृतीचा विचार न करता संपूर्ण प्रक्रिया पुन्हा करावी लागेल. अशा अल्गोरिदमसह, एक प्रतिकृती निवडण्याची जटिलता O(N), K प्रतिकृती निवडण्याची जटिलता O(N K) ~ O(N2) आहे.

चतुर्भुज जटिलता वाईट आहे, परंतु ती सुधारली जाऊ शकते. हे करण्यासाठी, आम्ही तयार करू खंड वृक्ष वजनाच्या रकमेसाठी. खोलीचे एक झाड lg N मिळेल, ज्याच्या पानांमध्ये प्रतिकृती वजन असेल आणि उर्वरित नोड्समध्ये - आंशिक बेरीज, झाडाच्या मुळाशी असलेल्या सर्व वजनांच्या बेरजेपर्यंत. पुढे, आम्ही 0 ते सर्व वजनांच्या बेरजेपर्यंत एक यादृच्छिक संख्या तयार करतो, i-th प्रतिकृती शोधतो, ती झाडावरून काढून टाकतो आणि उर्वरित प्रतिकृती शोधण्यासाठी प्रक्रिया पुन्हा करतो. या अल्गोरिदमसह, झाड बनवण्याची जटिलता O(N) आहे, i-th प्रतिकृती शोधून ती झाडावरून काढून टाकण्याची जटिलता O(lg N), K प्रतिकृती निवडण्याची जटिलता O(N + K) आहे. lg N) ~ O(N lg N) .

रेखीय-लॉग जटिलता चतुर्भुज जटिलतेपेक्षा चांगली आहे, विशेषतः मोठ्या K साठी.

हे अल्गोरिदम आहे कोड मध्ये लागू प्रकल्पातील क्लस्टरक्लायंट लायब्ररी "पूर्व" (तेथे, झाड O(N lg N) मध्ये बांधले आहे, परंतु हे अल्गोरिदमच्या अंतिम जटिलतेवर परिणाम करत नाही.)

कार्य 2. झेब्रा

एका अनियंत्रित नॉन-इंडेक्स्ड फील्डद्वारे मेमरीमध्ये दस्तऐवजांची कार्यक्षम क्रमवारी लावण्यासाठी अल्गोरिदम प्रस्तावित करणे आवश्यक होते:

तुमच्या टीमला शार्ड इन-मेमरी दस्तऐवज डेटाबेस विकसित करण्याचे काम देण्यात आले आहे. M (सामान्यतः N < 100 << M) आकाराच्या संग्रहातून अनियंत्रित (नॉन-इंडेक्स केलेले) अंकीय फील्डद्वारे क्रमवारी लावलेले शीर्ष N दस्तऐवज निवडणे हा एक सामान्य कार्यभार असेल. शीर्ष S दस्तऐवज (S ~ N) वगळल्यानंतर शीर्ष N निवडणे हा थोडासा कमी सामान्य वर्कलोड असेल.

अशा क्वेरी कार्यक्षमतेने कार्यान्वित करण्यासाठी अल्गोरिदम प्रस्तावित करा. सरासरी केस आणि सर्वात वाईट परिस्थितीमध्ये मोठ्या O नोटेशनचा वापर करून त्याच्या संगणकीय जटिलतेचा अंदाज लावा.

समाधानाचे विश्लेषण (व्हिडिओ)

34:50 वाजता सुरू होत आहे, फक्त 6 मिनिटे:

समाधानाचे विश्लेषण (मजकूर)

पृष्ठभाग समाधान: सर्व कागदपत्रांची क्रमवारी लावा (उदाहरणार्थ सह क्विझकोर्ट), नंतर N+S दस्तऐवज घ्या. या प्रकरणात, वर्गीकरणाची जटिलता सरासरी O(M lg M), सर्वात वाईट O(M2) वर असते.

हे उघड आहे की सर्व एम दस्तऐवजांची क्रमवारी लावणे आणि नंतर त्यातील फक्त एक छोटासा भाग घेणे अकार्यक्षम आहे. सर्व कागदपत्रांची क्रमवारी लावू नये म्हणून, अल्गोरिदम योग्य आहे द्रुत निवड, जे इच्छित दस्तऐवजांपैकी N + S निवडेल (ते कोणत्याही अल्गोरिदमद्वारे क्रमवारी लावले जाऊ शकतात). या प्रकरणात, जटिलता सरासरी O(M) पर्यंत कमी होईल, तर सर्वात वाईट स्थिती तशीच राहील.

तथापि, आपण ते आणखी कार्यक्षमतेने करू शकता - अल्गोरिदम वापरा बायनरी हीप स्ट्रीमिंग. या प्रकरणात, प्रथम N+S दस्तऐवज किमान- किंवा कमाल-ढीग (क्रमवारीच्या दिशेवर अवलंबून) जोडले जातात आणि नंतर प्रत्येक पुढील दस्तऐवजाची तुलना झाडाच्या मुळाशी केली जाते, ज्यामध्ये वर्तमान किमान किंवा कमाल दस्तऐवज आहे, आणि आवश्यक असल्यास झाडाला जोडले जाते. . या प्रकरणात, सर्वात वाईट परिस्थितीत, जेव्हा तुम्हाला झाडाची सतत पुनर्बांधणी करावी लागते, तेव्हा O(M lg M) असते, क्विकसिलेक्ट प्रमाणे सरासरी जटिलता O(M) असते.

तथापि, हीप स्ट्रीमिंग अधिक कार्यक्षम ठरते कारण व्यवहारात बहुतेक दस्तऐवज त्याच्या मूळ घटकाशी एकल तुलना केल्यानंतर ढीग पुनर्बांधणी न करता टाकून दिले जाऊ शकतात. अशी क्रमवारी झेब्रा इन-मेमरी दस्तऐवज डेटाबेसमध्ये लागू केली जाते जी कोंटूरमध्ये विकसित आणि वापरली जाते.

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

राज्ये बदलण्यासाठी सर्वात कार्यक्षम अल्गोरिदम प्रस्तावित करणे आवश्यक होते:

तुमच्या टीमला N नोड्सच्या वितरित क्लस्टरसाठी फॅन्सी स्टेट एक्सचेंज मेकॅनिझम विकसित करण्याचे काम देण्यात आले आहे. i-th नोडची स्थिती (i+1)-व्या नोडमध्ये हस्तांतरित केली जावी, N-th नोडची स्थिती पहिल्या नोडमध्ये हस्तांतरित केली जावी. जेव्हा दोन नोड्स त्यांच्या राज्यांची अणूची देवाणघेवाण करतात तेव्हा एकमेव समर्थित ऑपरेशन म्हणजे स्टेट स्वॅप. हे ज्ञात आहे की राज्य स्वॅपला M मिलीसेकंद लागतात. प्रत्येक नोड कोणत्याही क्षणी सिंगल स्टेट स्वॅपमध्ये सहभागी होण्यास सक्षम आहे.

क्लस्टरमधील सर्व नोड्सची स्थिती हस्तांतरित करण्यासाठी किती वेळ लागतो?

समाधानाचे विश्लेषण (मजकूर)

पृष्ठभाग सोल्यूशन: पहिल्या आणि दुसर्‍या घटकाच्या स्थितीची देवाणघेवाण करा, नंतर प्रथम आणि तिसरा, नंतर पहिला आणि चौथा, आणि असेच. प्रत्येक एक्सचेंज नंतर, एका घटकाची स्थिती इच्छित स्थितीत असेल. तुम्हाला O(N) क्रमपरिवर्तन करावे लागेल आणि O(N M) वेळ घालवावा लागेल.

रेखीय वेळ मोठा आहे, म्हणून तुम्ही घटकांच्या अवस्थांची जोड्यांमध्ये देवाणघेवाण करू शकता: प्रथम दुसऱ्यासह, तिसरा चौथा आणि असेच. प्रत्येक राज्य विनिमयानंतर, प्रत्येक दुसरा घटक योग्य स्थितीत असेल. तुम्हाला O(lg N) क्रमपरिवर्तन करावे लागेल आणि O(M lg N) वेळ घालवावा लागेल.

तथापि, शिफ्ट आणखी कार्यक्षम करणे शक्य आहे - रेखीय नाही, परंतु सतत वेळेत. हे करण्यासाठी, पहिल्या पायरीवर, तुम्हाला पहिल्या घटकाची स्थिती शेवटच्या घटकासह, दुसरी उपांत्य घटकासह, इ. शेवटच्या घटकाची स्थिती योग्य स्थितीत असेल. आणि आता आपल्याला दुसर्‍या घटकाची स्थिती शेवटच्या घटकासह, तिसर्या घटकाची उपांत्य घटकासह, इ. एक्सचेंजच्या या फेरीनंतर, सर्व घटकांची स्थिती योग्य स्थितीत असेल. एकूण O(2M) ~ O(1) क्रमपरिवर्तन असतील.

असे समाधान गणितज्ञांना अजिबात आश्चर्यचकित करणार नाही ज्याला अजूनही हे लक्षात आहे की रोटेशन ही दोन अक्षीय सममितींची रचना आहे. तसे, एका शिफ्टसाठी नाही तर K < N पोझिशन्सद्वारे क्षुल्लकपणे सामान्यीकृत केले जाते. (कसे ते कमेंट मध्ये लिहा.)

तुम्हाला कोडे आवडले का? तुम्हाला इतर उपाय माहित आहेत का? टिप्पण्यांमध्ये सामायिक करा.

आणि शेवटी येथे काही उपयुक्त दुवे आहेत:

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

स्त्रोत: www.habr.com