Ilifanyika siku chache zilizopita Mkutano wa Hydra. Vijana kutoka Kundi la JUG.ru walialika wasemaji wa ndoto (Leslie Lamport! Cliff Click! Martin Kleppmann!) Na kujitolea siku mbili kwa mifumo iliyosambazwa na kompyuta. Kontur alikuwa mmoja wa washirika watatu wa mkutano huo. Tulizungumza kwenye kibanda, tukazungumza kuhusu hifadhi yetu iliyosambazwa, tukacheza bingo, na kutatua mafumbo.

Hili ni chapisho lenye uchanganuzi wa kazi katika stendi ya Kontur kutoka kwa mwandishi wa maandishi yao. Nani alikuwa kwenye Hydra - hii ndio sababu yako ya kukumbuka uzoefu wa kupendeza, ambaye hakuwa - nafasi ya kunyoosha ubongo wako. kubwa O-alama.

Kulikuwa na hata washiriki ambao walitenganisha chati mgeuzo katika slaidi ili kuandika uamuzi wao. Sifanyi mzaha - walikabidhi rundo hili la karatasi kwa uthibitisho:

Kulikuwa na kazi tatu kwa jumla:

• kuhusu kuchagua nakala kwa uzani kwa kusawazisha mzigo
• kuhusu kupanga matokeo ya hoja dhidi ya hifadhidata ya kumbukumbu
• juu ya uhamisho wa serikali katika mfumo uliosambazwa na topolojia ya pete

Kazi ya 1. ClusterClient

Ilihitajika kupendekeza algorithm ya uteuzi mzuri wa K kutoka nakala za uzani wa N za mfumo uliosambazwa:

Timu yako ina jukumu la kuunda maktaba ya mteja kwa kikundi kilichosambazwa sana cha nodi za N. Maktaba inaweza kufuatilia metadata mbalimbali zinazohusiana na nodi (kwa mfano, muda wao wa kusubiri, viwango vya majibu 4xx/5xx, n.k.) na kuzipa uzito wa pointi zinazoelea W1..WN. Ili kusaidia mkakati wa utekelezaji kwa wakati mmoja, maktaba inapaswa kuwa na uwezo wa kuchagua nodi K kati ya N nasibu—nafasi ya kuchaguliwa inapaswa kuwa sawia na uzito wa nodi.

Pendekeza algorithm ili kuchagua nodi kwa ufanisi. Kadiria uchangamano wake wa kukokotoa kwa kutumia nukuu kubwa ya O.

Kwa nini kila kitu kiko kwa Kiingereza?

Kwa sababu katika fomu hii washiriki wa mkutano walipigana nao na kwa sababu Kiingereza kilikuwa lugha rasmi ya Hydra. Kazi zilionekana kama hii:

Chukua karatasi na penseli, fikiria, usikimbilie kufungua waharibifu mara moja 🙂

Uchambuzi wa suluhisho (video)

Kuanzia saa 5:53, dakika 4 pekee:

Na hivi ndivyo vijana walio na chati mgeuzo walivyotoa suluhisho lao:

Uchambuzi wa suluhisho (maandishi)

Suluhisho lifuatalo liko juu ya uso: jumla ya uzani wa nakala zote, toa nambari nasibu kutoka 0 hadi jumla ya uzani wote, kisha uchague i-replica ili jumla ya uzani wa nakala kutoka 0 hadi (i-1) th. ni chini ya nambari isiyo ya kawaida, na jumla ya uzani wa replica kutoka 0 hadi i-th - zaidi yake. Kwa hivyo itawezekana kuchagua replica moja, na kuchagua inayofuata, unahitaji kurudia utaratibu mzima bila kuzingatia replica iliyochaguliwa. Na algorithm kama hiyo, ugumu wa kuchagua nakala moja ni O(N), ugumu wa kuchagua nakala za K ni O(N K) ~ O(N2).

Ugumu wa Quadratic ni mbaya, lakini unaweza kuboreshwa. Ili kufanya hivyo, tutajenga mti wa sehemu kwa hesabu za uzito. Mti wa kina lg N utapatikana, katika majani ambayo kutakuwa na uzani wa replica, na katika nodi zilizobaki - hesabu za sehemu, hadi jumla ya uzani wote kwenye mzizi wa mti. Ifuatayo, tunatoa nambari isiyo ya kawaida kutoka 0 hadi jumla ya uzani wote, pata nakala ya i-th, tuondoe kwenye mti, na kurudia utaratibu wa kupata nakala zilizobaki. Na algorithm hii, ugumu wa kujenga mti ni O(N), ugumu wa kupata nakala ya i-th na kuiondoa kwenye mti ni O(lg N), ugumu wa kuchagua nakala za K ni O(N + K). lg N) ~ O(N lg N) .

Utata wa logi ya mstari ni mzuri zaidi kuliko uchangamano wa quadratic, hasa kwa K kubwa.

Ni algorithm hii kutekelezwa kwa kanuni Maktaba za ClusterClient kutoka kwa mradi "Mashariki". (Hapo, mti umejengwa katika O (N lg N), lakini hii haiathiri ugumu wa mwisho wa algorithm.)

Kazi ya 2. Zebra

Ilihitajika kupendekeza algorithm ya upangaji mzuri wa hati kwenye kumbukumbu kwa uga wa kiholela ambao haujaorodheshwa:

Timu yako ina jukumu la kuunda hifadhidata ya hati iliyoshirikiwa ya kumbukumbu. Mzigo wa kazi wa kawaida utakuwa kuchagua hati za juu za N zilizopangwa kwa uga wa nambari kiholela (usio na fahirisi) kutoka kwa mkusanyiko wa ukubwa M (kawaida N <100 << M). Mzigo mdogo wa kazi wa kawaida utakuwa kuchagua N ya juu baada ya kuruka hati za juu za S (S ~ N).

Pendekeza algorithm ya kutekeleza maswali kama haya kwa ufanisi. Kadiria uchangamano wake wa kimahesabu kwa kutumia nukuu kubwa ya O katika kisa cha wastani na hali mbaya zaidi.

Uchambuzi wa suluhisho (video)

Kuanzia 34:50, dakika 6 pekee:

Uchambuzi wa suluhisho (maandishi)

Suluhisho la uso: panga hati zote (kwa mfano na haraka), kisha chukua hati za N+S. Katika kesi hii, ugumu wa kupanga ni wastani wa O(M lg M), mbaya zaidi O(M2).

Ni dhahiri kwamba kupanga hati zote za M na kisha kuchukua sehemu ndogo tu haifai. Ili sio kupanga hati zote, algorithm inafaa haraka kuchagua, ambayo itachagua N + S ya hati zinazohitajika (zinaweza kupangwa kwa algorithm yoyote). Katika kesi hii, ugumu utapungua hadi O (M) kwa wastani, wakati hali mbaya zaidi itabaki sawa.

Walakini, unaweza kuifanya kwa ufanisi zaidi - tumia algorithm utiririshaji wa lundo la binary. Katika kesi hii, nyaraka za kwanza za N + S zinaongezwa kwa min- au max-lundo (kulingana na mwelekeo wa aina), na kisha kila hati inayofuata inalinganishwa na mzizi wa mti, ambayo ina hati ya chini au ya juu ya sasa, na huongezwa kwenye mti ikiwa ni lazima. . Katika kesi hii, ugumu katika hali mbaya zaidi, wakati lazima ujenge tena mti kila wakati, ni O (M lg M), ugumu wa wastani ni O (M), kama ilivyo kwa uchaguzi wa haraka.

Walakini, utiririshaji wa lundo unageuka kuwa mzuri zaidi kwa sababu ya ukweli kwamba katika mazoezi hati nyingi zinaweza kutupwa bila kujenga tena lundo baada ya kulinganisha moja na kipengele chake cha mizizi. Upangaji kama huo unatekelezwa katika hifadhidata ya hati ya kumbukumbu ya Zebra iliyotengenezwa na kutumika katika Kontur.

Kazi ya 3. Mabadiliko ya serikali

Ilihitajika kupendekeza algorithm inayofaa zaidi ya kuhama majimbo:

Timu yako ina jukumu la kuunda utaratibu mzuri wa kubadilishana hali kwa kundi lililosambazwa la nodi N. Hali ya nodi ya i-th inapaswa kuhamishiwa kwenye nodi ya (i+1)-th, hali ya nodi ya N-th inapaswa kuhamishiwa kwenye nodi ya kwanza. Uendeshaji pekee unaoungwa mkono ni ubadilishanaji wa serikali wakati nodi mbili zinabadilisha majimbo yao kwa atomi. Inajulikana kuwa ubadilishanaji wa serikali huchukua M milliseconds. Kila nodi inaweza kushiriki katika kubadilishana hali moja wakati wowote.

Inachukua muda gani kuhamisha majimbo ya nodi zote kwenye nguzo?

Uchambuzi wa suluhisho (maandishi)

Suluhisho la uso: kubadilishana majimbo ya kipengele cha kwanza na cha pili, kisha cha kwanza na cha tatu, kisha cha kwanza na cha nne, na kadhalika. Baada ya kila kubadilishana, hali ya kipengele kimoja itakuwa katika nafasi inayotakiwa. Lazima ufanye vibali vya O(N) na utumie muda wa O(N M).

Muda wa mstari ni mrefu, hivyo unaweza kubadilishana hali ya vipengele katika jozi: ya kwanza na ya pili, ya tatu na ya nne, na kadhalika. Baada ya kila kubadilishana hali, kila kipengele cha pili kitakuwa katika nafasi sahihi. Lazima ufanye vibali vya O(lg N) na utumie muda wa O(M lg N).

Hata hivyo, inawezekana kufanya mabadiliko hata ufanisi zaidi - si kwa mstari, lakini kwa wakati wa mara kwa mara. Ili kufanya hivyo, katika hatua ya kwanza, unahitaji kubadilisha hali ya kipengele cha kwanza na cha mwisho, cha pili na cha mwisho, na kadhalika. Hali ya kipengele cha mwisho itakuwa katika nafasi sahihi. Na sasa tunahitaji kubadilishana hali ya kipengele cha pili na cha mwisho, cha tatu na cha mwisho, na kadhalika. Baada ya mzunguko huu wa kubadilishana, majimbo ya vipengele vyote yatakuwa katika nafasi sahihi. Kutakuwa na vibali vya O(2M) ~ O(1) kwa jumla.

Suluhisho kama hilo halitamshangaza mwanahisabati ambaye bado anakumbuka kuwa mzunguko ni muundo wa ulinganifu wa axial mbili. Kwa njia, inafanywa kwa ujumla kwa mabadiliko sio moja, lakini kwa nafasi za K <N. (Andika katika maoni jinsi gani hasa.)

Ulipenda mafumbo? Je! unajua masuluhisho mengine? Shiriki katika maoni.

Na hapa kuna viungo muhimu mwishoni:

• kujifunza zaidi kuhusu maendeleo ya miundombinu katika contour
• tazama kumbukumbu za ndani kipeperushi kilicho na ripoti kuhusu mifumo iliyosambazwa
• tazama mfululizo wa mihadhara ya videoAlgorithms isiyo ya kawaida kwa watu wa kawaida»
• jiandikishe kwa yetu kituo katika Telegram

Chanzo: mapenzi.com