Бірнеше күн бұрын болған оқиға Гидра конференциясы. JUG.ru тобының жігіттері арман спикерлерін (Лесли Лэмпорт! Клифф Клик! Мартин Клепманн!) шақырып, екі күнді бөлінген жүйелер мен есептеулерге арнады. Контур конференцияның үш серіктесінің бірі болды. Біз стендте сөйлестік, таратылған қоймамыз туралы сөйлестік, бинго ойнадық және жұмбақтарды шештік.

Бұл мәтін авторының Контур стендіндегі тапсырмаларды талдауы бар пост. Гидрада кім болды - бұл сіздің жағымды тәжірибеңізді еске түсіруге себеп болды, ал кім болмады - миыңызды кеңейту мүмкіндігі үлкен О-белгілеу.

Тіпті өз шешімін жазу үшін флипчартты слайдтарға бөлшектеген қатысушылар да болды. Мен қалжыңдамаймын - олар бұл қағаз бумасын тексеру үшін берді:

Барлығы үш тапсырма болды:

• жүктемені теңестіру үшін салмақ бойынша көшірмелерді таңдау туралы
• жадтағы дерекқорға қарсы сұрау нәтижелерін сұрыптау туралы
• сақиналы топологиясы бар үлестірілген жүйеде күйді беру туралы

1-тапсырма. ClusterClient

Бөлінген жүйенің N өлшенген репликасынан K тиімді таңдау алгоритмін ұсыну қажет болды:

Сіздің командаңызға N түйіндерінің жаппай таратылған кластері үшін клиенттік кітапхананы әзірлеу тапсырылған. Кітапхана түйіндермен байланысты әртүрлі метадеректерді (мысалы, олардың кідірістері, 4xx/5xx жауап беру жылдамдығы және т.б.) қадағалап отырады және оларға W1..WN өзгермелі нүкте салмақтарын тағайындайды. Бір мезгілде орындау стратегиясын қолдау үшін кітапхана N түйіндердің K-ін кездейсоқ таңдай алуы керек — таңдалу мүмкіндігі түйіннің салмағына пропорционалды болуы керек.

Түйіндерді тиімді таңдау үшін алгоритмді ұсыныңыз. Үлкен O белгісін пайдаланып оның есептеу күрделілігін бағалаңыз.

Неліктен бәрі ағылшын тілінде?

Өйткені бұл формада конференцияға қатысушылар олармен күресті және ағылшын тілі Гидраның ресми тілі болғандықтан. Тапсырмалар келесідей болды:

Қағаз бен қарындаш алыңыз, ойланыңыз, спойлерлерді бірден ашуға асықпаңыз 🙂

Шешімді талдау (бейне)

5:53-тен бастап, небәрі 4 минут:

Міне, флипчарт бар жігіттер өз шешімін осылай көрсетті:

Шешімді талдау (мәтін)

Бетінде келесі шешім жатыр: барлық көшірмелердің салмақтарын қосыңыз, 0-ден барлық салмақтардың қосындысына кездейсоқ санды жасаңыз, содан кейін 0-ден (i-1)-ге дейінгі реплика салмақтарының қосындысы болатындай i-репликаны таңдаңыз. кездейсоқ саннан аз, ал 0-ден i-ге дейінгі реплика салмағының қосындысы - одан көп. Осылайша, бір репликаны таңдауға болады, ал келесісін таңдау үшін таңдалған репликаны ескерместен бүкіл процедураны қайталау керек. Мұндай алгоритммен бір репликаны таңдаудың күрделілігі O(N), К репликаларды таңдаудың күрделілігі O(N K) ~ O(N2).

Квадраттық күрделілік нашар, бірақ оны жақсартуға болады. Ол үшін біз саламыз сегмент ағашы салмақтардың қосындысы үшін. Тереңдігі lg N ағашы алынады, оның жапырақтарында көшірме салмақтар болады, ал қалған түйіндерде - ағаштың тамырындағы барлық салмақтардың қосындысына дейін ішінара қосындылар болады. Содан кейін біз 0-ден барлық салмақтардың қосындысына дейін кездейсоқ санды жасаймыз, i-ші репликаны табамыз, оны ағаштан алып тастаймыз және қалған көшірмелерді табу процедурасын қайталаймыз. Бұл алгоритммен ағашты құрудың күрделілігі O(N), i-ші репликаны табу және оны ағаштан жою күрделілігі O(lg N), K репликаларын таңдау күрделілігі O(N + K). lg N) ~ O(N lg N) .

Сызықтық журнал күрделілігі квадраттық күрделілікке қарағанда жақсырақ, әсіресе үлкен K үшін.

Бұл алгоритм кодта жүзеге асырылады Жобадан ClusterClient кітапханалары»Шығыс«. (Ол жерде ағаш O(N lg N) түрінде салынған, бірақ бұл алгоритмнің соңғы күрделілігіне әсер етпейді.)

2-тапсырма. Зебра

Жадтағы құжаттарды ерікті индекстелмеген өріс бойынша тиімді сұрыптау алгоритмін ұсыну қажет болды:

Сіздің командаңызға жадтағы қысқартылған құжат дерекқорын әзірлеу міндеті жүктелген. Жалпы жұмыс жүктемесі M өлшемі (әдетте N < 100 << M) жинағынан ерікті (индекстелмеген) сандық өріс бойынша сұрыпталған N жоғарғы құжатты таңдау болады. Жоғары S құжаттарын (S ~ N) өткізіп жібергеннен кейін N жоғарғы жағын таңдау сәл азырақ таралған жұмыс жүктемесі болады.

Осындай сұрауларды тиімді орындау үшін алгоритмді ұсыныңыз. Орташа жағдайда және ең нашар сценарийлерде үлкен O белгісін пайдаланып оның есептеу күрделілігін бағалаңыз.

Шешімді талдау (бейне)

34:50-де басталуы бар болғаны 6 минут:

Шешімді талдау (мәтін)

Беттік шешім: барлық құжаттарды сұрыптау (мысалы, жылдамдық), содан кейін N+S құжаттарын алыңыз. Бұл жағдайда сұрыптаудың күрделілігі орта есеппен O(M lg M), ең нашар жағдайда O(M2) болады.

Барлық М құжатты сұрыптап, одан кейін олардың аз ғана бөлігін алу тиімсіз екені анық. Барлық құжаттарды сұрыптамау үшін алгоритм қолайлы жылдам таңдау, ол қажетті құжаттардың N + S пернелерін таңдайды (оларды кез келген алгоритм бойынша сұрыптауға болады). Бұл жағдайда күрделілік орташа есеппен O(M) дейін төмендейді, ал ең нашар жағдай өзгеріссіз қалады.

Дегенмен, сіз мұны одан да тиімдірек жасай аласыз - алгоритмді қолданыңыз екілік үйінді ағыны. Бұл жағдайда бірінші N+S құжаттары min- немесе max-үймеге қосылады (сұрыптау бағытына байланысты), содан кейін әрбір келесі құжат ағымдағы минималды немесе максималды құжатты қамтитын ағаштың түбірімен салыстырылады, және қажет болса ағашқа қосылады. . Бұл жағдайда, ең нашар жағдайда, ағашты үнемі қайта құру қажет болғанда, күрделілік O(M lg M), орташа күрделілік жылдам таңдаудағыдай O(M) болады.

Дегенмен, үйме ағыны іс жүзінде оның түбір элементімен бір рет салыстырудан кейін үйінді қайта құрмай-ақ, құжаттардың көпшілігін жоюға болатындығына байланысты тиімдірек болып шықты. Мұндай сұрыптау Kontur жүйесінде әзірленген және пайдаланылатын Zebra жадтағы құжаттар базасында жүзеге асырылады.

Тапсырма 3. Мемлекеттік своптар

Күйлерді ауыстырудың ең тиімді алгоритмін ұсыну қажет болды:

Сіздің командаңызға N түйіндерінің таратылған кластері үшін керемет күй алмасу механизмін әзірлеу тапсырылған. i-ші түйіннің күйі (i+1)-ші түйінге, N-ші түйіннің күйі бірінші түйінге берілуі керек. Қолдау көрсетілетін жалғыз операция - екі түйін өз күйлерін атомдық түрде ауыстырған кезде күй ауыстыру. Күй свопы М миллисекундты алатыны белгілі. Әрбір түйін кез келген уақытта бір күйдің свопына қатыса алады.

Кластердегі барлық түйіндердің күйлерін тасымалдау қанша уақытты алады?

Шешімді талдау (мәтін)

Беттік шешім: бірінші және екінші элементтің күйлерін, содан кейін бірінші және үшінші, содан кейін бірінші және төртінші және т.б. Әрбір алмасудан кейін бір элементтің күйі қалаған күйде болады. O(N) ауыстыруларын жасап, O(N M) уақытын жұмсау керек.

Сызықтық уақыт ұзақ, сондықтан элементтердің күйлерін жұппен алмастыруға болады: біріншісі екіншісімен, үшіншісі төртіншімен және т.б. Әрбір мемлекеттік алмасудан кейін әрбір екінші элемент дұрыс позицияда болады. O(lg N) ауыстыруларын жасап, O(M lg N) уақытын өткізу керек.

Дегенмен, ауысымды одан да тиімді етуге болады - сызықтық емес, тұрақты уақытта. Ол үшін бірінші қадамда бірінші элементтің күйін соңғысымен, екіншісін соңғымен және т.б. ауыстыру керек. Соңғы элементтің күйі дұрыс күйде болады. Ал енді екінші элементтің күйін соңғысымен, үшіншісін соңғымен және т.б. ауыстыруымыз керек. Бұл алмасу раундынан кейін барлық элементтердің күйлері дұрыс позицияда болады. Барлығы O(2M) ~ O(1) ауыстырулар болады.

Бұндай шешім айналу екі осьтік симметриядан тұратын композиция екенін әлі есінде сақтайтын математикті таң қалдырмайды. Айтпақшы, ол бір емес, K < N позициялары бойынша жылжу үшін тривиальды түрде жалпыланады. (Нақты қалай екенін түсініктемелерде жазыңыз.)

Сізге басқатырғыштар ұнады ма? Басқа шешімдерді білесіз бе? Пікірлерде бөлісіңіз.

Міне, соңында пайдалы сілтемелер:

• туралы көбірек біліңіз инфрақұрылымды дамыту контурда
• ішкі жазбаларды қараңыз есептер жазылған парақша бөлінген жүйелер туралы
• бейне дәрістер сериясын қараңызҚарапайым адамдар үшін әдеттен тыс алгоритмдер»
• біздің арнаға жазылыңыз Telegram-дағы арна

Ақпарат көзі: www.habr.com