Notika pirms dažÄm dienÄm . PuiÅ”i no JUG.ru grupas uzaicinÄja sapÅu runÄtÄjus (Leslie Lamport! Cliff Click! Martin Kleppmann!) un veltÄ«ja divas dienas sadalÄ«tajÄm sistÄmÄm un skaitļoÅ”anai. Konturs bija viens no trim konferences partneriem. MÄs runÄjÄm pie stenda, runÄjÄm par mÅ«su izplatÄ«tajÄm krÄtuvÄm, spÄlÄjÄm bingo un risinÄjÄm mÄ«klas.
Å is ir viÅu teksta autora ieraksts ar Kontur stenda uzdevumu analÄ«zi. KurÅ” bija uz Hidras - tas ir jÅ«su iemesls atcerÄties patÄ«kamo pieredzi, kurÅ” nebija - iespÄja izstiept savas smadzenes liels O- apzÄ«mÄjums.
Bija pat dalÄ«bnieki, kuri izjauca tÄfeli slaidos, lai pierakstÄ«tu savu lÄmumu. Es nejokoju - viÅi nodeva Å”o papÄ«ra kaudzi pÄrbaudei:
KopumÄ bija trÄ«s uzdevumi:
- par kopiju atlasi pÄc svara slodzes lÄ«dzsvaroÅ”anai
- par vaicÄjumu rezultÄtu kÄrtoÅ”anu, salÄ«dzinot ar atmiÅÄ esoÅ”o datu bÄzi
- par stÄvokļa pÄrsÅ«tÄ«Å”anu sadalÄ«tÄ sistÄmÄ ar gredzena topoloÄ£iju
Uzdevums 1. ClusterClient
Bija nepiecieÅ”ams piedÄvÄt algoritmu efektÄ«vai K atlasei no sadalÄ«tas sistÄmas N svÄrtajÄm replikÄm:
JÅ«su komandai ir uzdots izstrÄdÄt klienta bibliotÄku masveidÄ izplatÄ«tam N mezglu klasterim. BibliotÄka sekotu dažÄdiem ar mezgliem saistÄ«tiem metadatiem (piemÄram, to latentumiem, 4xx/5xx atbildes Ätrumiem utt.) un pieŔķirtu tiem peldoÅ”Ä komata svÄrumus W1..WN. Lai atbalstÄ«tu vienlaicÄ«gas izpildes stratÄÄ£iju, bibliotÄkai jÄspÄj nejauÅ”i izvÄlÄties K no N mezgliem ā iespÄjai tikt izvÄlÄtai jÄbÅ«t proporcionÄlai mezgla svaram.
PiedÄvÄjiet algoritmu, lai efektÄ«vi atlasÄ«tu mezglus. NovÄrtÄjiet tÄ skaitļoÅ”anas sarežģītÄ«bu, izmantojot lielo O apzÄ«mÄjumu.
KÄpÄc viss ir angļu valodÄ?
Jo Å”ÄdÄ formÄ konferences dalÄ«bnieki cÄ«nÄ«jÄs ar viÅiem un tÄpÄc, ka angļu valoda bija Hidras oficiÄlÄ valoda. Uzdevumi izskatÄ«jÄs Å”Ädi:
Å em papÄ«ru un zÄ«muli, domÄ, nesteidzies uzreiz atvÄrt spoileri š
RisinÄjuma analÄ«ze (video)
SÄkot no 5:53, tikai 4 minÅ«tes:
Un lÅ«k, kÄ puiÅ”i ar papÄ«ra tÄfeli izvirzÄ«ja savu risinÄjumu:
RisinÄjuma analÄ«ze (teksts)
Uz virsmas ir Å”Äds risinÄjums: summÄjiet visu kopiju svarus, Ä£enerÄjiet nejauÅ”u skaitli no 0 lÄ«dz visu svaru summai, pÄc tam izvÄlieties i-reprodukciju tÄ, lai replikas svaru summa bÅ«tu no 0 lÄ«dz (i-1)th. ir mazÄks par nejauÅ”u skaitli, un kopiju svaru summa no 0 lÄ«dz i-tajai ir lielÄka par to. TÄtad bÅ«s iespÄjams atlasÄ«t vienu kopiju, un, lai izvÄlÄtos nÄkamo, jums ir jÄatkÄrto visa procedÅ«ra, neÅemot vÄrÄ izvÄlÄto kopiju. Izmantojot Å”Ädu algoritmu, vienas replikas izvÄles sarežģītÄ«ba ir O(N), K replikas izvÄles sarežģītÄ«ba ir O(N K) ~ O(N2).
KvadrÄtiskÄ sarežģītÄ«ba ir slikta, taÄu to var uzlabot. Lai to izdarÄ«tu, mÄs veidosim par svaru summÄm. Tiks iegÅ«ts koks ar dziļumu lg N, kura lapÄs bÅ«s replikas atsvari, bet atlikuÅ”ajos mezglos - daļÄjÄs summas, lÄ«dz visu svaru summai koka saknÄ. PÄc tam mÄs Ä£enerÄjam nejauÅ”u skaitli no 0 lÄ«dz visu svaru summai, atrodam i-to reprodukciju, noÅemam to no koka un atkÄrtojam procedÅ«ru, lai atrastu atlikuÅ”Äs kopijas. Izmantojot Å”o algoritmu, koka veidoÅ”anas sarežģītÄ«ba ir O(N), i-tÄs replikas atraÅ”anas un izÅemÅ”anas no koka sarežģītÄ«ba ir O(lg N), K replikas izvÄles sarežģītÄ«ba ir O(N + K lg N) ~ O(N lg N) .
LineÄrÄ logaritma sarežģītÄ«ba ir labÄka nekÄ kvadrÄtiskÄ sarežģītÄ«ba, Ä«paÅ”i lielam K.
Tas ir Å”is algoritms ClusterClient bibliotÄkas no projekta "". (Tur koks ir iebÅ«vÄts O(N lg N), taÄu tas neietekmÄ algoritma galÄ«go sarežģītÄ«bu.)
Uzdevums 2. Zebra
Bija nepiecieÅ”ams piedÄvÄt algoritmu efektÄ«vai dokumentu ŔķiroÅ”anai atmiÅÄ pÄc patvaļīga neindeksÄta lauka:
JÅ«su komandai ir uzdots izstrÄdÄt dalÄ«tu atmiÅÄ esoÅ”o dokumentu datubÄzi. IzplatÄ«ta darba slodze bÅ«tu atlasÄ«t populÄrÄkos N dokumentus, kas sakÄrtoti pÄc patvaļīga (neindeksÄta) ciparu lauka no M izmÄra kolekcijas (parasti N <100 << M). Nedaudz retÄka darba slodze bÅ«tu atlasÄ«t labÄko N pÄc tam, kad tiek izlaisti populÄrÄkie S dokumenti (S ~ N).
PiedÄvÄjiet algoritmu Å”Ädu vaicÄjumu efektÄ«vai izpildei. NovÄrtÄjiet tÄ skaitļoÅ”anas sarežģītÄ«bu, izmantojot lielo O apzÄ«mÄjumu vidÄjÄ gadÄ«jumÄ un sliktÄkajÄ gadÄ«jumÄ.
RisinÄjuma analÄ«ze (video)
SÄkot no 34:50, tikai 6 minÅ«tes:
RisinÄjuma analÄ«ze (teksts)
Virsmas risinÄjums: kÄrtojiet visus dokumentus (piemÄram, ar ), pÄc tam paÅemiet N+S dokumentus. Å ajÄ gadÄ«jumÄ Å”Ä·iroÅ”anas sarežģītÄ«ba ir vidÄji O(M lg M), sliktÄkajÄ gadÄ«jumÄ O(M2).
AcÄ«mredzami, ka sakÄrtot visus M dokumentus un pÄc tam paÅemt tikai nelielu daļu no tiem ir neefektÄ«vi. Lai nesakÄrtotu visus dokumentus, ir piemÄrots algoritms , kas atlasÄ«s N + S nepiecieÅ”amos dokumentus (tos var kÄrtot pÄc jebkura algoritma). Å ajÄ gadÄ«jumÄ sarežģītÄ«ba vidÄji samazinÄsies lÄ«dz O(M), savukÄrt sliktÄkajÄ gadÄ«jumÄ paliks nemainÄ«gs.
TomÄr jÅ«s varat to izdarÄ«t vÄl efektÄ«vÄk - izmantojiet algoritmu . Å ajÄ gadÄ«jumÄ pirmie N+S dokumenti tiek pievienoti min- vai max-heap (atkarÄ«bÄ no kÄrtoÅ”anas virziena), un pÄc tam katrs nÄkamais dokuments tiek salÄ«dzinÄts ar koka sakni, kurÄ ir paÅ”reizÄjais minimÄlais vai maksimÄlais dokuments, un vajadzÄ«bas gadÄ«jumÄ pievieno kokam. Å ajÄ gadÄ«jumÄ sarežģītÄ«ba sliktÄkajÄ gadÄ«jumÄ, kad nepÄrtraukti jÄpÄrbÅ«vÄ koks, ir O(M lg M), sarežģītÄ«ba vidÄji ir O(M), kÄ ar Quickselect.
TomÄr kaudzes straumÄÅ”ana izrÄdÄs efektÄ«vÄka, jo praksÄ lielÄko daļu dokumentu var izmest, neatjaunojot kaudzi pÄc vienas salÄ«dzinÄÅ”anas ar tÄs saknes elementu. Å Äda ŔķiroÅ”ana realizÄta Kontur izstrÄdÄtajÄ un lietotajÄ Zebra in-memory dokumentu datubÄzÄ.
Uzdevums 3. Valsts mijmaiÅas darÄ«jumi
Bija nepiecieÅ”ams piedÄvÄt visefektÄ«vÄko stÄvokļu maiÅas algoritmu:
JÅ«su komandai ir uzdots izstrÄdÄt izdomÄtu stÄvokļa apmaiÅas mehÄnismu sadalÄ«tam N mezglu klasterim. I-tÄ mezgla stÄvoklis jÄpÄrnes uz (i+1)-to mezglu, N-tÄ mezgla stÄvoklis jÄpÄrnes uz pirmo mezglu. VienÄ«gÄ atbalstÄ«tÄ operÄcija ir stÄvokļa mijmaiÅa, kad divi mezgli apmainÄs ar stÄvokļiem atomiski. Ir zinÄms, ka stÄvokļa maiÅa aizÅem M milisekundes. Katrs mezgls jebkurÄ brÄ«dÄ« var piedalÄ«ties vienÄ stÄvokļu mijmaiÅÄ.
Cik ilgs laiks nepiecieÅ”ams, lai pÄrsÅ«tÄ«tu visu klastera mezglu stÄvokļus?
RisinÄjuma analÄ«ze (teksts)
Virsmas risinÄjums: apmainÄ«ties ar pirmÄ un otrÄ elementa stÄvokļiem, tad pirmÄ un treÅ”Ä, tad pirmÄ un ceturtÄ, un tÄ tÄlÄk. PÄc katras apmaiÅas viena elementa stÄvoklis bÅ«s vÄlamajÄ pozÄ«cijÄ. Jums ir jÄveic O(N) permutÄcijas un jÄpavada O(N M) laiks.
LineÄrais laiks ir garÅ”, tÄpÄc elementu stÄvokļus var apmainÄ«t pa pÄriem: pirmo ar otro, treÅ”o ar ceturto utt. PÄc katras stÄvokļa maiÅas katrs otrais elements bÅ«s pareizajÄ pozÄ«cijÄ. JÄizveido O(lg N) permutÄcijas un jÄpavada O(M lg N) laiks.
TaÄu ir iespÄjams maiÅu padarÄ«t vÄl efektÄ«vÄku ā nevis lineÄrÄ, bet konstantÄ laikÄ. Lai to izdarÄ«tu, pirmajÄ solÄ« ir jÄmaina pirmÄ elementa stÄvoklis ar pÄdÄjo, otrÄ ar priekÅ”pÄdÄjo un tÄ tÄlÄk. PÄdÄjÄ elementa stÄvoklis bÅ«s pareizajÄ pozÄ«cijÄ. Un tagad mums ir jÄapmaina otrÄ elementa stÄvoklis ar pÄdÄjo, treÅ”Ä ar priekÅ”pÄdÄjo un tÄ tÄlÄk. PÄc Ŕīs apmaiÅas kÄrtas visu elementu stÄvokļi bÅ«s pareizÄ stÄvoklÄ«. KopÄ bÅ«s O(2M) ~ O(1) permutÄcijas.
Å Äds risinÄjums nemaz nepÄrsteigs matemÄtiÄ·i, kurÅ” joprojÄm atceras, ka rotÄcija ir divu aksiÄlu simetriju kompozÄ«cija. Starp citu, tas ir triviÄli vispÄrinÄts nobÄ«dei nevis pa vienu, bet pa K <N pozÄ«cijÄm. (KÄ tieÅ”i, rakstiet komentÄros.)
Vai jums patika mÄ«klas? Vai jÅ«s zinÄt citus risinÄjumus? Dalieties komentÄros.
Un beigÄs ir dažas noderÄ«gas saites:
- uzzinÄt vairÄk par kontÅ«rÄ
- skatiet iekÅ”Äjos ierakstus par sadalÄ«tajÄm sistÄmÄm
- skatÄ«ties video lekciju cikluĀ»
- abonÄjiet mÅ«su
Avots: www.habr.com