Zachitika masiku angapo apitawo Msonkhano wa Hydra. Anyamata ochokera ku Gulu la JUG.ru adayitana olankhula maloto (Leslie Lamport! Cliff Click! Martin Kleppmann!) Ndipo adapereka masiku awiri kugawa machitidwe ndi makompyuta. Kontur anali m'modzi mwa atatu omwe adagwirizana nawo pamsonkhanowu. Tinakambitsirana m’nyumba yosungiramo zinthu zakale, kukambitsirana za malo athu osungiramo zinthu zogaŵidwa, kuseŵera bingo, ndi kuthetsa ma puzzles.

Ili ndi positi yokhala ndi kusanthula kwa ntchito pa kontur kochokera kwa wolemba zolemba zawo. Ndani anali pa Hydra - ichi ndi chifukwa chanu kukumbukira zochitika zosangalatsa, amene sanali - mwayi kutambasula ubongo wanu chachikulu O- chidziwitso.

Panalinso anthu amene anang'amba tchatichi kuti alembe zomwe akufuna. Sindikuchita nthabwala - adapereka mapepala awa kuti atsimikizire:

Panali ntchito zitatu zonse:

• za kusankha zofaniziridwa ndi zolemera kuti zigwirizane ndi katundu
• za kusanja zotsatira za mafunso ndi database ya mu-memory
• pa kusamutsidwa kwa boma mu dongosolo logawidwa ndi ring topology

Ntchito 1. ClusterClient

Zinali zofunikira kuti tipereke lingaliro la algorithm pakusankha koyenera kwa K kuchokera ku N zolemetsa za dongosolo logawidwa:

Gulu lanu lili ndi ntchito yopanga laibulale yamakasitomala yamagulu ambiri a N node. Laibulaleyo imatha kutsata ma metadata osiyanasiyana okhudzana ndi ma node (mwachitsanzo, kuchedwa kwawo, 4xx/5xx mayankhidwe, ndi zina zotero) ndikuwapatsa zolemera zoyandama W1..WN. Pofuna kuthandizira njira yophatikizira nthawi imodzi, laibulale iyenera kusankha ma nodi a K a N mwachisawawa-mwayi wosankhidwa uyenera kukhala wolingana ndi kulemera kwa mfundo.

Lingalirani ma aligorivimu kuti musankhe node bwino. Yerekezerani zovuta zake zowerengera pogwiritsa ntchito zolemba zazikulu za O.

Chifukwa chiyani zonse zili mu Chingerezi?

Chifukwa mu mawonekedwe awa ochita nawo msonkhano adamenyana nawo komanso chifukwa Chingerezi chinali chinenero chovomerezeka cha Hydra. Ntchitozo zinkawoneka motere:

Tengani pepala ndi pensulo, ganizirani, musathamangire kutsegula owononga nthawi yomweyo 🙂

Kusanthula kwa yankho (kanema)

Kuyambira 5:53, mphindi 4 zokha:

Ndipo umu ndi momwe anyamata omwe ali ndi tchatichi adayankhira yankho lawo:

Kusanthula kwa yankho (mawu)

Yankho lotsatirali lili pamwamba: werengerani zolemera za zofananira zonse, pangani manambala mwachisawawa kuchokera pa 0 mpaka kuchuluka kwa zolemera zonse, kenako sankhani i-replica kotero kuti kuchuluka kwa zolemera zofananira kuchokera ku 0 mpaka (i-1) th. ndi zosakwana nambala mwachisawawa, ndi chiŵerengero cha zolemera replica kuchokera 0 mpaka i-th - kuposa izo. Chifukwa chake mutha kusankha chofananira chimodzi, ndikusankha chotsatira, muyenera kubwereza ndondomeko yonseyo osaganiziranso zomwe mwasankha. Ndi ma aligorivimu otere, zovuta zosankha choyimira chimodzi ndi O(N), zovuta kusankha K replicas ndi O(N K) ~ O(N2).

Kuvuta kwa Quadratic ndikoyipa, koma kumatha kuwongolera. Kuti tichite izi, tidzamanga mtengo wagawo kwa miyeso yolemera. Mtengo wakuya lg N udzapezedwa, m'masamba ake padzakhala zolemera zofananira, ndipo m'malo otsala - ndalama zochepa, mpaka kuchuluka kwa zolemera zonse pamizu ya mtengo. Kenaka, timapanga nambala yosasinthika kuchokera ku 0 kufika ku chiwerengero cha zolemera zonse, kupeza i-th replica, kuchotsa pamtengo, ndikubwereza ndondomekoyi kuti tipeze zotsalira zotsalira. Ndi algorithm iyi, zovuta zomangira mtengo ndi O(N), zovuta kupeza i-th replica ndikuchotsa pamtengo ndi O(lg N), zovuta kusankha K replicas ndi O(N + K). lg N) ~ O(N lg N) .

Kuvuta kwa Linear-log ndikwabwino kuposa quadratic complexity, makamaka kwa K.

Ndi algorithm iyi kukhazikitsidwa mu code malaibulale a ClusterClient ochokera ku polojekitiyi "East". (Kumeneko, mtengowo umamangidwa mu O (N lg N), koma izi sizikhudza zovuta zomaliza za algorithm.)

Ntchito 2. Mbidzi

Kunali kofunikira kupereka lingaliro la algorithm yosankha bwino zolembedwa m'makumbukidwe ndi gawo losawerengeka:

Gulu lanu liri ndi ntchito yokonza zosungiramo zosungiramo zokumbukira. Ntchito yodziwika bwino ingakhale kusankha zikalata zapamwamba za N zosankhidwa ndi manambala mokhazikika (osasankhidwa) kuchokera pamndandanda wa kukula kwa M (nthawi zambiri N <100 << M). Ntchito yocheperako pang'ono ingakhale kusankha pamwamba N mutadumpha zolemba zapamwamba za S (S ~ N).

Funsani algorithm kuti muyankhe mafunso oterowo moyenera. Yerekezerani zovuta zake zowerengera pogwiritsa ntchito zolemba zazikulu za O nthawi zambiri komanso zochitika zoyipa kwambiri.

Kusanthula kwa yankho (kanema)

Kuyambira 34:50, mphindi 6 zokha:

Kusanthula kwa yankho (mawu)

Yankho lapamwamba: sungani zolemba zonse (mwachitsanzo ndi kutchfun), kenako tengani zikalata za N+S. Pachifukwa ichi, zovuta za kusanja zimakhala pafupifupi O(M lg M), poyipa kwambiri O(M2).

Ndizodziwikiratu kuti kusanja zolemba zonse za M ndikungotenga gawo laling'ono chabe sikuthandiza. Kuti musasinthe zolemba zonse, algorithm ndiyoyenera kusankha mwachangu, yomwe idzasankhe N + S ya zolemba zomwe mukufuna (zikhoza kusankhidwa ndi algorithm iliyonse). Pachifukwa ichi, zovutazo zidzatsika mpaka O (M) pafupifupi, pamene zoipitsitsa zidzakhala zofanana.

Komabe, mutha kuchita bwino kwambiri - gwiritsani ntchito algorithm binary mulu kusonkhana. Pachifukwa ichi, zolemba zoyamba za N + S zimawonjezeredwa ku min- kapena max-mulu (malingana ndi njira yamtundu), ndiyeno chikalata chilichonse chotsatira chikufanizidwa ndi muzu wa mtengo, womwe uli ndi zolemba zochepa kapena zochepa zomwe zilipo panopa, ndipo amawonjezeredwa kumtengo ngati kuli kofunikira. Pankhaniyi, zovuta muzovuta kwambiri, pamene mukuyenera kumanganso mtengowo nthawi zonse, ndi O (M lg M), zovutazo pafupifupi ndi O (M), monga momwe zimakhalira ndi kusankha mwamsanga.

Komabe, kukhamukira kwa mulu kumakhala kothandiza kwambiri chifukwa chakuti pochita zambiri zolembazo zitha kutayidwa popanda kumanganso muluwo pambuyo poyerekeza kumodzi ndi mizu yake. Kusanja kotereku kumayendetsedwa muzolemba za Zebra mu-memory zomwe zidapangidwa ndikugwiritsidwa ntchito ku Kontur.

Ntchito 3. Kusinthana kwa boma

Zinali zofunikira kupereka algorithm yothandiza kwambiri yosinthira mayiko:

Gulu lanu lili ndi ntchito yokonza njira yabwino yosinthira dziko lamagulu ogawidwa a N node. Chikhalidwe cha i-th node chiyenera kusamutsidwa ku (i + 1) -th node, chikhalidwe cha N-th chiyenera kusamutsidwa ku mfundo yoyamba. Ntchito yokhayo yothandizira ndikusinthana kwa boma pamene mfundo ziwiri zimasinthana ndi mayiko awo atomu. Zimadziwika kuti kusinthana kwa boma kumatenga M milliseconds. Node iliyonse imatha kutenga nawo gawo pakusinthana kwa boma nthawi iliyonse.

Zimatenga nthawi yayitali bwanji kusamutsa zigawo za node zonse mumagulu?

Kusanthula kwa yankho (mawu)

Yankho lapamwamba: kusinthanitsa zigawo za chinthu choyamba ndi chachiwiri, kenako choyamba ndi chachitatu, kenako choyamba ndi chachinayi, ndi zina zotero. Pambuyo pa kusinthanitsa kulikonse, chikhalidwe cha chinthu chimodzi chidzakhala pamalo omwe mukufuna. Muyenera kupanga zilolezo za O(N) ndikuwononga nthawi ya O(N M).

Linear nthawi ndi yaitali, kotero inu mukhoza kusinthana zigawo za zinthu awiriawiri: choyamba ndi chachiwiri, chachitatu ndi chachinayi, ndi zina zotero. Pambuyo pa kusinthana kulikonse kwa boma, chinthu chachiwiri chilichonse chidzakhala pamalo abwino. Muyenera kupanga zololeza za O(lg N) ndikuwononga nthawi ya O(Mlg N).

Komabe, ndizotheka kupangitsa kusinthako kukhala kothandiza kwambiri - osati pamzere, koma nthawi zonse. Kuti muchite izi, pa sitepe yoyamba, muyenera kusinthanitsa chikhalidwe cha chinthu choyamba ndi chomaliza, chachiwiri ndi penultimate, ndi zina zotero. Chikhalidwe cha chinthu chomaliza chidzakhala cholondola. Ndipo tsopano tiyenera kusinthanitsa chikhalidwe cha chinthu chachiwiri ndi chomaliza, chachitatu ndi chotsatira, ndi zina zotero. Pambuyo pakusinthana uku, zigawo za zinthu zonse zidzakhala bwino. Padzakhala O(2M) ~ O(1) zilolezo zonse.

Yankho loterolo silingadabwitse konse katswiri wa masamu yemwe amakumbukirabe kuti kusinthasintha kumapangidwa ndi ma axial symmetries awiri. Mwa njira, zimasinthidwa pang'ono kuti zisinthidwe osati ndi m'modzi, koma ndi K <N maudindo. (Lembani mu ndemanga momwe ndendende.)

Kodi mumakonda zoseweretsa? Kodi mukudziwa njira zina? Gawani nawo ndemanga.

Ndipo apa pali maulalo othandiza pomaliza:

• Dziwani zambiri za chitukuko cha zomangamanga mu contour
• onani zolemba zamkati zowulutsa ndi malipoti za machitidwe ogawidwa
• onerani mndandanda wankhani zamavidiyoMa aligorivimu osazolowereka kwa anthu wamba»
• lembetsani ku yathu njira mu Telegram

Source: www.habr.com