Zgodilo se je pred nekaj dnevi . Fantje iz JUG.ru Group so povabili sanjske govorce (Leslie Lamport! Cliff Click! Martin Kleppmann!) in dva dni posvetili porazdeljenim sistemom in računalništvu. Kontur je bil eden od treh partnerjev konference. Na stojnici smo se pogovarjali, govorili o naših razdeljenih skladiščih, igrali bingo in reševali uganke.
To je prispevek z analizo nalog na stojnici Kontur od avtorja njihovega besedila. Kdo je bil na Hydri - to je vaš razlog, da se spomnite prijetne izkušnje, kdo ni bil - priložnost, da raztegnete svoje možgane velik O- notacija.
Bili so celo udeleženci, ki so tablo razstavili na diapozitive in zapisali svojo odločitev. Ne hecam se - ta kup papirja so dali v overitev:
Skupaj so bile tri naloge:
- o izbiri replik po uteži za izravnavo obremenitve
- o razvrščanju rezultatov poizvedbe glede na bazo podatkov v pomnilniku
- o prenosu stanja v porazdeljenem sistemu s topologijo obroča
Naloga 1. ClusterClient
Treba je bilo predlagati algoritem za učinkovito izbiro K iz N uteženih replik porazdeljenega sistema:
Vaša ekipa ima nalogo razviti odjemalsko knjižnico za masivno porazdeljeno gručo N vozlišč. Knjižnica bi spremljala različne metapodatke, povezane z vozlišči (npr. njihove zakasnitve, stopnje odziva 4xx/5xx itd.) in jim dodelila uteži s plavajočo vejico W1..WN. Da bi podprla strategijo sočasnega izvajanja, mora knjižnica imeti možnost, da naključno izbere K od N vozlišč – možnost, da bo izbrana, mora biti sorazmerna s težo vozlišča.
Predlagajte algoritem za učinkovito izbiro vozlišč. Ocenite njegovo računsko kompleksnost z uporabo velikega O.
Zakaj je vse v angleščini?
Ker so se v tej obliki udeleženci konference borili z njimi in ker je bila angleščina uradni jezik Hidre. Naloge so izgledale takole:
Vzemite papir in svinčnik, premislite, ne hitite takoj odpreti spojlerjev 🙂
Analiza rešitve (video)
Začetek ob 5:53, samo 4 minute:
In tukaj je, kako so fantje s tablo predstavili svojo rešitev:
Analiza rešitve (besedilo)
Naslednja rešitev je na površini: seštejte uteži vseh replik, ustvarite naključno število od 0 do vsote vseh uteži, nato izberite i-repliko tako, da je vsota uteži replik od 0 do (i-1)th je manjša od naključnega števila, vsota uteži replik od 0 do i-te pa večja od nje. Tako bo mogoče izbrati eno repliko, za izbiro naslednje pa je potrebno ponoviti celoten postopek brez upoštevanja izbrane replike. Pri takem algoritmu je kompleksnost izbire ene replike O(N), kompleksnost izbire K replik je O(N K) ~ O(N2).
Kvadratna kompleksnost je slaba, vendar jo je mogoče izboljšati. Da bi to naredili, bomo zgradili za vsote uteži. Dobili bomo drevo globine lg N, v listih katerega bodo uteži replike, v preostalih vozliščih pa delne vsote, do vsote vseh uteži v korenu drevesa. Nato generiramo naključno število od 0 do vsote vseh uteži, poiščemo i-to repliko, jo odstranimo iz drevesa in ponovimo postopek za iskanje preostalih replik. S tem algoritmom je kompleksnost gradnje drevesa O(N), kompleksnost iskanja i-te replike in njene odstranitve iz drevesa je O(lg N), kompleksnost izbire K replik je O(N + K lg N) ~ O(N lg N) .
Kompleksnost linearnega logaritma je boljša od kvadratne kompleksnosti, zlasti pri velikih K.
To je ta algoritem Knjižnice ClusterClient iz projekta "". (Tam je drevo zgrajeno v O(N lg N), vendar to ne vpliva na končno kompleksnost algoritma.)
Naloga 2. Zebra
Treba je bilo predlagati algoritem za učinkovito razvrščanje dokumentov v pomnilniku po poljubnem neindeksiranem polju:
Vaša ekipa ima nalogo razviti razdrobljeno zbirko podatkov dokumentov v pomnilniku. Običajna delovna obremenitev bi bila izbira prvih N dokumentov, razvrščenih po poljubnem (neindeksiranem) številskem polju iz zbirke velikosti M (običajno N < 100 << M). Nekoliko manj pogosta delovna obremenitev bi bila izbira zgornjega N po preskoku zgornjih S dokumentov (S ~ N).
Predlagajte algoritem za učinkovito izvajanje takih poizvedb. Ocenite njegovo računsko kompleksnost z uporabo zapisa velikega O v povprečnem primeru in najslabšem možnem scenariju.
Analiza rešitve (video)
Začetek ob 34:50, samo 6 minut:
Analiza rešitve (besedilo)
Površinska rešitev: razvrstite vse dokumente (na primer z ), nato vzemite dokumente N+S. V tem primeru je zahtevnost razvrščanja v povprečju O(M lg M), v najslabšem primeru O(M2).
Očitno je, da je razvrščanje vseh M dokumentov in nato prevzem le majhnega dela neučinkovito. Da ne bi razvrstili vseh dokumentov, je primeren algoritem , ki bo izbral N + S želenih dokumentov (lahko jih razvrstimo po poljubnem algoritmu). V tem primeru se bo kompleksnost v povprečju zmanjšala na O(M), v najslabšem primeru pa bo ostala enaka.
Vendar pa lahko to storite še bolj učinkovito - uporabite algoritem . V tem primeru se prvi N+S dokumenti dodajo v min- ali max-heap (odvisno od smeri razvrščanja), nato pa se vsak naslednji dokument primerja s korenom drevesa, ki vsebuje trenutni minimalni ali maksimalni dokument, in se po potrebi doda v drevo. V tem primeru je kompleksnost v najslabšem primeru, ko morate nenehno obnavljati drevo, O(M lg M), kompleksnost v povprečju je O(M), kot pri hitri izbiri.
Vendar se izkaže, da je pretakanje kopice bolj učinkovito zaradi dejstva, da je v praksi mogoče večino dokumentov zavreči brez ponovne izgradnje kopice po eni sami primerjavi z njenim korenskim elementom. Takšno razvrščanje je implementirano v podatkovni zbirki Zebra in-memory dokumentov, ki jo razvijamo in uporabljamo v Konturju.
Naloga 3. Zamenjave držav
Treba je bilo predlagati najučinkovitejši algoritem za premik stanj:
Vaša ekipa je zadolžena za razvoj domiselnega mehanizma za izmenjavo stanja za porazdeljeno gručo N vozlišč. Stanje i-tega vozlišča je treba prenesti na (i+1)-to vozlišče, stanje N-tega vozlišča pa na prvo vozlišče. Edina podprta operacija je zamenjava stanja, ko dve vozlišči atomsko izmenjata svoja stanja. Znano je, da zamenjava stanja traja M milisekund. Vsako vozlišče lahko kadar koli sodeluje pri zamenjavi posameznega stanja.
Koliko časa traja prenos stanj vseh vozlišč v gruči?
Analiza rešitve (besedilo)
Površinska rešitev: zamenjajte stanja prvega in drugega elementa, nato prvega in tretjega, nato prvega in četrtega itd. Po vsaki zamenjavi bo stanje enega elementa v želenem položaju. Narediti morate O(N) permutacij in porabiti O(N M) časa.
Linearni čas je dolg, zato lahko izmenjuješ stanja elementov v parih: prvega z drugim, tretjega s četrtim itd. Po vsaki zamenjavi stanja bo vsak drugi element v pravem položaju. Narediti morate O(lg N) permutacij in porabiti O(M lg N) časa.
Možno pa je narediti premik še učinkovitejši – ne v linearnem, temveč v konstantnem času. Če želite to narediti, morate na prvem koraku zamenjati stanje prvega elementa z zadnjim, drugega s predzadnjim in tako naprej. Stanje zadnjega elementa bo v pravilnem položaju. In zdaj moramo zamenjati stanje drugega elementa z zadnjim, tretjega s predzadnjim in tako naprej. Po tem krogu izmenjav bodo stanja vseh elementov v pravem položaju. Skupaj bo O(2M) ~ O(1) permutacij.
Takšna rešitev ne bo prav nič presenetila matematika, ki se še spomni, da je rotacija sestava dveh osnih simetrij. Mimogrede, trivialno je posplošen za premik ne za eno, ampak za K < N položajev. (V komentarje napišite, kako natančno.)
So vam bile všeč uganke? Ali poznate druge rešitve? Delite v komentarjih.
Za konec pa še nekaj uporabnih povezav:
- izvedeti več o v konturi
- glejte evidenco internih o porazdeljenih sistemih
- oglejte si serijo video predavanj»
- naročite se na naše
Vir: www.habr.com