Juhtus paar päeva tagasi . Grupi JUG.ru poisid kutsusid unelmate kõnelejad (Leslie Lamport! Cliff Click! Martin Kleppmann!) ja pühendasid kaks päeva hajutatud süsteemidele ja andmetöötlusele. Kontur oli üks kolmest konverentsi partnerist. Rääkisime putkas, rääkisime oma jagatud salvestusruumist, mängisime bingot ja lahendasime mõistatusi.
See on Konturi stendi ülesannete analüüsiga postitus nende teksti autorilt. Kes oli Hydra peal - see on teie põhjus meenutada meeldivat kogemust, kes mitte - võimalus oma aju venitada suur O- märge.
Oli isegi osalejaid, kes lammutasid pabertahvel slaidideks, et oma otsus kirja panna. Ma ei tee nalja – nad andsid selle paberivirna kontrollimiseks üle:
Kokku oli kolm ülesannet:
- koopiate valimise kohta koormuse tasakaalustamiseks kaalu järgi
- päringutulemuste sortimise kohta mälusiseste andmebaaside põhjal
- oleku ülekande kohta ringtopoloogiaga hajutatud süsteemis
Ülesanne 1. ClusterClient
Oli vaja välja pakkuda algoritm K tõhusaks valimiseks hajutatud süsteemi N kaalutud koopiast:
Teie meeskonna ülesandeks on arendada klienditeek massiliselt hajutatud N sõlmede klastri jaoks. Teek jälgiks erinevaid sõlmedega seotud metaandmeid (nt nende latentsusajad, 4xx/5xx reageerimissagedused jne) ja määraks neile ujukomakaalud W1...WN. Samaaegse täitmisstrateegia toetamiseks peaks raamatukogu suutma juhuslikult valida K N-st sõlmest – väljavalimise võimalus peaks olema võrdeline sõlme kaaluga.
Pakkuge välja algoritm sõlmede tõhusaks valimiseks. Hinnake selle arvutuslikku keerukust, kasutades suurt O-tähistust.
Miks on kõik inglise keeles?
Sest sellisel kujul võitlesid konverentsil osalejad nendega ja kuna inglise keel oli Hydra ametlik keel. Ülesanded nägid välja sellised:
Võta paber ja pliiats, mõtle, ära torma kohe spoilereid avama 🙂
Lahenduse analüüs (video)
Alates 5:53, ainult 4 minutit:
Ja siin on see, kuidas pabertahvel olevad poisid oma lahenduse esitasid:
Lahenduse analüüs (tekst)
Pinnal on järgmine lahendus: summeerida kõigi koopiate kaalud, genereerida juhuslik arv 0-st kõigi kaalude summani, seejärel valida i-replica nii, et koopiate kaalude summa oleks vahemikus 0 kuni (i-1). on väiksem kui juhuslik arv ja koopiate kaalude summa vahemikus 0 kuni i-nda on sellest suurem. Seega on võimalik valida üks koopia ja järgmise valimiseks peate kordama kogu protseduuri ilma valitud koopiat arvestamata. Sellise algoritmi puhul on ühe koopia valimise keerukus O(N), K koopia valimise keerukus on O(N K) ~ O(N2).
Ruutiline keerukus on halb, kuid seda saab parandada. Selleks ehitame kaalude summade jaoks. Saadakse puu sügavusega lg N, mille lehtedes on koopiakaalud ja ülejäänud sõlmedes - osalised summad, kuni kõigi puu juure kaalude summani. Järgmisena genereerime juhusliku arvu nullist kõigi kaalude summani, leiame i-nda koopia, eemaldame selle puust ja kordame ülejäänud koopiate leidmiseks protseduuri. Selle algoritmiga on puu ehitamise keerukus O(N), i-nda koopia leidmise ja puust eemaldamise keerukus on O(lg N), K koopia valimise keerukus on O(N + K lg N) ~ O(N lg N) .
Lineaarse logaritmi keerukus on parem kui ruutkeskmine keerukus, eriti suure K puhul.
See on see algoritm ClusterClient'i raamatukogud projektist "". (Seal on puu ehitatud O(N lg N), kuid see ei mõjuta algoritmi lõplikku keerukust.)
Ülesanne 2. Sebra
Tuli välja pakkuda algoritm mälus olevate dokumentide tõhusaks sortimiseks suvalise indekseerimata välja järgi:
Teie meeskonna ülesandeks on välja töötada tükeldatud mälusisene dokumentide andmebaas. Tavaline töökoormus oleks M suuruse kogumi hulgast (tavaliselt N < 100 << M) suvalise (indekseerimata) numbrivälja järgi sorteeritud N parimat dokumenti. Veidi harvem töökoormus oleks valida top N pärast top S dokumentide vahelejätmist (S ~ N).
Pakkuge välja algoritm selliste päringute tõhusaks täitmiseks. Hinnake selle arvutuslikku keerukust, kasutades suurt O-tähistust keskmise ja halvima stsenaariumi korral.
Lahenduse analüüs (video)
Alates 34:50, ainult 6 minutit:
Lahenduse analüüs (tekst)
Pinnalahendus: sorteeri kõik dokumendid (nt ), seejärel võtke N+S dokumendid. Sel juhul on sorteerimise keerukus keskmiselt O(M lg M), halvimal juhul O(M2).
On ilmne, et kõigi M dokumentide sorteerimine ja seejärel vaid väikese osa võtmine on ebaefektiivne. Et kõiki dokumente mitte sorteerida, sobib algoritm , mis valib soovitud dokumentidest N + S (neid saab sortida mis tahes algoritmi järgi). Sel juhul väheneb keerukus keskmiselt O(M)-ni, halvimal juhul jääb aga samaks.
Kuid saate seda teha veelgi tõhusamalt – kasutage algoritmi . Sel juhul lisatakse esimesed N+S dokumendid min- või max-hunnikusse (olenevalt sortimise suunast) ja seejärel võrreldakse iga järgmist dokumenti puu juurega, mis sisaldab hetkel kehtivat miinimum- või maksimumdokumenti, ja lisatakse vajadusel puule. . Sel juhul on keerukus halvimal juhul, kui pead pidevalt puud ümber ehitama, O (M lg M), keerukus on keskmiselt O (M), nagu ka Quickselecti puhul.
Kuhja voogesitus osutub aga tõhusamaks tänu sellele, et praktikas saab pärast ühekordset võrdlust selle juurelemendiga enamuse dokumente ära visata ilma hunnikut uuesti üles ehitamata. Selline sorteerimine on realiseeritud Konturis välja töötatud ja kasutatavas Zebra mälusiseses dokumentide andmebaasis.
Ülesanne 3. Riigivahetused
Oli vaja välja pakkuda kõige tõhusam olekute nihutamise algoritm:
Teie meeskonna ülesandeks on välja töötada väljamõeldud olekuvahetusmehhanism N sõlme hajutatud klastri jaoks. I-nda sõlme olek tuleks üle kanda (i+1)-ndasse sõlme, N-nda sõlme olek tuleks üle kanda esimesse sõlme. Ainus toetatud toiming on olekuvahetus, kui kaks sõlme vahetavad olekuid aatomiliselt. On teada, et olekuvahetus võtab aega M millisekundit. Iga sõlm saab igal hetkel osaleda ühes olekuvahetuses.
Kui kaua kulub klastri kõigi sõlmede olekute ülekandmiseks?
Lahenduse analüüs (tekst)
Pinnalahendus: vahetage esimese ja teise elemendi olekud, seejärel esimese ja kolmanda, seejärel esimese ja neljanda jne olekud. Pärast iga vahetust on ühe elemendi olek soovitud asendis. Peate tegema O(N) permutatsioone ja kulutama O(N M) aega.
Lineaarne aeg on pikk, nii et saate elementide olekuid vahetada paarikaupa: esimene teisega, kolmas neljandaga jne. Pärast iga olekuvahetust on iga teine element õiges asendis. Peate tegema O(lg N) permutatsiooni ja kulutama O(M lg N) aega.
Küll aga on võimalik nihet veelgi efektiivsemaks muuta – mitte lineaarses, vaid konstantses ajas. Selleks peate esimeses etapis vahetama esimese elemendi oleku viimasega, teise elemendi oleku eelviimasega ja nii edasi. Viimase elemendi olek on õiges asendis. Ja nüüd peame vahetama teise elemendi oleku viimasega, kolmanda elemendi eelviimasega ja nii edasi. Pärast seda vahetusvooru on kõigi elementide olekud õiges asendis. Kokku on O(2M) ~ O(1) permutatsioonid.
Selline lahendus ei üllata sugugi matemaatikut, kes veel mäletab, et pöörlemine on kahe telgsümmeetria kompositsioon. Muide, see on triviaalselt üldistatud nihkeks mitte ühe, vaid K < N positsiooni võrra. (Kirjutage kommentaaridesse, kuidas täpselt.)
Kas teile meeldisid mõistatused? Kas teate muid lahendusi? Jagage kommentaarides.
Ja siin on lõpuks mõned kasulikud lingid:
- kohta lisateavet kontuuris
- vaata sisemisi dokumente hajutatud süsteemide kohta
- vaata videoloengute sarja»
- tellige meie
Allikas: www.habr.com