I tupu i etahi ra ki muri . Ko nga taangata mai i te Rōpū JUG.ru i tono i nga kaikorero moemoea (Leslie Lamport! Cliff Click! Martin Kleppmann!) me te whakapau i nga ra e rua ki nga punaha tohatoha me te rorohiko. Ko Kontur tetahi o nga hoa tokotoru o te hui. I korero matou i te tihokahoka, i korero mo o matou putunga putunga, purei bingo, me te whakaoti panga.
He panui tenei me te wetewete i nga mahi i te tuunga o Kontur mai i te kaituhi o a raatau tuhinga. Ko wai i runga i te Hydra - koinei to take ki te mahara ki te wheako pai, ko wai kaore - he waahi ki te toro i to roro nui O-tohu.
Arā anō ngā kaiuru i wetewete i te tūtohi huri hei kiriata hei tuhi i tā rātou whakatau. Kare au i te katakata - i tukuna e ratou tenei puranga pepa hei manatoko:
E toru nga mahi katoa:
- e pa ana ki te kowhiri i nga tauira ma nga taumahatanga mo te whakataurite kawenga
- mō te kōmaka hua uiui ki tētahi pātengi raraunga pūmahara
- i runga i te whakawhitinga kawanatanga i roto i te punaha tohatoha me te topology mowhiti
Tūmahi 1. ClusterClient
I tika te whakatakoto i tetahi algorithm mo te kowhiringa pai o K mai i nga tauira taumaha N o te punaha toha:
Ko to roopu te mahi ki te whakawhanake i te whare pukapuka kiritaki mo te roopu toha nui o N node. Ka aroturukihia e te whare pukapuka nga momo metadata e pa ana ki nga pona (hei tauira, o ratou toronga, 4xx/5xx reiti whakautu, me etahi atu) me te tautapa i nga taumahatanga ira W1..WN ki a ratou. Hei tautoko i te rautaki mahi i te wa kotahi, ka taea e te whare pukapuka te kowhiri matapōkeretia K o N node—ko te tupono ki te kowhiri me orite ki te taumaha o te node.
Whakatakotoria he hātepee hei whiriwhiri pai i nga pona. Whakatau tatahia tona uauatanga rorohiko ma te whakamahi tohu O nui.
He aha nga mea katoa i te reo Ingarihi?
No te mea i roto i tenei ahua i whawhai nga kaiuru o te hui ki a ratou me te mea ko te reo Ingarihi te reo mana o Hydra. He penei te ahua o nga mahi:
Tangohia te pepa me te pene, whakaaro, kaua e tere ki te whakatuwhera i nga kaipahua inaianei 🙂
Te tātaritanga o te otinga (ataata)
Ka timata i te 5:53, 4 meneti anake:
A koinei te huarahi i whakatakotohia ai e nga taane me te maataki papamuri ta ratou otinga:
Tātaritanga o te otinga (kuputuhi)
Ko te otinga e whai ake nei kei runga i te mata: whakahiatohia nga pauna o nga tauira katoa, hangaia he tau matapōkere mai i te 0 ki te tapeke o nga taumahatanga katoa, katahi ka kowhiria he tauira-i kia penei ai te tapeke o nga taumahatanga tauira mai i te 0 ki te (i-1)th he iti ake i te tau matapōkere, ā, ko te tapeke o ngā taumahatanga tauira mai i te 0 ki te i-th - he nui ake i tērā. Na ka taea te kowhiri i tetahi tauira, me te kowhiri i te mea e whai ake nei, me whakahoki ano e koe nga tikanga katoa me te kore e whakaaro ki te tauira kua tohua. Ma tenei momo algorithm, ko te uaua o te whiriwhiri i tetahi tauira ko O(N), ko te uaua o te whiriwhiri i nga tauira K ko O(N K) ~ O(N2).
He kino te matatini tapawha, engari ka taea te whakapai ake. Ki te mahi i tenei, ka hanga e matou mo nga moni pauna. Ka whiwhia he rakau hohonu lg N, kei roto i nga rau he tauira taumahatanga, kei roto i nga pona e toe ana - he wahanga wahanga, tae noa ki te tapeke o nga taumahatanga katoa i te putake o te rakau. Whai muri, ka whakaputahia he tau matapōkere mai i te 0 ki te tapeke o nga taumahatanga katoa, ka kimihia te tauira i-th, ka tangohia mai i te rakau, ka tuaruatia ano te tikanga kia kitea nga tauira e toe ana. Ma tenei algorithm, ko te uaua o te hanga rakau ko O(N), ko te uaua o te kimi i te tauira i-th me te tango mai i te rakau ko O(lg N), ko te uaua o te whiriwhiri i nga tauira K ko O(N + K lg N) ~ O(N lg N) .
He pai ake te uaua o te raarangi-raupapa i te matatini tapawha, ina koa mo te K nui.
Ko tenei algorithm Ko nga whare pukapuka ClusterClient mai i te kaupapa "". (I reira, ka hangaia te rakau ki O(N lg N), engari kaore tenei e pa ki te uaua whakamutunga o te algorithm.)
Tūmahi 2. Hepara
He mea tika ki te whakatakoto i tetahi algorithm mo te whakariterite pai i nga tuhinga i roto i te mahara ma te waahi kore-taupurangi:
Ko to roopu te mahi ki te hanga i tetahi putunga putunga tuhinga mahara-marama. Ko te kawenga mahi noa ko te kowhiri i nga tuhinga N o runga kua tohua ma te apure tau (kaore i tohua) mai i te kohinga rahi M (ko te tikanga N <100 << M). He iti ake te taumaha o te mahi ko te kowhiri i runga N i muri i te peke i nga tuhinga S o runga (S ~ N).
Whakatakotoria he algorithm hei whakahaere pai i aua patai. Whakatau tatahia tona uauatanga rorohiko ma te whakamahi tohu O nui i roto i te keehi toharite me nga ahuatanga kino rawa atu.
Te tātaritanga o te otinga (ataata)
Ka timata i te 34:50, 6 meneti anake:
Tātaritanga o te otinga (kuputuhi)
Te otinga mata: tohua nga tuhinga katoa (hei tauira me te ), ka tango tuhinga N+S. I tenei ahuatanga, ko te uaua o te tohatoha kei te toharite O(M lg M), i te kino rawa atu O(M2).
Ka kitea ko te whakariterite i nga tuhinga M katoa me te tango i tetahi waahanga iti noa iho kaore e pai. Kia kore ai e tohatoha nga tuhinga katoa, he pai te algorithm , ka tohua te N + S o nga tuhinga e hiahiatia ana (ka taea te whakariterite ma tetahi algorithm). I tenei keehi, ka heke te uaua ki te O(M) i te toharite, ka noho tonu te keehi kino rawa atu.
Heoi, ka taea e koe te mahi pai ake - whakamahia te algorithm . I tenei keehi, ko nga tuhinga N+S tuatahi ka taapirihia ki te min-, max-heap ranei (i runga i te ahunga o te ahua), ka whakatauritea ia tuhinga e whai ake nei ki te putake o te rakau, kei roto te tuhinga iti rawa atu, morahi ranei. ka tapiritia ki te rakau mehemea e tika ana. I roto i tenei take, ko te uauatanga i roto i te keehi kino rawa atu, ina me hanga tonu e koe te rakau, ko O(M lg M), ko te matatini o te toharite ko O(M), pera me te kowhiri tere.
Heoi ano, he pai ake te rere o te puranga na te mea ko te nuinga o nga tuhinga ka taea te whakakore me te kore e hanga ano i te puranga i muri i te whakatauritenga kotahi me tona huanga pakiaka. Ka whakatinanahia taua momo tohatoha i roto i te putunga tuhinga tuhinga mahara-a Zebra i whakawhanakehia, ka whakamahia ki Kontur.
Tūmahi 3. Whakawhiti whenua
He mea tika ki te whakatakoto i te algorithm tino pai mo te neke whenua:
Ko to roopu te mahi ki te whakawhanake i tetahi tikanga whakawhiti ahua ataahua mo te kahui tohatoha N node. Me whakawhiti te ahua o te node i-th ki te (i+1)-th node, me whakawhiti te ahua o te node N-th ki te node tuatahi. Ko te mahi e tautokohia ana ko te whakawhiti whenua ina whakawhiti nga pona e rua i o raatau whenua ngota. E mohiotia ana ka pau te M nga mirihakona ma te whakawhiti whenua. Ka taea e ia node te uru ki roto i te whakawhiti whenua kotahi i tetahi wa.
Kia pehea te roa o te whakawhiti i nga ahuatanga o nga pona katoa i roto i te tautau?
Tātaritanga o te otinga (kuputuhi)
Te otinga mata: whakawhitihia nga ahuatanga o te huānga tuatahi me te tuarua, katahi te tuatahi me te tuatoru, katahi te tuatahi me te tuawha, me era atu. I muri i ia whakawhitinga, ka noho te ahua o tetahi huānga ki te waahi e hiahiatia ana. Me hanga O(N) whakaaetanga ka whakapau i te waa O(N M).
He roa te wa raina, no reira ka taea e koe te whakawhiti takirua i nga ahuatanga o nga huānga: te tuatahi me te tuarua, te tuatoru me te tuawha, me era atu. I muri i ia whakawhitinga kawanatanga, ka noho nga waahanga tuarua ki te waahi tika. Me hanga e koe nga whakarereketanga O(lg N) me te whakapau i te waa O(M lg N).
Heoi ano, ka taea te neke ake i te pai ake - kaua i roto i te raina, engari i te waa tonu. Ki te mahi i tenei, i te taahiraa tuatahi, me whakawhiti koe i te ahua o te huānga tuatahi me te whakamutunga, te tuarua me te penultimate, me etahi atu. Ko te ahua o te huānga whakamutunga ka noho tika. Na inaianei me whakawhiti tatou i te ahua o te waahanga tuarua me te whakamutunga, te tuatoru me te penultimate, me era atu. Whai muri i tenei huringa o nga whakawhitinga, ka noho tika nga ahuatanga o nga waahanga katoa. Ka puta nga whakarereketanga O(2M) ~ O(1) katoa.
Ko taua otinga e kore rawa e miharo i te tohunga pangarau e maumahara tonu ana ko te hurihanga he hanganga o nga hangarite axial e rua. Ma te ara, he mea whaanui noa mo te nekehanga ehara ma te kotahi, engari ma nga tuunga K <N. (Tuhia ki nga korero me pehea te tika.)
I pai koe ki nga panga? Kei te mohio koe ki etahi atu otinga? A faaite i roto i nga korero.
Anei etahi hononga whai hua i te mutunga:
- ako atu mo i roto i te porohita
- tirohia nga rekoata o roto mo nga punaha tohatoha
- tirohia te raupapa o nga korero korero ataata»
- ohauru ki to maatau
Source: will.com