Okazis antaŭ kelkaj tagoj Hidra Konferenco. La uloj de la Grupo JUG.ru invitis sonĝparolantojn (Leslie Lamport! Cliff Click! Martin Kleppmann!) kaj dediĉis du tagojn al distribuitaj sistemoj kaj komputado. Kontur estis unu el la tri partneroj de la konferenco. Ni parolis ĉe la budo, parolis pri nia distribuita stokado, ludis bingo kaj solvis enigmojn.

Ĉi tio estas afiŝo kun analizo de taskoj ĉe la stando Kontur de la aŭtoro de ilia teksto. Kiu estis sur la Hidro - jen via kialo por memori la agrablan sperton, kiu ne estis - ŝanco streĉi vian cerbon granda O-notacio.

Ekzistis eĉ partoprenantoj, kiuj malmuntis la paperfolion en lumbildojn por noti sian decidon. Mi ne ŝercas - ili transdonis ĉi tiun stakon da papero por kontrolo:

Estis tri taskoj entute:

• pri elektado de kopioj per pezoj por ŝarĝbalancado
• pri ordigo de serĉrezultoj kontraŭ enmemora datumbazo
• pri ŝtattransigo en distribuita sistemo kun ringa topologio

Tasko 1. ClusterClient

Estis necese proponi algoritmon por la efika elekto de K el N pezbalancitaj kopioj de distribuita sistemo:

Via teamo estas taskita evoluigi klientan bibliotekon por amase distribuita aro de N nodoj. La biblioteko konservus trakon de diversaj metadatenoj asociitaj kun nodoj (ekz., iliaj latentecoj, 4xx/5xx respondaj indicoj, ktp.) kaj asignus glitkomajn pezojn W1..WN al ili. Por apogi la samtempan ekzekutstrategion, la biblioteko devus povi elekti K el N nodoj hazarde - ebleco de esti elektita devus esti proporcia al la pezo de nodo.

Proponu algoritmon por elekti nodojn efike. Taksi ĝian komputilan kompleksecon uzante grandan O-notacion.

Kial ĉio estas en la angla?

Ĉar en ĉi tiu formo la kongresanoj batalis kun ili kaj ĉar la angla estis la oficiala lingvo de Hidro. La taskoj aspektis jene:

Prenu paperon kaj krajonon, pensu, ne rapidu malfermi spoilers tuj 🙂

Analizo de la solvo (vidbendo)

Ekde 5:53, nur 4 minutoj:

Kaj jen kiel la uloj kun la paperfolio prezentis sian solvon:

Analizo de la solvo (teksto)

La sekva solvo kuŝas sur la surfaco: sumigu la pezojn de ĉiuj kopioj, generu hazardan nombron de 0 al la sumo de ĉiuj pezoj, tiam elektu i-replikon tia ke la sumo de kopiopezoj de 0 ĝis (i-1)-a estas malpli ol hazarda nombro, kaj la sumo de kopiaj pezoj de 0 ĝis i-a - pli ol ĝi. Do eblos elekti unu kopion, kaj por elekti la sekvan, vi devas ripeti la tutan proceduron sen konsideri la elektitan kopion. Kun tia algoritmo, la komplekseco de elektado de unu kopio estas O (N), la komplekseco de elektado de K kopioj estas O (N K) ~ O (N2).

Kvadrata komplekseco estas malbona, sed ĝi povas esti plibonigita. Por fari tion, ni konstruos segmentarbo por sumoj de pezoj. Arbo de profundo lg N estos akirita, en kies folioj estos kopiaj pezoj, kaj en la ceteraj nodoj - partaj sumoj, ĝis la sumo de ĉiuj pezoj ĉe la radiko de la arbo. Poste, ni generas hazardan nombron de 0 ĝis la sumo de ĉiuj pezoj, trovas la i-an kopion, forigas ĝin de la arbo kaj ripetas la proceduron por trovi la ceterajn kopiojn. Kun ĉi tiu algoritmo, la komplekseco de konstruado de arbo estas O (N), la komplekseco de trovado de la i-a kopio kaj forigo de ĝi de la arbo estas O (lg N), la komplekseco de elektado de K kopioj estas O (N + K). lg N) ~ O(N lg N) .

Linear-loga komplekseco estas pli bela ol kvadrata komplekseco, precipe por granda K.

Ĝi estas ĉi tiu algoritmo efektivigita en kodo ClusterClient-bibliotekoj de la projekto "Oriento". (Tie, ​​la arbo estas konstruita en O (N lg N), sed tio ne influas la finan kompleksecon de la algoritmo. )

Tasko 2. Zebro

Necesis proponi algoritmon por efika ordigo de dokumentoj en memoro per arbitra ne-indeksita kampo:

Via teamo estas taskigita evoluigi fragmentan en-memoran dokumentdatumbazon. Ofta laborkvanto estus elekti suprajn N dokumentojn ordigitajn per arbitra (ne-indeksita) nombra kampo el kolekto de grandeco M (kutime N < 100 << M). Iomete malpli ofta laborkvanto estus elekti supran N post transsalti suprajn S-dokumentojn (S ~ N).

Proponu algoritmon por ekzekuti tiajn demandojn efike. Taksi ĝian komputilan kompleksecon uzante grandan O-notacion en la averaĝa kazo kaj la plej malbonaj kazscenaroj.

Analizo de la solvo (vidbendo)

Ekde 34:50, nur 6 minutoj:

Analizo de la solvo (teksto)

Surfaca solvo: ordigu ĉiujn dokumentojn (ekzemple kun rapidvorto), tiam prenu N+S dokumentojn. En ĉi tiu kazo, la komplekseco de ordigo estas averaĝe O (M lg M), ĉe la plej malbona O (M2).

Estas evidente, ke ordigi ĉiujn M-dokumentojn kaj poste preni nur malgrandan parton de ili estas malefike. Por ne ordigi ĉiujn dokumentojn, algoritmo taŭgas rapida elekto, kiu elektos N + S el la dezirataj dokumentoj (ili povas esti ordigitaj per iu ajn algoritmo). En ĉi tiu kazo, la komplekseco malpliiĝos al O (M) averaĝe, dum la plej malbona kazo restos la sama.

Tamen vi povas fari ĝin eĉ pli efike - uzu la algoritmon duuma amaso fluanta. En ĉi tiu kazo, la unuaj N+S dokumentoj estas aldonitaj al min- aŭ maksimuma amaso (depende de la ordigdirekto), kaj tiam ĉiu sekva dokumento estas komparita kun la radiko de la arbo, kiu enhavas la nunan minimuman aŭ maksimuman dokumenton, kaj estas aldonita al la arbo se necese. . En ĉi tiu kazo, la komplekseco en la plej malbona kazo, kiam vi devas konstante rekonstrui la arbon, estas O(M lg M), la komplekseco averaĝe estas O(M), kiel kun rapida elekto.

Tamen, amasfluo rezultas esti pli efika pro la fakto ke praktike la plej multaj el la dokumentoj povas esti forĵetitaj sen rekonstruado de la amaso post ununura komparo kun ĝia radika elemento. Tia ordigo estas efektivigita en la Zebra en-memora dokumentdatumbazo evoluigita kaj uzita en Kontur.

Tasko 3. Ŝtataj interŝanĝoj

Estis necese proponi la plej efikan algoritmon por ŝanĝantaj ŝtatoj:

Via teamo estas taskita evoluigi fantazian ŝtatinterŝanĝan mekanismon por distribuita areto de N nodoj. La stato de la i-a nodo devus esti transdonita al la (i+1)-a nodo, la stato de la N-a nodo devus esti transdonita al la unua nodo. La nura subtenata operacio estas la ŝtatŝanĝo kiam du nodoj interŝanĝas siajn statojn atome. Estas konata ke ŝtatŝanĝo prenas M milisekundojn. Ĉiu nodo povas partopreni en ununura ŝtatŝanĝo en iu ajn donita momento.

Kiom da tempo necesas por translokigi la statojn de ĉiuj nodoj en areto?

Analizo de la solvo (teksto)

Surfaca solvo: interŝanĝu la statojn de la unua kaj dua elemento, poste la unua kaj tria, poste la unua kaj kvara, ktp. Post ĉiu interŝanĝo, la stato de unu elemento estos en la dezirata pozicio. Vi devas fari O(N) permutojn kaj elspezi O(N M) tempon.

Linia tempo estas longa, do vi povas interŝanĝi la statojn de elementoj en paroj: la unua kun la dua, la tria kun la kvara, ktp. Post ĉiu ŝtata interŝanĝo, ĉiu dua elemento estos en la ĝusta pozicio. Vi devas fari O(lg N) permutojn kaj elspezi O(M lg N) tempon.

Tamen, eblas fari la movon eĉ pli efika - ne en linia, sed en konstanta tempo. Por fari tion, je la unua paŝo, vi devas interŝanĝi la staton de la unua elemento kun la lasta, la dua kun la antaŭlasta, ktp. La stato de la lasta elemento estos en la ĝusta pozicio. Kaj nun ni devas interŝanĝi la staton de la dua elemento kun la lasta, la tria kun la antaŭlasta, ktp. Post ĉi tiu rondo de interŝanĝoj, la statoj de ĉiuj elementoj estos en la ĝusta pozicio. Estos O(2M) ~ O(1) permutaĵoj entute.

Tia solvo tute ne surprizos matematikiston, kiu ankoraŭ memoras, ke rotacio estas konsisto de du aksaj simetrioj. Cetere, ĝi estas banale ĝeneraligita por movo ne per unu, sed per K < N pozicioj. (Skribu en la komentoj kiel precize.)

Ĉu vi ŝatis enigmojn? Ĉu vi konas aliajn solvojn? Kunhavigu en la komentoj.

Kaj jen kelkaj utilaj ligiloj finfine:

• lerni pli pri disvolviĝo de infrastrukturoj en konturo
• vidu registrojn de internaj flugfolio kun raportoj pri distribuitaj sistemoj
• spektu la serion de videoprelegojNekutimaj algoritmoj por ordinaraj homoj»
• abonu nian kanalo en Telegramo

fonto: www.habr.com