Чанд рӯз пеш рӯй дод . Бачаҳо аз гурӯҳи JUG.ru сухангӯёни орзуҳоро даъват карданд (Лесли Лампорт! Клифф Клик! Мартин Клепман!) ва ду рӯзро ба системаҳои тақсимшуда ва ҳисоббарорӣ бахшиданд. Контур яке аз се шарики конфронс буд. Мо дар стенд сӯҳбат кардем, дар бораи нигаҳдории тақсимшудаи худ сӯҳбат кардем, бинго бозӣ кардем ва муаммоҳоро ҳал кардем.
Ин мақола бо таҳлили вазифаҳо дар стенди Контур аз муаллифи матни онҳост. Кӣ дар Гидра буд - ин сабаби шумо барои ба ёд овардани таҷрибаи гуворо аст, ва кӣ набуд - имкони дароз кардани майнаи шумо калон О.- қайд.
Ҳатто иштирокчиёне буданд, ки флипчартро ба слайдҳо тақсим карда, қарори худро навиштанд. Ман шӯхӣ намекунам - онҳо ин коғазро барои тафтиш доданд:
Дар маҷмӯъ се вазифа вуҷуд дошт:
- дар бораи интихоби репликаҳо аз рӯи вазнҳо барои мувозинати сарборӣ
- дар бораи мураттаб кардани натиҷаҳои дархост дар заминаи пойгоҳи додаҳои хотира
- оид ба интиқоли давлатӣ дар системаи тақсимшуда бо топологияи ҳалқа
Вазифаи 1. ClusterClient
Лозим буд, ки алгоритми интихоби самараноки К аз N нусхаи вазншудаи системаи тақсимшуда пешниҳод карда шавад:
Дастаи шумо вазифадор аст, ки китобхонаи мизоҷро барои кластери ба таври васеъ паҳншудаи N гиреҳ таҳия кунад. Китобхона метамаълумоти мухталифи марбут ба гиреҳҳоро пайгирӣ мекунад (масалан, таъхирҳои онҳо, суръати посухи 4xx/5xx ва ғ.) ва ба онҳо вазнҳои нуқтаи шинокунандаи W1..WN таъин мекунад. Барои дастгирии стратегияи иҷроиши ҳамзамон, китобхона бояд K аз N гиреҳро ба таври тасодуфӣ интихоб кунад - имконияти интихоб бояд ба вазни гиреҳ мутаносиб бошад.
Барои самаранок интихоб кардани гиреҳҳо алгоритм пешниҳод кунед. Мушкилии ҳисобкунии онро бо истифода аз аломати бузурги O ҳисоб кунед.
Чаро ҳама чиз бо забони англисӣ аст?
Зеро дар ин шакл иштирокдорони конфронс бо онҳо меҷангиданд ва забони англисӣ забони расмии Ҳидра буд. Вазифаҳо чунин менамуданд:
Коғазу қалам гиред, фикр кунед, дарҳол ба кушодани спойлерҳо шитоб накунед 🙂
Таҳлили ҳалли (видео)
Оғоз аз 5:53, ҳамагӣ 4 дақиқа:
Ва ин аст, ки чӣ тавр бачаҳои флипчарт ҳалли худро пешниҳод карданд:
Таҳлили ҳалли (матн)
Ҳалли зерин дар рӯи замин ҷойгир аст: ҷамъи вазнҳои ҳамаи репликаҳоро ҷамъ кунед, рақами тасодуфиро аз 0 то ҷамъи ҳамаи вазнҳо тавлид кунед ва сипас i-репликаро интихоб кунед, ки маблағи вазнҳои реплика аз 0 то (i-1)-ум бошад. камтар аз як адади тасодуфӣ аст, ва ҷамъи вазнҳои реплика аз 0 то 2-ум - зиёдтар аз он. Ҳамин тавр, имкон пайдо мешавад, ки як репликаро интихоб кунед ва барои интихоби дигар, шумо бояд тамоми расмро бидуни назардошти нусхаи интихобшуда такрор кунед. Бо чунин алгоритм мураккабии интихоби як реплика O(N), мураккабии интихоби К реплика O(N K) ~ O(NXNUMX) мебошад.
Мушкилии квадратӣ бад аст, аммо онро беҳтар кардан мумкин аст. Барои ин мо месозем барои маблағи вазнҳо. Дарахти умқи lg N ба даст оварда мешавад, ки дар баргҳои он вазнҳои такрорӣ ва дар гиреҳҳои боқимонда - қисман, то ҷамъи тамоми вазнҳои решаи дарахт пайдо мешаванд. Минбаъд, мо як адади тасодуфиро аз 0 то ҷамъи ҳамаи вазнҳо тавлид мекунем, репликаи i-умро пайдо мекунем, онро аз дарахт хориҷ мекунем ва тартиби пайдо кардани репликаҳои боқимондаро такрор мекунем. Бо ин алгоритм мураккабии сохтани дарахт O(N), мураккабии дарёфти нусхаи i-ум ва хориҷ кардани он аз дарахт O(lg N), мураккабии интихоби К репликаҳо O(N+K) аст. lg N) ~ O(N lg N) .
Мушкилии хатти-логӣ назар ба мураккабии квадратӣ беҳтар аст, махсусан барои К.
Ин алгоритм аст Китобхонаҳои ClusterClient аз лоиҳаи "". (Дар он ҷо, дарахт дар O(N lg N) сохта шудааст, аммо ин ба мураккабии ниҳоии алгоритм таъсир намерасонад.)
Вазифаи 2. Зебра
Лозим буд, ки алгоритми ба таври муассир ҷудо кардани ҳуҷҷатҳо дар хотира аз рӯи майдони индекснашавандаи худсарона пешниҳод карда шавад:
Дастаи шумо вазифадор аст, ки як пойгоҳи додаҳои ҳуҷҷатҳои хотираи муштаракро таҳия кунад. Сарбории маъмулӣ ин интихоби N ҳуҷҷати болоии аз рӯи майдони рақамии худсарона (индексиянашуда) аз маҷмӯаи андозаи M (одатан N < 100 << M) мураттабшуда мебошад. Сарбории кори каме камтар маъмул ин интихоби N боло пас аз гузаштани ҳуҷҷатҳои S боло (S ~ N) хоҳад буд.
Барои самаранок иҷро кардани чунин дархостҳо алгоритмеро пешниҳод кунед. Мушкилии ҳисобкунии онро бо истифода аз аломати бузурги O дар ҳолати миёна ва бадтарин сенарияҳо ҳисоб кунед.
Таҳлили ҳалли (видео)
Оғоз соати 34:50, ҳамагӣ 6 дақиқа:
Таҳлили ҳалли (матн)
Ҳалли рӯизаминӣ: ҳама ҳуҷҷатҳоро ҷудо кунед (масалан бо ), пас ҳуҷҷатҳои N+S гиред. Дар ин маврид мураккабии људокунї ба њисоби миёна О(M lg M), дар бадтаринаш О(М2) аст.
Маълум аст, ки ба тартиб андохтани хамаи М хуччатхо ва баъд гирифтани як кисми ками онхо бесамар аст. Барои он ки ҳама ҳуҷҷатҳоро ҷудо накунед, алгоритм мувофиқ аст , ки N + S -и ҳуҷҷатҳои дилхоҳро интихоб мекунад (онҳоро аз рӯи ҳама алгоритм мураттаб кардан мумкин аст). Дар ин ҳолат, мураккабӣ ба ҳисоби миёна ба O(M) кам мешавад, дар ҳоле ки бадтарин ҳолат бетағйир мемонад.
Бо вуҷуди ин, шумо метавонед онро боз ҳам самараноктар иҷро кунед - алгоритмро истифода баред . Дар ин ҳолат, ҳуҷҷатҳои аввалини N+S ба min- ё max-heap (вобаста ба самти навъ) илова карда мешаванд ва сипас ҳар як ҳуҷҷати навбатӣ бо решаи дарахт муқоиса карда мешавад, ки ҳуҷҷати ҳадди ақал ё ҳадди аксарро дар бар мегирад, ва агар лозим бошад, ба дарахт илова карда мешавад. . Дар ин ҳолат, мураккабӣ дар ҳолати бадтарин, вақте ки шумо бояд пайваста дарахтро аз нав созед, O(M lg M) аст, мураккабӣ ба ҳисоби миёна O(M), мисли интихоби quickselect.
Бо вуҷуди ин, ҷараёни теппа самараноктар мешавад, зеро дар амал аксари ҳуҷҷатҳоро бе барқарор кардани тӯда пас аз як муқоиса бо унсури решаи он партофтан мумкин аст. Чунин навъбандӣ дар базаи ҳуҷҷати дар хотираи Zebra дар Контур таҳия ва истифода мешавад.
Вазифаи 3. Свопҳои давлатӣ
Лозим буд, ки алгоритми аз ҳама самарабахши тағир додани ҳолатҳо пешниҳод карда шавад:
Дастаи шумо вазифадор аст, ки механизми табодули давлатиро барои кластери тақсимшудаи N гиреҳ таҳия кунад. Ҳолати гиреҳи i-ум бояд ба гиреҳи (i+1)-ум, ҳолати гиреҳи N-ум ба гиреҳи аввал интиқол дода шавад. Ягона амалиёти дастгиришаванда ин ивази ҳолат аст, вақте ки ду гиреҳ ҳолати худро ба таври атомӣ иваз мекунанд. Маълум аст, ки своп ҳолати M миллисонияро мегирад. Ҳар як гиреҳ метавонад дар як своп ҳолати ягона дар ҳар лаҳза иштирок кунад.
Интиқоли ҳолати ҳама гиреҳҳо дар кластер чанд вақт мегирад?
Таҳлили ҳалли (матн)
Ҳалли рӯизаминӣ: иваз кардани ҳолати элементҳои якум ва дуюм, баъд якум ва сеюм, баъд якум ва чорум ва ғайра. Пас аз ҳар мубодила, ҳолати як элемент дар ҳолати дилхоҳ хоҳад буд. Шумо бояд тағиротҳои O(N) кунед ва вақти O(NM)-ро сарф кунед.
Вақти хатӣ дароз аст, бинобар ин шумо метавонед ҳолати элементҳоро ҷуфт-ҷуфт иваз кунед: якум бо дуюм, сеюм бо чорум ва ғайра. Пас аз ҳар як мубодилаи давлатӣ, ҳар як унсури дуюм дар мавқеи дуруст хоҳад буд. Шумо бояд ивазкунии O(lg N) кунед ва вақти O(M lg N)-ро сарф кунед.
Вале сменаро боз хам самарабахштар — на дар хат, балки дар вакти доимй кардан мумкин аст. Барои ин, дар қадами аввал ба шумо лозим аст, ки ҳолати элементи якумро бо элементи охирин, дуюмро бо элементи охирин ва ғайра иваз кунед. Ҳолати элементи охирин дар ҳолати дуруст хоҳад буд. Ва ҳоло ба мо лозим аст, ки ҳолати элементи дуюмро бо элементи охирин, сеюмро бо элементи пеш аз охирин ва ғайра иваз кунем. Пас аз ин даври мубодила, давлатҳои ҳама унсурҳо дар мавқеи дуруст хоҳанд буд. Дар маҷмӯъ тағиротҳои O(2M) ~ O(1) хоҳанд буд.
Чунин ҳалл математикеро, ки то ҳол дар хотир дорад, ки гардиш таркиб аз ду симметрияи меҳвар аст, ба ҳайрат намеорад. Зимнан, он барои смена на аз руи як, балки аз руи мавкеъхои К<N ба таври ночиз умум карда мешавад. (Дар шарҳҳо нависед, ки чӣ тавр дақиқ.)
Оё шумо муаммоҳоро дӯст медоштед? Оё шумо роҳҳои ҳалли дигарро медонед? Дар шарҳҳо мубодила кунед.
Ва инҳоянд чанд истинодҳои муфид дар охир:
- бештар маълумот гиред дар контур
- ба сабтҳои дохилӣ нигаред дар бораи системаҳои тақсимшуда
- силсилаи видеолексияҳоро тамошо кунед»
- ба мо обуна шавед
Манбаъ: will.com