Desilo se prije nekoliko dana Hydra Conference. Momci iz grupe JUG.ru pozvali su govornike iz snova (Leslie Lamport! Cliff Click! Martin Kleppmann!) i posvetili dva dana distribuiranim sistemima i računarstvu. Kontur je bio jedan od tri partnera konferencije. Razgovarali smo na štandu, razgovarali o našem distribuiranom skladištu, igrali bingo i rješavali zagonetke.

Ovo je objava sa analizom zadataka na štandu Kontura od autora njihovog teksta. Ko je bio na Hidri - ovo je tvoj razlog da se prisjetiš ugodnog iskustva, ko nije - prilika da rastegneš mozak veliki O-notacija.

Bilo je čak i učesnika koji su rastavili flipčart u slajdove kako bi zapisali svoju odluku. Ne šalim se - dali su ovu hrpu papira na provjeru:

Ukupno su bila tri zadatka:

• o odabiru replika po težinama za balansiranje opterećenja
• o sortiranju rezultata upita prema bazi podataka u memoriji
• o prijenosu stanja u distribuiranom sistemu sa prstenastom topologijom

Zadatak 1. ClusterClient

Bilo je potrebno predložiti algoritam za efikasan izbor K od N ponderiranih replika distribuiranog sistema:

Vaš tim ima zadatak da razvije klijentsku biblioteku za masovno distribuirani klaster od N čvorova. Biblioteka bi pratila različite metapodatke povezane sa čvorovima (npr. njihove latencije, 4xx/5xx stope odgovora, itd.) i dodijelila im težine s pomičnim zarezom W1..WN. Da bi podržala strategiju istovremenog izvršavanja, biblioteka bi trebalo da bude u mogućnosti da nasumično izabere K od N čvorova – šansa da bude izabrana treba da bude proporcionalna težini čvora.

Predložite algoritam za efikasan odabir čvorova. Procijenite njegovu računsku složenost koristeći veliku O notaciju.

Zašto je sve na engleskom?

Zato što su se u ovoj formi učesnici konferencije borili sa njima i zato što je engleski bio službeni jezik Hidre. Zadaci su izgledali ovako:

Uzmi papir i olovku, razmisli, ne žuri da odmah otvaraš spojlere 🙂

Analiza rješenja (video)

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

A evo kako su momci sa flipčartom 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 sume svih težina, zatim odaberite i-repliku tako da je zbroj težina replika od 0 do (i-1) je manji od slučajnog broja, a zbir težina replike od 0 do i-tog - veći od njega. Tako će biti moguće odabrati jednu repliku, a da biste odabrali sljedeću, morate ponoviti cijeli postupak bez razmatranja odabrane replike. Sa takvim algoritmom, složenost izbora jedne replike je O(N), složenost izbora K replika je O(N K) ~ O(N2).

Kvadratna složenost je loša, ali se može poboljšati. Da bismo to uradili, gradićemo segmentno stablo za sume težina. Dobiva se stablo dubine lg N u čijim listovima će biti replike težine, a u preostalim čvorovima - parcijalni zbir, do zbira svih težina u korijenu stabla. Zatim generišemo slučajni broj od 0 do zbira svih težina, pronađemo i-tu repliku, uklonimo je iz stabla i ponovimo proceduru da pronađemo preostale replike. Sa ovim algoritmom, složenost izgradnje stabla je O(N), složenost pronalaženja i-te replike i njenog uklanjanja iz stabla je O(lg N), složenost izbora K replika je O(N + K lg N) ~ O(N lg N) .

Linear-log kompleksnost je ljepša od kvadratne složenosti, posebno za velike K.

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

Zadatak 2. Zebra

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

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

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

Analiza rješenja (video)

Sa početkom u 34:50, samo 6 minuta:

Analiza rješenja (tekst)

Površinsko rješenje: sortirajte sve dokumente (na primjer sa brzo sortiranje), zatim uzmite N+S dokumente. U ovom slučaju, složenost sortiranja je u prosjeku O(M lg M), u najgorem slučaju O(M2).

Očigledno je da je sortiranje svih M dokumenata i zatim uzimanje samo malog dijela njih neefikasno. Da ne biste sortirali sve dokumente, prikladan je algoritam brzi izbor, koji će odabrati N + S željenih dokumenata (mogu se sortirati prema bilo kojem algoritmu). U ovom slučaju, složenost će se u prosjeku smanjiti na O(M), dok će najgori slučaj ostati isti.

Međutim, možete to učiniti još efikasnije - koristite algoritam binarni prijenos hrpe. U ovom slučaju, prvi N+S dokumenti se dodaju u min- ili maksimalnu hrpu (u zavisnosti od smjera sortiranja), a zatim se svaki sljedeći dokument upoređuje s korijenom stabla, koji sadrži trenutni minimalni ili maksimalni dokument, i dodaje se stablu ako je potrebno. . U ovom slučaju, složenost u najgorem slučaju, kada morate stalno obnavljati stablo, je O(M lg M), složenost u prosjeku je O(M), kao kod brzog odabira.

Međutim, ispostavlja se da je strimovanje gomile efikasnije zbog činjenice da se u praksi većina dokumenata može odbaciti bez ponovne izgradnje hrpe nakon jednog poređenja sa njenim osnovnim elementom. Takvo sortiranje implementirano je u bazi podataka Zebra in-memory dokumenata razvijenoj i korištenoj u Konturu.

Zadatak 3. Zamjene stanja

Bilo je potrebno predložiti najefikasniji algoritam za pomicanje stanja:

Vaš tim ima zadatak da razvije 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 zamjena stanja kada dva čvora atomski razmjenjuju svoja stanja. Poznato je da zamjena stanja traje M milisekundi. Svaki čvor može sudjelovati u jednoj zamjeni stanja u bilo kojem trenutku.

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

Analiza rješenja (tekst)

Površinsko rješenje: zamijenite stanja prvog i drugog elementa, zatim prvog i trećeg, zatim prvog i četvrtog, itd. Nakon svake razmjene, stanje jednog elementa će biti u željenoj poziciji. Morate napraviti O(N) permutacija i potrošiti O(N M) vremena.

Linearno vrijeme je dugo, tako da možete razmjenjivati ​​stanja elemenata u parovima: prvi sa drugim, treći sa četvrtim itd. Nakon svake razmjene stanja, svaki drugi element će biti u pravoj poziciji. Morate napraviti O(lg N) permutacija i potrošiti O(M lg N) vremena.

Međutim, moguće je pomak učiniti još efikasnijim - ne u linearnom, već u konstantnom vremenu. Da biste to učinili, u prvom koraku trebate zamijeniti stanje prvog elementa s posljednjim, drugog s pretposljednjim i tako dalje. Stanje posljednjeg elementa bit će u ispravnom položaju. I sada treba da zamenimo stanje drugog elementa sa poslednjim, trećeg sa predzadnjim, itd. Nakon ove runde razmjene, stanja svih elemenata će biti u pravom položaju. Ukupno će biti O(2M) ~ O(1) permutacija.

Takvo rješenje neće nimalo iznenaditi matematičara koji se još uvijek sjeća da je rotacija sastav dvije aksijalne simetrije. Usput, trivijalno je generaliziran za pomak ne za jedan, već za K < N pozicije. (Napišite u komentarima kako tačno.)

Da li ste voleli zagonetke? Znate li druga rješenja? Podijelite u komentarima.

I evo nekoliko korisnih linkova za kraj:

• saznajte više o razvoj infrastrukture u konturi
• vidi evidenciju internih letak sa izvještajima o distribuiranim sistemima
• pogledajte seriju video predavanjaNeobični algoritmi za obične ljude»
• pretplatite se na naše kanal u Telegramu

izvor: www.habr.com