Het 'n paar dae gelede gebeur . Die ouens van JUG.ru Group het droomsprekers (Leslie Lamport! Cliff Click! Martin Kleppmann!) genooi en twee dae aan verspreide stelsels en rekenaars gewy. Kontur was een van die drie vennote van die konferensie. Ons het by die stand gesels, oor ons verspreide stoorplekke gepraat, bingo gespeel en raaisels opgelos.
Hierdie is 'n pos met 'n ontleding van take by die Kontur-stalletjie van die skrywer van hul teks. Wie was op die Hydra - dit is jou rede om die aangename ervaring te onthou, wie was nie - 'n kans om jou brein te rek groot O-notasie.
Daar was selfs deelnemers wat die blaaibord in skyfies afgebreek het om hul besluit neer te skryf. Ek maak nie 'n grap nie - hulle het hierdie stapel papier vir verifikasie oorhandig:
Daar was drie take in totaal:
- oor die kies van replikas volgens gewigte vir vragbalansering
- oor die sortering van navraagresultate teen 'n in-geheue databasis
- op staatsoordrag in 'n verspreide stelsel met 'n ringtopologie
Taak 1. ClusterClient
Dit was nodig om 'n algoritme voor te stel vir die doeltreffende seleksie van K uit N geweegde replikas van 'n verspreide stelsel:
Jou span het die taak om 'n kliëntbiblioteek te ontwikkel vir 'n massief verspreide groep N nodusse. Die biblioteek sal tred hou met verskeie metadata wat met nodusse geassosieer word (bv. hul latensies, 4xx/5xx reaksietempo's, ens.) en swaaipuntgewigte W1..WN aan hulle toewys. Om die gelyktydige uitvoeringstrategie te ondersteun, moet die biblioteek K van N nodusse ewekansig kan kies - 'n kans om gekies te word moet eweredig wees aan 'n nodus se gewig.
Stel 'n algoritme voor om nodusse doeltreffend te selekteer. Skat die berekeningskompleksiteit daarvan deur groot O-notasie te gebruik.
Hoekom is alles in Engels?
Omdat die konferensiedeelnemers in hierdie vorm met hulle baklei het en omdat Engels die amptelike taal van Hydra was. Die take het soos volg gelyk:
Neem papier en potlood, dink, moenie dadelik spoilers oopmaak nie 🙂
Ontleding van die oplossing (video)
Begin om 5:53, slegs 4 minute:
En hier is hoe die ouens met die blaaibord hul oplossing voorgestel het:
Ontleding van die oplossing (teks)
Die volgende oplossing lê op die oppervlak: som die gewigte van alle replikas, genereer 'n ewekansige getal van 0 tot die som van alle gewigte, kies dan 'n i-replika sodat die som van replika gewigte van 0 tot (i-1)e is minder as 'n ewekansige getal, en die som van replika gewigte van 0 tot i-de - meer as dit. Dit sal dus moontlik wees om een replika te kies, en om die volgende een te kies, moet u die hele prosedure herhaal sonder om die geselekteerde replika in ag te neem. Met so 'n algoritme is die kompleksiteit van die keuse van een replika O(N), die kompleksiteit van die keuse van K replikas is O(N K) ~ O(N2).
Kwadratiese kompleksiteit is sleg, maar dit kan verbeter word. Om dit te doen, sal ons bou vir somme van gewigte. 'n Boom van diepte lg N sal verkry word, in die blare waarvan daar replika gewigte sal wees, en in die oorblywende nodusse - gedeeltelike somme, tot die som van alle gewigte aan die wortel van die boom. Vervolgens genereer ons 'n ewekansige getal van 0 tot die som van alle gewigte, vind die i-de replika, verwyder dit uit die boom, en herhaal die prosedure om die oorblywende replikas te vind. Met hierdie algoritme is die kompleksiteit van die bou van 'n boom O(N), die kompleksiteit om die i-de replika te vind en dit uit die boom te verwyder is O(lg N), die kompleksiteit van die keuse van K replikas is O(N + K) lg N) ~ O(N lg N) .
Lineêre log kompleksiteit is mooier as kwadratiese kompleksiteit, veral vir groot K.
Dit is hierdie algoritme ClusterClient biblioteke van die projek "". (Daar is die boom gebou in O(N lg N), maar dit beïnvloed nie die finale kompleksiteit van die algoritme nie.)
Taak 2. Zebra
Dit was nodig om 'n algoritme voor te stel vir doeltreffende sortering van dokumente in die geheue deur 'n arbitrêre nie-geïndexeerde veld:
Jou span is getaak om 'n versnipperde in-geheue dokument databasis te ontwikkel. 'n Algemene werklading sal wees om top N dokumente gesorteer volgens 'n arbitrêre (nie-geïndexeerde) numeriese veld uit 'n versameling van grootte M (gewoonlik N < 100 << M) te kies. 'n Effens minder algemene werklading sou wees om top N te kies nadat top S-dokumente (S ~ N) oorgeslaan is.
Stel 'n algoritme voor om sulke navrae doeltreffend uit te voer. Skat die berekeningskompleksiteit daarvan deur groot O-notasie in die gemiddelde geval en die ergste geval scenario's te gebruik.
Ontleding van die oplossing (video)
Begin om 34:50, slegs 6 minute:
Ontleding van die oplossing (teks)
Oppervlakoplossing: sorteer alle dokumente (byvoorbeeld met ), neem dan N+S-dokumente. In hierdie geval is die kompleksiteit van sortering gemiddeld O(M lg M), op die ergste O(M2).
Dit is duidelik dat dit ondoeltreffend is om alle M dokumente te sorteer en dan net 'n klein deel daarvan te neem. Om nie alle dokumente te sorteer nie, is 'n algoritme geskik , wat N + S van die verlangde dokumente sal kies (hulle kan volgens enige algoritme gesorteer word). In hierdie geval sal die kompleksiteit gemiddeld tot O(M) afneem, terwyl die ergste geval dieselfde sal bly.
Jy kan dit egter selfs meer doeltreffend doen - gebruik die algoritme . In hierdie geval word die eerste N+S-dokumente by min- of maksimum-hoop gevoeg (afhangende van die sorteerrigting), en dan word elke daaropvolgende dokument vergelyk met die wortel van die boom, wat die huidige minimum of maksimum dokument bevat, en word by die boom gevoeg indien nodig. . In hierdie geval is die kompleksiteit in die ergste geval, wanneer jy die boom voortdurend moet herbou, O(M lg M), die kompleksiteit is gemiddeld O(M), soos met quickselect.
Hoopstroming blyk egter meer doeltreffend te wees as gevolg van die feit dat die meeste van die dokumente in die praktyk weggegooi kan word sonder om die hoop te herbou na 'n enkele vergelyking met sy wortelelement. Sulke sortering word geïmplementeer in die Zebra-in-geheue-dokumentdatabasis wat in Kontur ontwikkel en gebruik word.
Taak 3. Staatsruilings
Dit was nodig om die mees doeltreffende algoritme vir die verskuiwing van toestande voor te stel:
Jou span het die taak om 'n spoggerige staatsuitruilmeganisme vir 'n verspreide groep N nodusse te ontwikkel. Die i-de nodus se toestand moet na die (i+1)-de nodus oorgedra word, die N-de node se toestand moet na die eerste node oorgedra word. Die enigste ondersteunde operasie is die staatsruiling wanneer twee nodusse hul toestande atomies uitruil. Dit is bekend dat 'n staatsruil M millisekondes neem. Elke nodus kan op enige gegewe oomblik aan 'n enkele staatsruil deelneem.
Hoe lank neem dit om die toestande van alle nodusse in 'n groep oor te dra?
Ontleding van die oplossing (teks)
Oppervlakoplossing: wissel die toestande van die eerste en tweede element, dan die eerste en derde, dan die eerste en vierde, ensovoorts. Na elke uitruiling sal die toestand van een element in die verlangde posisie wees. Jy moet O(N) permutasies maak en O(N M) tyd spandeer.
Lineêre tyd is lank, so jy kan die toestande van elemente in pare uitruil: die eerste met die tweede, die derde met die vierde, ensovoorts. Na elke staatsuitruiling sal elke tweede element in die regte posisie wees. Jy moet O(lg N) permutasies maak en O(M lg N) tyd spandeer.
Dit is egter moontlik om die verskuiwing nog doeltreffender te maak - nie in lineêr nie, maar in konstante tyd. Om dit te doen, moet jy by die eerste stap die toestand van die eerste element uitruil met die laaste een, die tweede met die voorlaaste een, ensovoorts. Die toestand van die laaste element sal in die korrekte posisie wees. En nou moet ons die toestand van die tweede element verruil met die laaste een, die derde een met die voorlaaste een, ensovoorts. Na hierdie rondte van uitruilings sal die toestande van alle elemente in die regte posisie wees. Daar sal O(2M) ~ O(1) permutasies in totaal wees.
So 'n oplossing sal glad nie 'n wiskundige verbaas wat nog onthou dat 'n rotasie 'n samestelling van twee aksiale simmetrieë is nie. Terloops, dit word triviaal veralgemeen vir 'n verskuiwing nie deur een nie, maar deur K < N posisies. (Skryf in die kommentaar hoe presies.)
Het jy van legkaarte gehou? Ken jy ander oplossings? Deel in die kommentaar.
En hier is 'n paar nuttige skakels op die ou end:
- Leer meer oor in kontoer
- sien rekords van interne oor verspreide stelsels
- kyk na die reeks videolesings»
- teken in op ons
Bron: will.com