Gerðist fyrir nokkrum dögum Hydra ráðstefna. Strákarnir úr JUG.ru hópnum buðu draumaræðumurum (Leslie Lamport! Cliff Click! Martin Kleppmann!) og eyddu tveimur dögum í dreifð kerfi og tölvumál. Kontur var einn þriggja samstarfsaðila ráðstefnunnar. Við ræddum saman í stúkunni, ræddum um dreifða geymsluna okkar, spiluðum bingó og leystum þrautir.

Þetta er færsla með greiningu á verkefnum á Kontur-básnum frá höfundi texta þeirra. Hver var á Hydra - þetta er ástæðan þín til að muna ánægjulega upplifunina, hver var ekki - tækifæri til að teygja heilann stór O-tákn.

Það voru meira að segja þátttakendur sem tóku flettitöfluna í sundur í glærur til að skrifa niður ákvörðun sína. Ég er ekki að grínast - þeir afhentu þennan pappírsbunka til staðfestingar:

Alls voru þrjú verkefni:

• um að velja eftirlíkingar eftir lóðum fyrir álagsjafnvægi
• um að flokka niðurstöður fyrirspurna á móti gagnagrunni í minni
• um ríkistilfærslu í dreifðu kerfi með hringlaga svæðisfræði

Verkefni 1. ClusterClient

Nauðsynlegt var að leggja til reiknirit fyrir skilvirkt val á K úr N vegnum eftirlíkingum af dreifðu kerfi:

Teyminu þínu er falið að þróa viðskiptavinabókasafn fyrir gríðarlega dreifðan þyrping N hnúta. Safnið myndi halda utan um ýmis lýsigögn sem tengjast hnútum (td töf þeirra, 4xx/5xx svarhlutfall osfrv.) og úthluta þeim fljótapunktaþyngd W1..WN. Til þess að styðja við samhliða framkvæmdarstefnu ætti bókasafnið að geta valið K af N hnúta af handahófi - möguleikar á að vera valdir ættu að vera í réttu hlutfalli við þyngd hnúts.

Leggðu til reiknirit til að velja hnúta á skilvirkan hátt. Metið flókið útreikninga með því að nota stóra O nótnaskrift.

Af hverju er allt á ensku?

Vegna þess að í þessu formi börðust þátttakendur ráðstefnunnar með þeim og vegna þess að enska var opinbert tungumál Hydra. Verkefnin litu svona út:

Taktu pappír og blýant, hugsaðu, ekki flýta þér að opna spoilera strax 🙂

Greining á lausninni (myndband)

Byrjar 5:53, aðeins 4 mínútur:

Og hér er hvernig strákarnir með flettitöfluna settu fram lausn sína:

Greining á lausninni (texti)

Eftirfarandi lausn liggur á yfirborðinu: Leggðu saman þyngd allra eftirmynda, búðu til slembitölu frá 0 til summan af öllum lóðum, veldu síðan i-eftirmynd þannig að summa af eftirlíkingum þyngd frá 0 til (i-1) er minni en tilviljunarkennd tala, og summa eftirmynda vegur frá 0 til i-th - meira en það. Þannig að það verður hægt að velja eina eftirmynd og til að velja þá næstu þarftu að endurtaka alla aðgerðina án þess að huga að valinni eftirmynd. Með slíkri reiknirit er flókið við að velja eina eftirmynd O(N), flókið við að velja K eftirmynd er O(N K) ~ O(N2).

Ferðungsflækjustig er slæmt, en það er hægt að bæta það. Til að gera þetta munum við byggja hlutatré fyrir upphæðir af lóðum. Tré með dýpt lg N verður fengin, í laufum þess verða eftirlíkingarþyngdir og í hnútunum sem eftir eru - hlutaupphæðir, allt að summu allra lóða við rót trésins. Því næst búum við til handahófskennda tölu frá 0 upp í summu allra lóða, finnum i-th eftirmyndina, fjarlægjum hana úr trénu og endurtökum ferlið til að finna eftirlíkingarnar sem eftir eru. Með þessari reiknirit er flókið að byggja tré O(N), flókið við að finna i-þætti eftirlíkingarinnar og fjarlægja það úr trénu er O(lg N), flókið við að velja K eftirmyndir er O(N + K lg N) ~ O(N lg N) .

Línuleg logarflækjustig er flottari en ferningsflækjustig, sérstaklega fyrir stóra K.

Það er þetta reiknirit útfært í kóða ClusterClient bókasöfn úr verkefninu "Austur". (Þar er tréð byggt í O(N lg N), en það hefur ekki áhrif á endanlegt flókið reiknirit.)

Verkefni 2. Zebra

Nauðsynlegt var að leggja til reiknirit fyrir skilvirka flokkun skjala í minni eftir handahófskenndu óverðtryggðu sviði:

Teyminu þínu er falið að þróa sundurskorinn gagnagrunn skjala í minni. Algengt vinnuálag væri að velja efstu N skjölin flokkuð eftir handahófskenndu (óverðtryggðu) tölusviði úr safni af stærð M (venjulega N < 100 << M). Örlítið sjaldgæfara vinnuálag væri að velja efsta N eftir að hafa sleppt efstu S skjölunum (S ~ N).

Leggðu til reiknirit til að framkvæma slíkar fyrirspurnir á skilvirkan hátt. Áætlaðu útreikningsflækju þess með því að nota stórt O-merki í meðalfalli og versta tilviki.

Greining á lausninni (myndband)

Byrjar kl 34:50, aðeins 6 mínútur:

Greining á lausninni (texti)

Yfirborðslausn: flokkaðu öll skjöl (til dæmis með fljótasort), taktu síðan N+S skjöl. Í þessu tilviki er flókið flokkun að meðaltali O(M lg M), í versta falli O(M2).

Það er augljóst að það er óhagkvæmt að flokka öll M skjöl og taka svo aðeins lítinn hluta þeirra. Til að flokka ekki öll skjöl hentar reiknirit fljótlegt val, sem mun velja N + S af skjölunum sem óskað er eftir (þau er hægt að raða eftir hvaða reiknirit sem er). Í þessu tilviki mun flækjustigið minnka í O(M) að meðaltali en versta tilvikið verður óbreytt.

Hins vegar geturðu gert það enn skilvirkari - notaðu reikniritið tvöfaldur hrúgu streymi. Í þessu tilviki er fyrstu N+S skjölunum bætt við min- eða max-heap (fer eftir flokkunarstefnu) og síðan er hvert næsta skjal borið saman við rót trésins, sem inniheldur núverandi lágmarks- eða hámarksskjal, og er bætt við tréð ef þarf. . Í þessu tilfelli er flækjustigið í versta falli, þegar þú þarft stöðugt að endurbyggja tréð, O(M lg M), flækjustigið að meðaltali O(M), eins og með skyndival.

Hins vegar reynist hrúgastraumur skilvirkari vegna þess að í reynd er hægt að farga flestum skjölunum án þess að endurbyggja hrúguna eftir einn samanburð við rótarþáttinn. Slík flokkun er útfærð í Zebra in-memory skjalagagnagrunni sem þróaður og notaður er í Kontur.

Verkefni 3. Skiptaskipti ríkisins

Það var nauðsynlegt að leggja til skilvirkasta reikniritið til að skipta um ástand:

Liðinu þínu er falið að þróa glæsilegt ástandsskiptakerfi fyrir dreifðan þyrping N hnúta. Ástand i-ta hnútsins ætti að vera flutt í (i+1)-ta hnútinn, ástand N-hnútsins ætti að flytja í fyrsta hnútinn. Eina studda aðgerðin er ástandsskipti þegar tveir hnútar skiptast á ríkjum sínum í lotukerfinu. Það er vitað að ástandsskipti taka M millisekúndur. Sérhver hnútur er fær um að taka þátt í einni stöðuskipti á hverri stundu.

Hversu langan tíma tekur það að flytja ástand allra hnúta í klasa?

Greining á lausninni (texti)

Yfirborðslausn: skiptast á ástandi fyrsta og annars frumefnis, síðan fyrsta og þriðja, síðan fyrsta og fjórða, og svo framvegis. Eftir hver skipti verður ástand eins þáttar í æskilegri stöðu. Þú verður að gera O(N) umbreytingar og eyða O(N M) tíma.

Línulegur tími er langur, þannig að þú getur skipt um stöðu frumefna í pörum: fyrsta með öðru, þriðja með fjórða, og svo framvegis. Eftir hver skipti á ríkinu verður annar hver þáttur í réttri stöðu. Þú verður að gera O(lg N) umbreytingar og eyða O(M lg N) tíma.

Hins vegar er hægt að gera vaktina enn skilvirkari - ekki í línulegri, heldur á föstu tíma. Til að gera þetta, í fyrsta skrefi, þarftu að skipta um stöðu fyrsta þáttarins við þann síðasta, seinni við þann næstsíðasta og svo framvegis. Staða síðasta þáttar verður í réttri stöðu. Og nú þurfum við að skipta um stöðu annars þáttarins við þann síðasta, þann þriðja við þann næstsíðasta og svo framvegis. Eftir þessa skiptalotu verða ástand allra þátta í réttri stöðu. Alls verða O(2M) ~ O(1) breytingar.

Slík lausn kemur stærðfræðingi alls ekki á óvart sem man enn eftir því að snúningur er samsetning tveggja ássamhverfa. Við the vegur, það er léttvægt alhæft fyrir breytingu ekki um einn, heldur með K < N stöðum. (Skrifaðu í athugasemdir hvernig nákvæmlega.)

Fannst þér gaman að þrautum? Veistu um aðrar lausnir? Deildu í athugasemdum.

Og hér eru nokkrir gagnlegir tenglar í lokin:

• læra meira um uppbyggingu innviða í útlínu
• sjá skrár yfir innri bæklingur með skýrslum um dreifð kerfi
• horfa á röð myndbandsfyrirlestraÓvenjuleg reiknirit fyrir venjulegt fólk»
• gerast áskrifandi að okkar rás í Telegram

Heimild: www.habr.com