Mõni päev tagasi toimus konverents Hydra. JUG.ru Group kutsus unistuste esinejad (Leslie Lamport! Cliff Click! Martin Kleppmann!) ja pühendas kaks päeva jaotatud süsteemidele ja arvutustele. Contour oli üks kolmest konverentsi partnerist. Me suhtlesime stendis, rääkisime oma jaotatud ladudest, mängisime bingo't, lahendasime ülesandeid.

See postitus sisaldab ülesannete lahendusi Contouri stendilt nende autori poolt. Kes oli Hydra's - see on võimalus meenutada meeldivaid muljeid, kes ei olnud - võimalus oma mõtteid pingutada. big O-märkusega.

Kohal olid isegi osalejad, kes tuletasid flipperi slaididele, et salvestada oma lahendused. Ma ei naljata - nad esitasid kontrollimiseks sellise paberikuhja:

Kokku oli kolm ülesannet:

replikate valik kaalude järgi koormuse tasakaalustamiseks
päringu tulemuste sortimine in-memory andmebaasis
oleku edastamine jaotatud süsteemis ringikujulise topoloogiaga

Ülesanne 1. ClusterClient

Pidi pakkuma efektiivset K valimise algoritmi N-st kaalutud replikate jaotatud süsteemis:

Teie meeskond peab arendama klientide raamistiku massiliselt jaotatud N sõlme klastrile. Raamistik jälgib erinevaid metainformatsiooni, mis on seotud sõlmedega (nt nende latentsus, 4xx/5xx vastuste määr jne) ja määrab neile ujuvad kaalud W1..WN. Toetades samaaegse täitmisstrateegiat, peaks raamistiku olema võimeline juhuslikult valima K N sõlme – valimise tõenäosus peaks olema proportsionaalne sõlme kaaluga.
Paku ülesanne sõlmede efektiivseks valimiseks. Hinda selle arvutuslikku keerukust, kasutades suurt O märkust.

Miks on kõik inglise keeles?

Sest sellisel kujul võitlesid nende vastu konverentsi osalejad ja kuna inglise keel oli Hydra ametlik keel. Ülesanded nägid välja järgmiselt:

Võtke paber ja pliiats, mõelge, ärge kiirustage kohe spoilerite avamisega 🙂

Lahenduse arutelu (video)

Algus 5:53, kestvus kokku 4 minutit:

Nii esitasid oma lahenduse need samad poisid, kes olid flippide tahvlitega:

Lahenduse arutelu (tekst)

Pinnal on selline lahendus: liita kokku kõikide replikate kaalud, genereerida juhuslik number vahemikus 0 kuni kõikide kaalude summani, seejärel valida selline i-replika, et replikate kaalude summa vahemikus 0 kuni (i-1)-ni on väiksem juhuslikust numbrist, ja replikate kaalude summa vahemikus 0 kuni i-ni on sellest suurem. Nii saab valida ühe replika ning järgmise valimiseks tuleb kogu protseduur uuesti läbi viia, arvesse võtmata valitud replikat. Sellise algoritmiga on ühe replikate valimise keerukus O(N), K replikate valimise keerukus on O(N·K) ~ O(N²).

Ruutfunktsioon on halb, kuid seda on võimalik parandada. Selleks ehitame segmentpuu kaalude summade jaoks. Saame puu, mille sügavus on lg N, mille lehtedes asuvad replikate kaalud ja teistes sõlmedes osalised summad, jõudes puu juures kõikide kaalude summani. Järgmiseks genereerime juhusliku numbri vahemikus 0 kuni kõikide kaalude summani, leiame i-replika, eemaldame selle puust ning kordame protseduuri ülejäänud replikate otsimiseks. Sellise algoritmiga on puu ehitamise keerukus O(N), i-replika otsimise ja selle puust eemaldamise keerukus on O(lg N), K replikate valimise keerukus on O(N + K lg N) ~ O(N lg N).

Lineaarlogaritmiline keerukus on meeldivam kui ruutline, eriti suurte K-de puhul.

Just see algoritm on rakendatud koodis ClusterClient raamatukogus projektis „Ida“. (Seal ehitatakse puu O(N lg N) ajaga, kuid see ei mõjuta algoritmi lõplikku keerukust.)

Ülesanne 2. Zebra

Vajati algoritmi, mis tõhusalt sorteerib dokumente mälus mingi suvalise indekseerimata välja järgi:

Teie meeskond on ülesandeks arendada šarded mäludokumentide andmebaasi. Tüüpiline koormus oleks valida top N dokumenti, mis on sorteeritud suvalise (indekseerimata) numbrilise välja järgi kollektsioonist suurusega M (tavaliselt N < 100 << M). Veidi vähem levinud koormus oleks valida top N pärast top S dokumentide vahelejätmist (S ~ N).
Pakkuge algoritm, mis võimaldab selliseid päringuid tõhusalt täita. Hindake selle arvutuslikku keerukust suur O märkega keskmises ja halvimas stsenaariumis.

Lahenduse arutelu (video)

Algus 34:50, kokku 6 minutit:

Lahenduse arutelu (tekst)

Lahendus on pinnapealne: sorteerida kõik dokumendid (näiteks kasutades quicksort), seejärel võtta N+S dokumenti. Sellisel juhul on keskmine sortimise keerukus O(M lg M), halvim O(M²).

Ilmselgelt ei ole tõhus kõiki M dokumente sortida, et seejärel ainult väike osa neist võtta. Et mitte sortida kõiki dokumente, sobib algoritm quickselect, mis valib N+S vajalikke dokumente (neid saab sorteerida ükskõik millise algoritmi abil). Sel juhul väheneb keerukus keskmiselt O(M)-ni, kuid halvim juhtum jääb samaks.

Siiski on võimalik veelgi efektiivsemalt tegutseda — kasutada algoritmi binary heap streaming. Sel juhul kogutakse esimesed N+S dokumenti min- või max-heap'i (sõltuvalt sorteerimise suunast), seejärel võrreldakse iga järgmist dokumenti puu juurega, kus asub hetkel minimaalne või maksimaalne dokument, ja vajadusel lisatakse see puusse. Sel juhul halvim juhtum, kui puu tuleb pidevalt ümber ehitada — O(M lg M), keskmine keerukus — O(M), nagu quickselecti puhul.

Kuid heap streaming osutub tõhusamaks, kuna praktikas saab suure osa dokumentidest kõrvale jätta, ilma et oleks vaja kühveldust ümber ehitada, pärast ühte võrreldumist juureelemendiga. Selline sorteerimine on rakendatud dokumendipõhises mälu andmebaasis Zebra, mis on välja töötatud ja mida kasutatakse Konturis.

Ülesanne 3. Olekuvahetused

Pidi olema kõige efektiivsem algoritm olekute liigutamiseks:

Teie ülesanne on arendada keeruline olekuvahetuse mehhanism jaotatud N sõlmega klastris. i-nda sõlme olek tuleks edastada (i+1)-ndale sõlmele; N-nda sõlme olek tuleks edastada esimesele sõlmele. Ainsaks toetatud toiminguks on olekuvahetus, kui kaks sõlme vahetavad oma olekud aatomiliselt. On teada, et olekuvahetus võtab aega M millisekundit. Iga sõlm suudab osaleda ühes olekuvahetuses igal hetkel.
Kui kaua läheb aega kõikide sõlmede olekute edastamiseks klastris?

Lahenduse arutelu (tekst)

Pinnapealne lahendus: vahetada esimese ja teise elemendi olekud, seejärel esimese ja kolmanda, seejärel esimese ja neljanda jne. Iga vahetuse järel satub ühe elemendi olek soovitud positsioonile. Peab tegema O(N) ümberkorraldust ja kulutama O(N·M) aega.

Lineaarne aeg on pikk, seega saab elemente vahetada paaridena: esimest teisega, kolmandat neljandaga jne. Iga vahetuse järel satub iga teise elemendi olek soovitud positsioonile. Peab tegema O(lg N) ümberkorraldust ja kulutama O(M lg N) aega.

Kuid nihke saab teha veelgi efektiivsemaks — mitte lineaarselt, vaid konstantselt. Selleks tuleb esimeses sammus vahetada esimese elemendi olek viimasena, teise eelviimasena ja nii edasi. Viimase elemendi olek jõuab vajaliku positsiooni. Nüüd tuleb vahetada teise elemendi olek viimasega, kolmanda eelviimasega ja nii edasi. Pärast seda ümmargust vahetust asuvad kõik elementide olekud vajalikes positsioonides. Kokku tehakse O(2M) ~ O(1) ümberpaigutust.

Selline lahendus ei üllata matemaatikut, kes veel mäletab, et pööramine on kahe teljega sümmeetri kompositsioon. Muide, seda saab trivialiseeritult üldistada nihkega mitte ühe, vaid K < N positsiooni kohta. (Kirjutage kommentaarides, kuidas täpselt.)

Kas sulle meeldisid ülesanded? Kas tead muid lahendusi? Jagage kommentaarides.

Ja siin on mõned kasulikud lingid lõpetuseks: