Ndodhi pak ditë më parë . Djemtë nga grupi JUG.ru ftuan folësit e ëndrrave (Leslie Lamport! Cliff Click! Martin Kleppmann!) dhe i kushtuan dy ditë sistemeve të shpërndara dhe informatikës. Kontur ishte një nga tre partnerët e konferencës. Ne folëm në kabinë, folëm për ruajtjen tonë të shpërndarë, luajtëm bingo dhe zgjidhëm enigmat.
Ky është një postim me një analizë të detyrave në stendën e Konturit nga autori i tekstit të tyre. Kush ishte në Hidra - kjo është arsyeja juaj për të kujtuar përvojën e këndshme, kush nuk ishte - një shans për të shtrirë trurin tuaj i madh O- shënim.
Madje kishte pjesëmarrës që e çmontuan tabelën në rrëshqitje për të shkruar vendimin e tyre. Nuk po bëj shaka - ata e dorëzuan këtë pirg letre për verifikim:
Kishte tre detyra në total:
- rreth zgjedhjes së kopjeve sipas peshave për balancimin e ngarkesës
- rreth renditjes së rezultateve të pyetjeve kundrejt një baze të dhënash në memorie
- mbi transferimin e gjendjes në një sistem të shpërndarë me një topologji unazore
Detyra 1. ClusterClient
Ishte e nevojshme të propozohej një algoritëm për zgjedhjen efikase të K nga N kopje të peshuara të një sistemi të shpërndarë:
Ekipi juaj ka për detyrë të zhvillojë një bibliotekë klientësh për një grup nyjesh të shpërndarë masivisht. Biblioteka do të mbajë gjurmët e meta të dhënave të ndryshme të lidhura me nyjet (p.sh. vonesat e tyre, normat e përgjigjes 4xx/5xx, etj.) dhe do t'u caktojë atyre pesha me pikë lundruese W1..WN. Për të mbështetur strategjinë e ekzekutimit të njëkohshëm, biblioteka duhet të jetë në gjendje të zgjedhë K nga N nyje në mënyrë të rastësishme - mundësia për t'u zgjedhur duhet të jetë proporcionale me peshën e një nyje.
Propozoni një algoritëm për të zgjedhur nyjet në mënyrë efikase. Vlerësoni kompleksitetin e tij llogaritës duke përdorur shënimin e madh O.
Pse është gjithçka në anglisht?
Sepse në këtë formë pjesëmarrësit e konferencës luftuan me ta dhe sepse anglishtja ishte gjuha zyrtare e Hidrës. Detyrat dukeshin kështu:
Merrni letër dhe laps, mendoni, mos nxitoni të hapni spoilerët menjëherë 🙂
Analiza e zgjidhjes (video)
Duke filluar nga ora 5:53, vetëm 4 minuta:
Dhe ja se si djemtë me flipchart parashtruan zgjidhjen e tyre:
Analiza e zgjidhjes (teksti)
Zgjidhja e mëposhtme qëndron në sipërfaqe: mblidhni peshat e të gjitha kopjeve, gjeneroni një numër të rastësishëm nga 0 në shumën e të gjitha peshave, më pas zgjidhni një kopje i-të tillë që shuma e peshave të kopjeve nga 0 në (i-1) th është më pak se një numër i rastësishëm, dhe shuma e peshave të kopjeve nga 0 në i-të - më shumë se ajo. Pra, do të jetë e mundur të zgjidhni një kopje, dhe për të zgjedhur një tjetër, duhet të përsërisni të gjithë procedurën pa marrë parasysh kopjen e zgjedhur. Me një algoritëm të tillë, kompleksiteti i zgjedhjes së një kopje është O(N), kompleksiteti i zgjedhjes së kopjeve K është O(N K) ~ O(N2).
Kompleksiteti kuadratik është i keq, por mund të përmirësohet. Për ta bërë këtë, ne do të ndërtojmë për shumat e peshave. Do të fitohet një pemë me thellësi lg N, në gjethet e së cilës do të ketë pesha kopje, dhe në nyjet e mbetura - shuma të pjesshme, deri në shumën e të gjitha peshave në rrënjën e pemës. Më pas, gjenerojmë një numër të rastësishëm nga 0 në shumën e të gjitha peshave, gjejmë kopjen e i-të, e heqim atë nga pema dhe përsërisim procedurën për të gjetur kopjet e mbetura. Me këtë algoritëm, kompleksiteti i ndërtimit të një peme është O(N), kompleksiteti i gjetjes së kopjes së i-të dhe heqjes së saj nga pema është O(lg N), kompleksiteti i zgjedhjes së kopjeve K është O(N + K lg N) ~ O(N lg N) .
Kompleksiteti linear-log është më i mirë se kompleksiteti kuadratik, veçanërisht për K të madh.
Ky është algoritmi Bibliotekat ClusterClient nga projekti "". (Atje, pema është ndërtuar në O(N lg N), por kjo nuk ndikon në kompleksitetin përfundimtar të algoritmit.)
Detyra 2. Zebra
Ishte e nevojshme të propozohej një algoritëm për renditjen efikase të dokumenteve në memorie nga një fushë arbitrare jo e indeksuar:
Ekipi juaj ka për detyrë të zhvillojë një bazë të dhënash dokumentesh të copëtuara në memorie. Një ngarkesë e zakonshme pune do të ishte zgjedhja e N dokumenteve kryesore të renditura sipas një fushe numerike arbitrare (jo të indeksuar) nga një koleksion me madhësi M (zakonisht N < 100 << M). Një ngarkesë pune pak më pak e zakonshme do të ishte zgjedhja e N-së së lartë pas kapërcimit të dokumenteve S lart (S ~ N).
Propozoni një algoritëm për të ekzekutuar pyetje të tilla në mënyrë efikase. Vlerësoni kompleksitetin e tij llogaritës duke përdorur shënimin e madh O në rastin mesatar dhe skenarët më të keq.
Analiza e zgjidhjes (video)
Duke filluar nga ora 34:50, vetëm 6 minuta:
Analiza e zgjidhjes (teksti)
Zgjidhja sipërfaqësore: rendit të gjitha dokumentet (për shembull me ), më pas merrni dokumentet N+S. Në këtë rast, kompleksiteti i renditjes është mesatarisht O(M lg M), në rastin më të keq O(M2).
Është e qartë se renditja e të gjitha dokumenteve M dhe më pas marrja e vetëm një pjese të vogël të tyre është joefikase. Për të mos renditur të gjitha dokumentet, një algoritëm është i përshtatshëm , i cili do të zgjedhë N + S të dokumenteve të dëshiruara (ato mund të renditen sipas çdo algoritmi). Në këtë rast, kompleksiteti do të ulet në O(M) mesatarisht, ndërsa rasti më i keq do të mbetet i njëjtë.
Sidoqoftë, mund ta bëni edhe më me efikasitet - përdorni algoritmin . Në këtë rast, dokumentet e para N+S i shtohen grumbullit min- ose max (në varësi të drejtimit të renditjes), dhe më pas çdo dokument tjetër krahasohet me rrënjën e pemës, e cila përmban dokumentin minimal ose maksimal aktual. dhe shtohet në pemë nëse është e nevojshme. . Në këtë rast, kompleksiteti në rastin më të keq, kur duhet të rindërtoni vazhdimisht pemën, është O(M lg M), kompleksiteti mesatarisht është O(M), si me zgjedhjen e shpejtë.
Sidoqoftë, transmetimi i grumbullit rezulton të jetë më efikas për faktin se në praktikë shumica e dokumenteve mund të hidhen pa rindërtuar grumbullin pas një krahasimi të vetëm me elementin e tij rrënjë. Një renditje e tillë zbatohet në bazën e të dhënave të dokumenteve Zebra në memorie të zhvilluar dhe përdorur në Kontur.
Detyra 3. Shkëmbimi i shtetit
Ishte e nevojshme të propozohej algoritmi më efikas për ndryshimin e gjendjeve:
Ekipi juaj ka për detyrë të zhvillojë një mekanizëm të zbukuruar të shkëmbimit të gjendjes për një grup të shpërndarë N nyjesh. Gjendja e nyjës së i-të duhet të transferohet në nyjen (i+1)-të, gjendja e nyjës së N-të duhet të transferohet në nyjen e parë. Operacioni i vetëm i mbështetur është shkëmbimi i gjendjes kur dy nyje shkëmbejnë gjendjet e tyre në mënyrë atomike. Dihet se një shkëmbim shteti merr M milisekonda. Çdo nyje është në gjendje të marrë pjesë në një shkëmbim të vetëm gjendjesh në çdo moment të caktuar.
Sa kohë duhet për të transferuar gjendjet e të gjitha nyjeve në një grup?
Analiza e zgjidhjes (teksti)
Zgjidhja sipërfaqësore: shkëmbeni gjendjet e elementit të parë dhe të dytë, pastaj të parën dhe të tretën, pastaj të parën dhe të katërtin, e kështu me radhë. Pas çdo shkëmbimi, gjendja e një elementi do të jetë në pozicionin e dëshiruar. Duhet të bëni ndërrime O(N) dhe të kaloni kohë O(N M).
Koha lineare është e gjatë, kështu që ju mund të shkëmbeni gjendjet e elementeve në çifte: e para me të dytin, e treta me të katërtin, e kështu me radhë. Pas çdo shkëmbimi shtetëror, çdo element i dytë do të jetë në pozicionin e duhur. Duhet të bëni ndërrime O(lg N) dhe të shpenzoni kohë O(M lg N).
Sidoqoftë, është e mundur që ndryshimi të bëhet edhe më efikas - jo në linjë, por në kohë konstante. Për ta bërë këtë, në hapin e parë, duhet të shkëmbeni gjendjen e elementit të parë me atë të fundit, të dytin me atë të parafundit, e kështu me radhë. Gjendja e elementit të fundit do të jetë në pozicionin e duhur. Dhe tani duhet të shkëmbejmë gjendjen e elementit të dytë me të fundit, të tretën me atë të parafundit, e kështu me radhë. Pas këtij raundi shkëmbimesh, shtetet e të gjithë elementëve do të jenë në pozicionin e duhur. Gjithsej do të ketë permutacione O(2M) ~ O(1).
Një zgjidhje e tillë nuk do ta befasojë aspak një matematikan që ende kujton se një rrotullim është një përbërje e dy simetrive boshtore. Nga rruga, ajo përgjithësohet në mënyrë të parëndësishme për një zhvendosje jo me një, por nga pozicionet K <N. (Shkruani në komente se sa saktësisht.)
Ju pëlqyen enigmat? A dini zgjidhje të tjera? Ndani në komente.
Dhe këtu janë disa lidhje të dobishme në fund:
- mësoni më shumë rreth në kontur
- shih të dhënat e brendshme rreth sistemeve të shpërndara
- shikoni serinë e video leksioneve»
- abonohuni në tonë
Burimi: www.habr.com