Bir necha kun oldin sodir bo'lgan Gidra konferentsiyasi. JUG.ru guruhi yigitlari orzu spikerlarini taklif qilishdi (Leslie Lamport! Cliff Click! Martin Kleppmann!) va ikki kunni taqsimlangan tizimlar va hisoblashlarga bag'ishladilar. Kontur konferensiyaning uchta hamkoridan biri edi. Biz stendda gaplashdik, taqsimlangan omborlarimiz haqida gaplashdik, bingo o'ynadik va jumboqlarni hal qildik.

Bu Kontur stendidagi topshiriqlar matni muallifidan tahlil qilingan post. Gidrada kim bo'lgan - bu sizning yoqimli tajribangizni eslash uchun sabab, kim bo'lmagan - miyangizni cho'zish imkoniyati katta O-notatsiya.

Hatto o'z qarorini yozish uchun flipchartni slaydlarga ajratib qo'ygan ishtirokchilar ham bor edi. Men hazil qilmayapman - ular tekshirish uchun bu qog'oz to'plamini berishdi:

Hammasi bo'lib uchta vazifa bor edi:

• yuklarni muvozanatlash uchun og'irliklar bo'yicha replikalarni tanlash haqida
• so'rov natijalarini xotiradagi ma'lumotlar bazasiga nisbatan saralash haqida
• halqali topologiyaga ega taqsimlangan tizimda holatni uzatish bo'yicha

Vazifa 1. ClusterClient

Tarqalgan tizimning N ta vaznli replikalaridan K ni samarali tanlash algoritmini taklif qilish kerak edi:

Sizning jamoangiz N tugunlarning ommaviy taqsimlangan klasteri uchun mijozlar kutubxonasini ishlab chiqish vazifasini bajaradi. Kutubxona tugunlar bilan bog'liq bo'lgan turli metama'lumotlarni (masalan, ularning kechikishlari, 4xx/5xx javob tezligi va boshqalar) kuzatib boradi va ularga W1..WN suzuvchi nuqta og'irliklarini tayinlaydi. Bir vaqtning o'zida bajarish strategiyasini qo'llab-quvvatlash uchun kutubxona N ta tugunning K ni tasodifiy tanlay olishi kerak - tanlanish imkoniyati tugunning og'irligiga mutanosib bo'lishi kerak.

Tugunlarni samarali tanlash uchun algoritmni taklif qiling. Katta O belgisi yordamida uning hisoblash murakkabligini baholang.

Nega hammasi ingliz tilida?

Chunki bu shaklda konferentsiya ishtirokchilari ular bilan kurashgan va ingliz tili Gidraning rasmiy tili bo'lganligi sababli. Vazifalar quyidagicha ko'rinardi:

Qog'oz va qalam oling, o'ylab ko'ring, darhol spoylerlarni ochishga shoshilmang 🙂

Yechim tahlili (video)

5:53 dan boshlab, atigi 4 daqiqa:

Mana, flipchartli yigitlar o'z yechimini qanday ko'rsatdilar:

Yechim tahlili (matn)

Sirtda quyidagi yechim yotadi: barcha replikalarning ogʻirliklarini yigʻing, 0 dan barcha ogʻirliklar yigʻindisigacha tasodifiy son hosil qiling, soʻngra i-replikasini tanlang, shunda replika ogʻirliklari yigʻindisi 0 dan (i-1) gacha boʻladi. tasodifiy sondan kichik va 0 dan i-chi gacha bo'lgan replika og'irliklarining yig'indisi - undan ko'p. Shunday qilib, bitta nusxani tanlash mumkin bo'ladi va keyingisini tanlash uchun tanlangan replikani hisobga olmasdan butun protsedurani takrorlashingiz kerak. Bunday algoritm bilan bitta replikani tanlashning murakkabligi O(N), K replikasini tanlashning murakkabligi O(N K) ~ O(N2).

Kvadrat murakkablik yomon, lekin uni yaxshilash mumkin. Buning uchun biz quramiz segment daraxti og'irliklar yig'indisi uchun. Chuqurligi lg N bo'lgan daraxt olinadi, uning barglarida takroriy og'irliklar, qolgan tugunlarda esa qisman yig'indi, daraxtning ildizidagi barcha og'irliklar yig'indisiga qadar bo'ladi. Keyinchalik, biz 0 dan barcha og'irliklar yig'indisigacha tasodifiy son hosil qilamiz, i-replikani topamiz, uni daraxtdan olib tashlaymiz va qolgan replikalarni topish uchun protsedurani takrorlaymiz. Bu algoritm yordamida daraxt qurishning murakkabligi O(N), i-replikani topish va uni daraxtdan olib tashlashning murakkabligi O(lg N), K replika tanlashning murakkabligi O(N+K) ga teng. lg N) ~ O(N lg N) .

Chiziqli log murakkabligi kvadratik murakkablikdan ko'ra yaxshi, ayniqsa katta K. uchun.

Bu algoritm kodda amalga oshiriladi Loyihadan ClusterClient kutubxonalari "Sharq". (U erda daraxt O(N lg N) da qurilgan, ammo bu algoritmning yakuniy murakkabligiga ta'sir qilmaydi.)

2-topshiriq. Zebra

Xotiradagi hujjatlarni o'zboshimchalik bilan indekslanmagan maydon bo'yicha samarali saralash algoritmini taklif qilish kerak edi:

Sizning jamoangizga umumiy xotiradagi hujjatlar ma'lumotlar bazasini ishlab chiqish vazifasi yuklangan. Umumiy ish yuki M o'lchamdagi (odatda N < 100 << M) to'plamdan ixtiyoriy (indekssiz) raqamli maydon bo'yicha tartiblangan N ta eng yaxshi hujjatni tanlashdir. Biroz kamroq tarqalgan ish yuki yuqori S hujjatlarni (S ~ N) o'tkazib yuborgandan so'ng yuqori N ni tanlash bo'ladi.

Bunday so'rovlarni samarali bajarish uchun algoritmni taklif qiling. O'rtacha va eng yomon stsenariylarda katta O belgisidan foydalanib, uning hisoblash murakkabligini baholang.

Yechim tahlili (video)

34:50 dan boshlab, atigi 6 daqiqa:

Yechim tahlili (matn)

Yuzaki yechim: barcha hujjatlarni tartiblash (masalan tezkor), keyin N+S hujjatlarini oling. Bunday holda, saralashning murakkabligi o'rtacha O(M lg M), eng yomoni O(M2).

Ko'rinib turibdiki, barcha M xujjatlarni saralash va keyin ularning faqat kichik qismini olish samarasizdir. Barcha hujjatlarni tartiblamaslik uchun algoritm mos keladi tez tanlash, bu kerakli hujjatlarning N + S ni tanlaydi (ular har qanday algoritm bo'yicha saralanishi mumkin). Bunday holda, murakkablik o'rtacha O (M) ga kamayadi, eng yomoni esa bir xil bo'lib qoladi.

Biroq, siz buni yanada samarali qilishingiz mumkin - algoritmdan foydalaning ikkilik to'p oqimi. Bunday holda, birinchi N+S hujjatlari min- yoki max-heapga qo'shiladi (tartib yo'nalishiga qarab), so'ngra har bir keyingi hujjat joriy minimal yoki maksimal hujjatni o'z ichiga olgan daraxt ildizi bilan taqqoslanadi, va agar kerak bo'lsa, daraxtga qo'shiladi. . Bu holatda, eng yomon holatda, daraxtni doimiy ravishda qayta qurish kerak bo'lganda, murakkablik O(M lg M), o'rtacha murakkablik O(M), tezkor tanlashda bo'lgani kabi.

Biroq, yig'ma oqim yanada samaraliroq bo'lib chiqadi, chunki amalda hujjatlarning aksariyati uning ildiz elementi bilan bir marta taqqoslashdan so'ng uyumni qayta tiklamasdan olib tashlanishi mumkin. Bunday tartiblash Konturda ishlab chiqilgan va foydalaniladigan Zebra xotiradagi hujjatlar bazasida amalga oshiriladi.

Vazifa 3. Davlat almashinuvi

Vaziyatlarni o'zgartirish uchun eng samarali algoritmni taklif qilish kerak edi:

Sizning jamoangizga N tugunlarning taqsimlangan klasteri uchun ajoyib davlat almashinuvi mexanizmini ishlab chiqish vazifasi yuklatilgan. i-tugunning holati (i+1)-chi tugunga, N-tugunning holati birinchi tugunga o'tkazilishi kerak. Qo'llab-quvvatlanadigan yagona operatsiya - bu ikkita tugun o'z holatlarini atomik ravishda almashtirganda davlat almashinuvi. Ma'lumki, davlat almashinuvi M millisekundni oladi. Har bir tugun istalgan vaqtda yagona davlat almashinuvida ishtirok etishi mumkin.

Klasterdagi barcha tugunlarning holatini uzatish uchun qancha vaqt ketadi?

Yechim tahlili (matn)

Yuzaki yechim: birinchi va ikkinchi element, keyin birinchi va uchinchi, keyin birinchi va to'rtinchi va hokazo holatlarni almashish. Har bir almashinuvdan so'ng, bitta elementning holati kerakli holatda bo'ladi. Siz O (N) almashtirishni amalga oshirishingiz va O (N M) vaqtini sarflashingiz kerak.

Chiziqli vaqt uzoq, shuning uchun siz elementlarning holatini juftlik bilan almashishingiz mumkin: birinchisi ikkinchisi bilan, uchinchisi to'rtinchisi bilan va hokazo. Har bir davlat almashinuvidan so'ng, har bir ikkinchi element to'g'ri holatda bo'ladi. Siz O(lg N) almashtirishlarni qilishingiz va O(M lg N) vaqtini sarflashingiz kerak.

Biroq, siljishni yanada samaraliroq qilish mumkin - chiziqli emas, balki doimiy vaqtda. Buni amalga oshirish uchun birinchi bosqichda siz birinchi elementning holatini oxirgisi bilan, ikkinchisini oxirgidan oldingi bilan va hokazolarni almashtirishingiz kerak. Oxirgi elementning holati to'g'ri holatda bo'ladi. Va endi biz ikkinchi elementning holatini oxirgisi bilan, uchinchisini oxirgidan oldingi bilan va hokazolarni almashtirishimiz kerak. Ushbu ayirboshlash bosqichidan so'ng barcha elementlarning holati to'g'ri holatda bo'ladi. Jami O(2M) ~ O(1) almashtirishlar bo'ladi.

Bunday yechim aylanish ikki eksenel simmetriyaning tarkibi ekanligini hali ham eslaydigan matematikni ajablantirmaydi. Aytgancha, u bir emas, balki K < N pozitsiyalari bo'yicha siljish uchun trivial umumlashtiriladi. (Izohlarda qanday qilib aniq yozing.)

Sizga jumboqlar yoqdimi? Boshqa yechimlarni bilasizmi? Izohlarda baham ko'ring.

Va oxirida ba'zi foydali havolalar:

• haqida ko'proq bilib oling infratuzilmani rivojlantirish konturda
• ichki yozuvlarga qarang hisobotlar bilan flayer taqsimlangan tizimlar haqida
• video ma'ruzalar turkumini tomosha qilingOddiy odamlar uchun noodatiy algoritmlar»
• obuna bo'ling Telegramdagi kanal

Manba: www.habr.com