Waxay dhacday maalmo ka hor . Ragga ka socda kooxda JUG.ru waxay martiqaadeen kuwa ku hadla riyada (Leslie Lamport! Cliff Click! Martin Kleppmann!) waxayna u hureen laba maalmood si ay u qaybiyaan nidaamyada iyo xisaabinta. Kontur waxa uu ahaa mid ka mid ah saddexda wada-hawlgalayaasha shirka. Waanu ka hadalnay goobta, waxaanu ka hadalnay kaydintayada la qaybiyay, waxaanu ciyaarnay bingo, oo aanu xalinay halxiraalaha.
Tani waa qoraal ay ku qoran tahay falanqaynta hawlaha Kontur ka taagan qoraaga qoraalkooda. Yaa ku jiray Hydra - tani waa sababta aad u xasuusato waayo-aragnimada wacan, oo aan ahayn - fursad aad ku fidin karto maskaxdaada weyn O-tilmaan.
Xataa waxaa jiray ka qaybgalayaasha oo kala furfuray xaashida sawirada sawirada si ay u qoraan go'aankooda. Kaftan maayo - waxay ku wareejiyeen warqadan is dul saaran si loo xaqiijiyo:
Guud ahaan waxaa jiray saddex hawlood:
- ku saabsan xulashada nuqullada miisaannada loogu talagalay dheellitirka rarka
- ku saabsan kala soocida natiijooyinka weydiimaha ee ka dhanka ah kaydka kaydka xusuusta
- ku saabsan wareejinta gobolka ee nidaamka qaybsan oo leh topology giraan ah
Hawsha 1. Kooxda Macmiilka
Waxay ahayd lagama maarmaan in la soo jeediyo algorithm xulashada hufan ee K ee nuqullada Miisaanka leh ee nidaamka qaybsan:
Kooxdaada waxaa loo xilsaaray inay horumariyaan maktabad macmiil si ay u helaan koox N nodes ah oo si weyn loo qaybiyey. Maktabadu waxay la socon doontaa xog badan oo kala duwan oo la xidhiidha qanjidhada (tusaale, daahitaankooda, 4xx/5xx heerka jawaab celinta, iwm.) oo waxay ku meelayn doontaa miisaanyada dul sabeynaya W1..WN iyaga. Si loo taageero istiraatijiyadda fulinta ee isku xigta, maktabaddu waa inay awood u yeelataa inay si aan kala sooc lahayn u soo xulato qanjidhada K ee N - fursadda lagu dooranayo waa inay la mid tahay miisaanka noodhka.
Soo jeedi algorithm si aad si hufan u doorato noodhka. Qiyaas kakanaanta xisaabinta iyadoo la adeegsanayo qoraal weyn.
Maxay wax walba ugu qoran yihiin Ingiriisi?
Sababtoo ah qaabkan ka qaybgalayaasha shirku waxay kula dagaalameen iyaga iyo sababtoo ah Ingiriisiga ayaa ahaa luqadda rasmiga ah ee Hydra. Hawshu waxay u ekayd sidan:
Qaado warqad iyo qalin, ka fakar, ha ku degdegin inaad furto qaswadayaasha isla markiiba π
Falanqaynta xalka (video)
Laga bilaabo 5:53, kaliya 4 daqiiqo:
Oo waa kan sida nimankii sawir-gacmeedka watay ay u dejiyeen xalkooda:
Falanqaynta xalka (qoraal)
Xalkan soo socdaa waxa uu yaalaa dusha sare: isu geynta miisaanka dhammaan nuqullada, ka soo saar tiro aan toos ahayn oo ka bilaabma 0 ilaa wadarta dhammaan miisaannada, ka dibna dooro i- nuqul ka mid ah wadarta miisaannada nuqullada laga bilaabo 0 ilaa (i-1) th waa ka yar yahay tiro random ah, iyo wadarta miisaannada nuqul ka ah 0 ilaa i-th - in ka badan. Markaa waxaa suurtogal ah in la doorto hal nuqul, oo aad doorato midka ku xiga, waxaad u baahan tahay inaad ku celiso nidaamka oo dhan adigoon tixgelineynin nuqulka la doortay. Algorithm-ka noocan oo kale ah, kakanaanta doorashada hal nuqul waa O(N), kakanaanta doorashada K replicas waa O(N K) ~ O(N2).
Kakanaanta afar geesoodka waa xun, laakiin waa la hagaajin karaa. Si tan loo sameeyo, waan dhisi doonaa marka la isu geeyo miisaanka. Geed qoto dheer lg N ayaa la heli doonaa, caleemaha kuwaas oo ay jiri doonaan miisaanno nuqul ah, iyo qanjidhada soo haray - wadarta qayb ahaan, ilaa wadarta dhammaan miisaannada xididka geedka. Marka xigta, waxaan ka soo saareynaa lambar random laga bilaabo 0 ilaa wadarta dhammaan miisaannada, hel nuqulka i-th, ka saar geedka, oo ku celi nidaamka si aan u helno nuqullada haray. Algorithm-kan, kakanaanta dhismaha geedku waa O(N), kakanaanta helitaanka i-th replica iyo ka saarida geedka waa O (lg N), kakanaanta xulashada K nuqulada waa O(N + K). lg N) ~ O(N lg N) .
Kakanaanta-logga-tooska ah way ka fiican tahay kakanaanta afargeesoodka ah, gaar ahaan kuwa waaweyn ee K.
Waa algorithm kan Maktabadaha ClisterClient ee mashruuca"" (Halkaas, geedku wuxuu ku dhisan yahay O (N lg N), laakiin tani ma saameynayso kakanaanta kama dambaysta ah ee algorithm.)
Hawsha 2. Zebra
Waxay ahayd lagama maarmaan in la soo jeediyo algorithm si loo kala saaro dokumentiyada si hufan ee xusuusta iyadoo la adeegsanayo goob aan tusin lahayn:
Kooxdaada waxaa loo xilsaaray inay horumariyaan xogta dukumeentiga xusuusta ee la wadaagay. Culayska shaqada ee caadiga ah waa in la doorto dukumeentiyada sare ee N oo lagu kala soocaa goob tirooyin aan loo meel dayin (aan la tilmaamin) laga soo bilaabo ururinta cabbirka M (sida caadiga ah N <100 << M). Culays shaqo oo yar oo ka yar ayaa ah in la doorto N sare ka dib marka la boodo dukumeentiyada S ee sare (S ~ N).
Soo jeedi algorithm si loo fuliyo weydiimahan oo kale si hufan. Ku qiyaas kakanaanta xisaabinta iyadoo la adeegsanayo tilmaanta O weyn ee celceliska kiiska iyo xaaladaha ugu xun.
Falanqaynta xalka (video)
Laga bilaabo 34:50, kaliya 6 daqiiqo:
Falanqaynta xalka (qoraal)
Xalka dusha sare: kala saar dhammaan dukumeentiyada (tusaale ahaan ), ka dibna qaado dukumentiyada N+S. Xaaladdan oo kale, kakanaanta kala-soocidda waa celcelis ahaan O(M lg M), oo ugu xun O(M2).
Way caddahay in kala-soocidda dhammaan dukumeentiyada M ka dibna qaadashada qayb yar oo ka mid ah ay tahay mid aan waxtar lahayn. Si aan loo kala saarin dhammaan dukumiintiyada, algorithm ayaa ku habboon , kaas oo dooran doona N + S dukumentiyada la rabo (waxaa lagu kala saari karaa algorithm kasta). Xaaladdan oo kale, kakanaanta ayaa hoos u dhigi doonta O (M) celcelis ahaan, halka kiiskii ugu xumaa uu ahaan doono sidii hore.
Si kastaba ha ahaatee, waxaad samayn kartaa xitaa si waxtar leh - isticmaal algorithm . Xaaladdan oo kale, dukumiintiyada N + S ee ugu horreeya ayaa lagu daraa min- ama max-tuul (waxay kuxirantahay jihada nooca), ka dibna dukumeenti kasta oo xiga ayaa la barbar dhigayaa xididka geedka, kaas oo ka kooban dukumeentiga ugu yar ama ugu badan. waxaana lagu daraa geedka haddii loo baahdo. Xaaladdan oo kale, kakanaanta kiiska ugu xun, markaad tahay inaad si joogto ah u dhisto geedka, waa O (M lg M), kakanaanta celceliska waa O (M), sida dhakhso loo doorto.
Si kastaba ha noqotee, qulqulka qulqulka ayaa u muuqda inuu noqdo mid waxtar badan sababtoo ah xaqiiqda ah in badi dukumeentiyada la tuuri karo iyada oo aan dib loo dhisin tuubada ka dib marka la barbardhigo halbeegga asalka ah. Kala-soocidda noocan oo kale ah waxaa lagu hirgeliyay kaydka xogta dukumeentiga Zebra ee lagu sameeyay laguna isticmaalay Kontur.
Hawsha 3. Isdhaafsiga Gobolka
Waxay ahayd lagama maarmaan in la soo jeediyo algorithm-ka ugu waxtarka badan ee isbeddelka gobollada:
Kooxdaada waxaa loo xilsaaray in ay horumariyaan hab dawladeed oo qurux badan oo is dhaafsi ah oo loogu talagalay koox qaybsan oo N nood ah. Gobolka i-th node waa in loo wareejiyaa (i+1) -th node, gobolka N-th waa in loo wareejiyaa noodhka kowaad. Hawlgalka kaliya ee la taageeray waa isweydaarsiga gobolka marka laba nood ay isweydaarsadaan gobolladooda si atomiga ah. Waxaa la og yahay in isweydaarsiga gobolku uu qaato M millise seconds. Nood kastaa waxa uu awoodaa in uu ka qaybqaato hal is-beddelasho dawladeed wakhti kasta.
Intee in le'eg ayay qaadanaysaa in lagu wareejiyo gobolada dhammaan noodyada ee kutlada?
Falanqaynta xalka (qoraal)
Xalka dusha sare: isweydaarsiga gobolada curiyaha koowaad iyo labaad, ka dibna ka koowaad iyo saddexaad, ka dibna ka koowaad iyo afaraad, iyo wixii la mid ah. Isweydaarsi kasta ka dib, xaaladda hal element ayaa ku jiri doonta booska la rabo. Waa inaad samaysaa O(N) permutations oo aad waqti ku bixisaa O(N M).
Waqtiga tooska ah waa dheer yahay, markaa waxaad ku beddeli kartaa gobollada curiyeyaasha laba-labo: kan koowaad oo leh kan labaad, kan saddexaad oo leh kan afraad, iyo wixii la mid ah. Ka dib beddelka gobol kasta, qayb kasta oo labaad waxay ku jiri doontaa booska saxda ah. Waa inaad samaysaa O(lg N) permutations oo aad waqti ku bixisaa O(M lg N).
Si kastaba ha ahaatee, waxaa suurtagal ah in la sameeyo isbeddelka xitaa mid waxtar leh - maaha mid toosan, laakiin waqti joogto ah. Si tan loo sameeyo, tallaabada ugu horreysa, waxaad u baahan tahay inaad ku beddesho xaaladda curiyaha koowaad ee kan ugu dambeeya, kan labaadna kan ugu dambeeya, iyo wixii la mid ah. Xaaladda curiyaha ugu dambeeya wuxuu ahaan doonaa booska saxda ah. Oo hadda waxaan u baahan nahay in la beddelo xaaladda element labaad iyo kan ugu dambeeya, ka saddexaad oo leh penultimate, iyo wixii la mid ah. Ka dib wareegaan isweydaarsiga, gobolada dhammaan walxaha waxay ku jiri doonaan booska saxda ah. Waxaa jiri doona O(2M) ~ O(1) isugeynta guud.
Xalka noocan oo kale ah ma la yaabi doono xisaabyahan gabi ahaanba, kaas oo weli xusuusta in wareeggu uu yahay mid ka kooban laba calaamadood oo axial ah. Si kastaba ha ahaatee, si fudud ayaa loo soo koobay isbedel ma aha mid, laakiin boosaska K <N. (Faallooyinka ku qor sida saxda ah.)
Ma jeceshay xujooyinka? Ma garanaysaa xalal kale? La wadaag faallooyinka
Oo halkan waxaa ah qaar ka mid ah xiriiriyeyaasha waxtarka leh ee dhamaadka:
- wax badan ka baro koontoor
- eeg diiwaanka gudaha ku saabsan hababka loo qaybiyey
- daawo muxaadaro muqaal ah oo taxane ahΒ»
- subscribe noo saar
Source: www.habr.com