O ṣẹlẹ ni awọn ọjọ diẹ sẹhin . Awọn enia buruku lati JUG.ru Group pe ala agbohunsoke (Leslie Lamport! Cliff Tẹ! Martin Kleppmann!) Ati ti yasọtọ ọjọ meji lati pin awọn ọna šiše ati iširo. Kontur jẹ ọkan ninu awọn alabaṣiṣẹpọ alapejọ mẹta. A sọrọ ni iduro, sọrọ nipa ibi ipamọ ti a pin kaakiri, ṣere bingo, ati yanju awọn iṣoro.
Eyi jẹ ifiweranṣẹ pẹlu itupalẹ awọn iṣẹ-ṣiṣe ni iduro Contour lati ọdọ onkọwe ti ọrọ wọn. Fun awọn ti o ti wa si Hydra, eyi ni aye rẹ lati ranti awọn iriri igbadun; fun awọn ti ko ni, eyi ni aye lati na ọpọlọ rẹ nla O- akiyesi.
Paapaa awọn olukopa wa ti o ṣajọpọ iwe itẹwe sinu awọn ifaworanhan lati kọ ojutu wọn silẹ. Emi ko ṣe awada - wọn fi akopọ iwe yii silẹ fun ayewo:
Awọn iṣẹ-ṣiṣe mẹta ni apapọ:
- nipa yiyan awọn ẹda nipasẹ awọn iwọn fun iwọntunwọnsi fifuye
- nipa tito awọn abajade ibeere kan si ibi ipamọ data inu-iranti
- lori gbigbe ipinle ni eto pinpin pẹlu topology oruka
Iṣẹ-ṣiṣe 1. ClusterClient
O jẹ dandan lati dabaa algorithm kan fun yiyan daradara K jade ninu awọn ẹda iwuwo iwuwo ti eto pinpin:
Ẹgbẹ rẹ jẹ iṣẹ ṣiṣe pẹlu idagbasoke ile-ikawe alabara kan fun iṣupọ pinpin kaakiri ti awọn apa N. Ile-ikawe naa yoo tọju ọpọlọpọ awọn metadata ti o ni nkan ṣe pẹlu awọn apa (fun apẹẹrẹ, awọn lairi wọn, awọn oṣuwọn idahun 4xx/5xx, ati bẹbẹ lọ) ati fi awọn iwuwo aaye lilefoofo W1..WN si wọn. Lati le ṣe atilẹyin ilana ipaniyan nigbakanna, ile-ikawe yẹ ki o ni anfani lati mu awọn apa K ti N laileto — aye ti yiyan yẹ ki o jẹ ibamu si iwuwo ipade kan.
Ṣe imọran algorithm kan lati yan awọn apa daradara. Ṣe iṣiro idiju iširo rẹ nipa lilo akiyesi O nla.
Kini idi ti ohun gbogbo wa ni Gẹẹsi?
Nitoripe eyi ni bi awọn olukopa apejọ ṣe ja wọn ati nitori Gẹẹsi jẹ ede osise ti Hydra. Awọn iṣoro naa dabi eyi:
Mu iwe ati pencil, ronu, maṣe yara lati ṣii awọn apanirun lẹsẹkẹsẹ :)
Onínọmbà ti ojutu (fidio)
Bẹrẹ ni 5:53, iṣẹju 4 nikan:
Ati pe eyi ni bii awọn eniyan kanna ti o ni iwe afọwọkọ naa ṣe ipinnu ojutu wọn:
Itupalẹ ti ojutu (ọrọ)
Ojutu atẹle wa lori oke: apao awọn iwuwo ti gbogbo awọn ẹda, ṣe ina nọmba ID kan lati 0 si apapọ gbogbo awọn iwuwo, lẹhinna yan i-ẹda iru eyi ti apapọ awọn iwuwo ti awọn ẹda lati 0 si (i -1) th kere ju nọmba laileto, ati apapọ awọn iwuwo ti awọn ẹda lati 0 si i-th - diẹ sii ju rẹ lọ. Ni ọna yii o le yan ẹda kan, ati lati yan eyi ti o tẹle, o nilo lati tun gbogbo ilana naa ṣe laisi akiyesi ẹda ti o yan. Pẹlu iru algoridimu bẹ, idiju ti yiyan ẹda kan jẹ O (N), idiju ti yiyan awọn ẹda K jẹ O (N·K) ~ O (N2).
Idiju Quadrat jẹ buburu, ṣugbọn o le ni ilọsiwaju. Fun eyi a yoo kọ fun awọn akopọ ti awọn iwuwo. Abajade jẹ igi ijinle lg N, awọn ewe eyiti yoo ni awọn iwuwo ti awọn ẹda, ati awọn apa ti o ku yoo ni awọn akopọ apa kan, titi de apao gbogbo awọn iwuwo ni gbongbo igi naa. Nigbamii ti, a ṣe ina nọmba ID kan lati 0 si apapọ gbogbo awọn iwuwo, wa ẹda i-th, yọ kuro lati igi naa ki o tun ṣe ilana naa lati wa awọn ẹda ti o ku. Pẹlu iru algoridimu bẹ, idiju ti kikọ igi kan jẹ O (N), idiju wiwa i-th ajọra ati yiyọ kuro ninu igi jẹ O (lg N), idiju ti yiyan awọn ẹda K jẹ O (N +) K lg N) ~ O(N lg N) .
Idiju-logarithmic Linear dara ju idiju kuadiratiki, pataki fun K nla.
O jẹ algorithm yii ClusterClient ikawe lati ise agbese "" (Nibẹ ni a ṣe itumọ igi naa ni O (N lg N), ṣugbọn eyi ko ni ipa lori idiju ikẹhin ti algorithm.)
Isoro 2. Abila
O jẹ dandan lati daba algorithm kan fun yiyan awọn iwe aṣẹ daradara ni iranti nipasẹ aaye lainidii ti kii ṣe atọka:
Ẹgbẹ rẹ jẹ iṣẹ ṣiṣe lati ṣe agbekalẹ ibi ipamọ data ti iwe-ipamọ ti o pin ninu. Iṣeduro iṣẹ ti o wọpọ yoo jẹ lati yan awọn iwe aṣẹ N oke ti a lẹsẹsẹ nipasẹ aaye lainidii (ti kii ṣe atọka) aaye nọmba lati akojọpọ iwọn M (nigbagbogbo N <100 <<M). Iṣẹ ṣiṣe ti o kere diẹ ti o wọpọ yoo jẹ lati yan oke N lẹhin ti o fo awọn iwe aṣẹ S oke (S ~ N).
Ṣe imọran algorithm kan lati ṣiṣẹ iru awọn ibeere bẹ daradara. Ṣe iṣiro idiju iširo rẹ nipa lilo akiyesi O nla ninu ọran apapọ ati awọn oju iṣẹlẹ ọran ti o buruju.
Onínọmbà ti ojutu (fidio)
Bẹrẹ ni 34:50, iṣẹju 6 nikan:
Itupalẹ ti ojutu (ọrọ)
Solusan lori dada: too gbogbo awọn iwe aṣẹ (fun apẹẹrẹ, lilo ), lẹhinna mu awọn iwe aṣẹ N+S. Ni idi eyi, idiju ti lẹsẹsẹ ni apapọ jẹ O (M lg M), ni buruju - O (M2).
O han ni, tito gbogbo awọn iwe aṣẹ M ati lẹhinna mu apakan kekere kan ninu wọn jẹ ailagbara. Ni ibere ki o má ba to gbogbo awọn iwe aṣẹ, algorithm kan yoo ṣe , eyi ti yoo yan N + S awọn iwe aṣẹ ti a beere (wọn le ṣe lẹsẹsẹ nipasẹ eyikeyi algorithm). Ni idi eyi, idiju yoo dinku si O (M) ni apapọ, ati pe ọran ti o buru julọ yoo wa kanna.
Sibẹsibẹ, o le ṣe paapaa daradara siwaju sii - lo algorithm . Ni ọran yii, awọn iwe N + S akọkọ ni a ṣafikun si min- tabi okiti max (da lori itọsọna yiyan), ati lẹhinna iwe-ipamọ kọọkan ti o tẹle ni a fiwera pẹlu gbongbo igi naa, eyiti o ni iwọn ti o kere ju lọwọlọwọ tabi iwe ti o pọju. , ati, ti o ba wulo, ti wa ni afikun si awọn igi. Ni idi eyi, idiju ninu ọran ti o buru julọ, nigba ti o ni lati tun tun ṣe igi naa nigbagbogbo, jẹ O (M lg M), idiwọn ni apapọ ni O (M), bi nigba lilo kiakia.
Bibẹẹkọ, ṣiṣan okiti n jade lati ni imunadoko diẹ sii nitori otitọ pe ni iṣe pupọ julọ awọn iwe aṣẹ le jẹ asonu laisi atunko okiti naa, lẹhin lafiwe ẹyọkan pẹlu ipin root rẹ. A ṣe imuse yiyan yii ni ibi ipamọ data iwe iranti Zebra, ti dagbasoke ati lo ni Kontur.
Isoro 3. State swaps
O jẹ dandan lati daba algorithm ti o munadoko julọ fun awọn ipinlẹ iyipada:
Ẹgbẹ rẹ ni iṣẹ ṣiṣe lati ṣe agbekalẹ ẹrọ paṣipaarọ ipinlẹ ti o wuyi fun iṣupọ N ti pin kaakiri. Ipo i-th node yẹ ki o gbe lọ si (i+1) - th node, ipinlẹ N-th yẹ ki o gbe lọ si ipade akọkọ. Iṣiṣẹ atilẹyin nikan ni iyipada ipinlẹ nigbati awọn apa meji paarọ awọn ipinlẹ wọn ni atomiki. O ti wa ni mo wipe a ipinle siwopu gba M milliseconds. Gbogbo ipade ni anfani lati kopa ninu swap ipinlẹ kan ni eyikeyi akoko ti a fun.
Igba melo ni o gba lati gbe awọn ipinlẹ ti gbogbo awọn apa inu iṣupọ kan?
Itupalẹ ti ojutu (ọrọ)
Ojutu lori dada: paarọ awọn ipinlẹ ti akọkọ ati awọn eroja keji, lẹhinna akọkọ ati kẹta, lẹhinna akọkọ ati kẹrin, ati bẹbẹ lọ. Lẹhin paṣipaarọ kọọkan, ipo ti ẹya kan yoo wa ni ipo ti o fẹ. Iwọ yoo ni lati ṣe awọn permutations O (N) ati lo akoko O (N·M).
Akoko laini gun, nitorinaa o le ṣe paṣipaarọ awọn ipinlẹ ti awọn eroja ni awọn orisii: akọkọ pẹlu keji, ẹkẹta pẹlu kẹrin, ati bẹbẹ lọ. Lẹhin paṣipaarọ kọọkan ti ipinle, gbogbo nkan keji yoo wa ni ipo ti o fẹ. Iwọ yoo ni lati ṣe awọn permutations O (lg N) ati lo akoko O (M lg N).
Sibẹsibẹ, o le ṣe iyipada paapaa daradara siwaju sii - kii ṣe ni laini, ṣugbọn ni akoko igbagbogbo. Lati ṣe eyi, ni igbesẹ akọkọ o nilo lati paarọ ipo ti akọkọ ano pẹlu awọn ti o kẹhin, awọn keji pẹlu awọn penultimate, ati be be lo. Ipo ti nkan ti o kẹhin yoo wa ni ipo ti o fẹ. Ati ni bayi o nilo lati paarọ ipo ti ipin keji pẹlu eyi ti o kẹhin, ẹkẹta pẹlu ọkan penultimate, ati bẹbẹ lọ. Lẹhin iyipo iyipada yii, awọn ipinlẹ ti gbogbo awọn eroja yoo wa ni ipo ti o fẹ. Lapapọ, O(2M) ~ O(1) permutations yoo ṣee ṣe.
Iru ojutu yii kii yoo ṣe iyalẹnu fun mathimatiki kan rara, ti o tun ranti pe yiyi jẹ akopọ ti awọn ami-ami axial meji. Nipa ọna, o jẹ ohun ti o wọpọ lati yipada kii ṣe nipasẹ ọkan, ṣugbọn nipasẹ awọn ipo K <N. (Kọ sinu awọn asọye bawo ni pato.)
Ṣe o fẹran awọn isiro naa? Ṣe o mọ awọn ojutu miiran? Pin ninu awọn asọye.
Eyi ni diẹ ninu awọn ọna asopọ iwulo ikẹhin:
- wa diẹ sii nipa ni Kontur
- wo awọn igbasilẹ inu nipa pin awọn ọna šiše
- wo jara ti awọn ikowe fidio "»
- alabapin si wa
orisun: www.habr.com