Dogodilo se prije nekoliko dana Hydra konferencija. Dečki iz JUG.ru Group pozvali su govornike iz snova (Leslie Lamport! Cliff Click! Martin Kleppmann!) i dva dana posvetili distribuiranim sustavima i računalstvu. Kontur je bio jedan od tri partnera konferencije. Razgovarali smo na štandu, razgovarali o našem distribuiranom skladištu, igrali bingo i rješavali probleme.

Ovo je post s analizom zadataka na štandu Kontura od autora njihovog teksta. Za one koji su bili u Hidri, ovo je prilika da se prisjete ugodnih iskustava, za one koji nisu, ovo je prilika za razgibavanje mozga veliki O-notacija.

Bilo je čak i sudionika koji su rastavili flipchart na slajdove kako bi zapisali svoje rješenje. Ne šalim se - dali su ovu hrpu papira na uvid:

Bila su ukupno tri zadatka:

• o odabiru replika po težinama za uravnoteženje opterećenja
• o sortiranju rezultata upita prema bazi podataka u memoriji
• o prijenosu stanja u distribuiranom sustavu s topologijom prstena

Zadatak 1. ClusterClient

Bilo je potrebno predložiti algoritam za učinkovit odabir K od N ponderiranih replika distribuiranog sustava:

Vaš tim ima zadatak razviti klijentsku biblioteku za masivno distribuirani klaster od N čvorova. Knjižnica bi pratila razne metapodatke povezane s čvorovima (npr. njihove latencije, stope odgovora 4xx/5xx, itd.) i dodijelila im težine W1..WN s pomičnim zarezom. Kako bi podržala strategiju istovremenog izvođenja, knjižnica bi trebala moći nasumično odabrati K od N čvorova—šansa da budete odabrani trebala bi biti proporcionalna težini čvora.

Predložite algoritam za učinkovit odabir čvorova. Procijenite njegovu računsku složenost koristeći veliko O.

Zašto je sve na engleskom?

Zato što su se sudionici konferencije tako borili protiv njih i zato što je engleski bio službeni jezik Hidre. Problemi su izgledali ovako:

Uzmite papir i olovku, razmislite, nemojte žuriti s otvaranjem spojlera odmah :)

Analiza rješenja (video)

Počinje u 5:53, samo 4 minute:

A evo kako su ti isti tipovi s flipchartom predstavili svoje rješenje:

Analiza rješenja (tekst)

Sljedeće rješenje leži na površini: zbrojite težine svih replika, generirajte slučajni broj od 0 do zbroja svih težina, zatim odaberite i-repliku tako da zbroj težina replika od 0 do (i -1)th je manji od slučajnog broja, a zbroj težina replika od 0 do i-th - veći od njega. Na taj način možete odabrati jednu repliku, a za odabir sljedeće potrebno je ponoviti cijeli postupak bez razmatranja odabrane replike. S takvim algoritmom, složenost odabira jedne replike je O(N), složenost odabira K replika je O(N·K) ~ O(N2).

Kvadratna složenost je loša, ali se može poboljšati. Za ovo ćemo graditi stablo segmenta za sume težina. Rezultat je stablo dubine lg N, čiji će listovi sadržavati težine replika, a preostali čvorovi će sadržavati parcijalne zbrojeve, do zbroja svih težina u korijenu stabla. Zatim generiramo slučajni broj od 0 do zbroja svih težina, pronalazimo i-tu repliku, uklanjamo je sa stabla i ponavljamo postupak za pronalaženje preostalih replika. S takvim algoritmom, složenost konstruiranja stabla je O(N), složenost pronalaženja i-te replike i njenog uklanjanja sa stabla je O(lg N), složenost odabira K replika je O(N + K lg N) ~ O(N lg N) .

Linearno-logaritamska složenost je bolja od kvadratne složenosti, posebno za velike K.

To je ovaj algoritam implementiran u kodu ClusterClient biblioteke iz projekta "Istok" (Tamo je stablo izgrađeno u O(N lg N), ali to ne utječe na konačnu složenost algoritma.)

Problem 2. Zebra

Bilo je potrebno predložiti algoritam za učinkovito sortiranje dokumenata u memoriji po proizvoljnom neindeksiranom polju:

Vaš tim ima zadatak razviti razdijeljenu bazu podataka dokumenata u memoriji. Uobičajeno radno opterećenje bilo bi odabrati prvih N dokumenata razvrstanih po proizvoljnom (neindeksiranom) numeričkom polju iz kolekcije veličine M (obično N < 100 << M). Nešto manje uobičajeno radno opterećenje bilo bi odabrati gornji N nakon preskakanja gornjih S dokumenata (S ~ N).

Predložite algoritam za učinkovito izvršavanje takvih upita. Procijenite njegovu računsku složenost koristeći veliki O zapis u prosječnom slučaju i najgorem scenariju.

Analiza rješenja (video)

Početak u 34:50, samo 6 minuta:

Analiza rješenja (tekst)

Rješenje na površini: sortirajte sve dokumente (na primjer, koristeći živa sorta), zatim uzmite N+S dokumenata. U ovom slučaju, složenost sortiranja u prosjeku je O(M lg M), u najgorem slučaju - O(M2).

Očito je neučinkovito sortiranje svih M dokumenata, a zatim uzimanje samo njihovog malog dijela. Kako ne biste sortirali sve dokumente, poslužit će algoritam brzi odabir, koji će odabrati N+S traženih dokumenata (mogu se sortirati bilo kojim algoritmom). U tom slučaju složenost će se u prosjeku smanjiti na O(M), a najgori će slučaj ostati isti.

Međutim, možete to učiniti još učinkovitije - koristite algoritam strujanje binarne gomile. U ovom slučaju, prvih N+S dokumenata dodaje se u min- ili max-heap (ovisno o smjeru sortiranja), a zatim se svaki sljedeći dokument uspoređuje s korijenom stabla, koji sadrži trenutni minimalni ili maksimalni dokument , i po potrebi se dodaje stablu . U ovom slučaju, složenost u najgorem slučaju, kada morate stalno iznova graditi stablo, je O(M lg M), složenost u prosjeku je O(M), kao kada koristite quickselect.

Međutim, ispada da je strujanje hrpe učinkovitije zbog činjenice da se u praksi većina dokumenata može odbaciti bez ponovne izgradnje hrpe, nakon jedne usporedbe s korijenskim elementom. Ovo sortiranje implementirano je u Zebra in-memory bazi dokumenata, razvijenoj i korištenoj u Konturu.

Problem 3. Zamjene stanja

Bilo je potrebno predložiti najučinkovitiji algoritam za pomicanje stanja:

Vaš tim ima zadatak razviti fensi mehanizam za razmjenu stanja za distribuirani klaster od N čvorova. Stanje i-tog čvora treba prenijeti na (i+1)-ti čvor, stanje N-tog čvora treba prenijeti na prvi čvor. Jedina podržana operacija je izmjena stanja kada dva čvora atomski razmjenjuju svoja stanja. Poznato je da zamjena stanja traje M milisekundi. Svaki čvor može sudjelovati u jednoj izmjeni stanja u bilo kojem trenutku.

Koliko je vremena potrebno za prijenos stanja svih čvorova u klasteru?

Analiza rješenja (tekst)

Rješenje na površini: zamijeniti stanja prvog i drugog elementa, zatim prvog i trećeg, pa prvog i četvrtog i tako dalje. Nakon svake izmjene stanje jednog elementa će biti u željenoj poziciji. Morat ćete napraviti O(N) permutacija i potrošiti O(N·M) vremena.

Linearno vrijeme je dugo, tako da možete mijenjati stanja elemenata u paru: prvi s drugim, treći s četvrtim i tako dalje. Nakon svake izmjene stanja, svaki drugi element će biti u željenom položaju. Morat ćete napraviti O(lg N) permutacija i potrošiti O(M lg N) vremena.

Međutim, pomak možete učiniti još učinkovitijim - ne u linearnom, već u konstantnom vremenu. Da biste to učinili, u prvom koraku morate razmijeniti stanje prvog elementa s posljednjim, drugog s pretposljednjim i tako dalje. Stanje posljednjeg elementa bit će u željenom položaju. I sada trebamo razmijeniti stanje drugog elementa s posljednjim, trećeg s pretposljednjim i tako dalje. Nakon ove runde razmjene, stanja svih elemenata bit će u željenoj poziciji. Ukupno će se napraviti O(2M) ~ O(1) permutacija.

Takvo rješenje neće nimalo iznenaditi matematičara, koji se još sjeća da je rotacija sastav dviju osnih simetrija. Uzgred, trivijalno je generalizirano pomak ne za jedan, nego za K < N položaja. (Napišite u komentarima točno kako.)

Jesu li vam se svidjele zagonetke? Znate li druga rješenja? Podijelite u komentarima.

Evo nekoliko konačnih korisnih poveznica:

• saznajte više o razvoj infrastrukture u Konturu
• pogledajte internu evidenciju letak s izvješćima o distribuiranim sustavima
• pogledajte seriju video predavanja "Neobični algoritmi za obične ljude»
• pretplatite se na naše Telegram kanal

Izvor: www.habr.com