Bir neçə gün əvvəl baş verib . JUG.ru Qrupunun uşaqları xəyal spikerlərini (Leslie Lamport! Cliff Click! Martin Kleppmann!) dəvət etdilər və iki günü paylanmış sistemlərə və hesablamalara həsr etdilər. Kontur konfransın üç tərəfdaşından biri idi. Biz stenddə danışdıq, paylanmış anbarlarımız haqqında danışdıq, bingo oynadıq və bulmacalar həll etdik.
Bu, mətnin müəllifindən Kontur stendindəki tapşırıqların təhlili ilə yazıdır. Hydra-da kim idi - bu xoş təcrübəni xatırlamaq üçün səbəbdir, kim yox idi - beyninizi uzatmaq şansı böyük O- qeyd.
Hətta qərarlarını yazmaq üçün flipçartı slaydlara sökən iştirakçılar var idi. Mən zarafat etmirəm - onlar yoxlama üçün bu kağız yığınını verdilər:
Ümumilikdə üç vəzifə var idi:
- yük balansı üçün çəkilər üzrə replikaların seçilməsi haqqında
- sorğu nəticələrinin yaddaşdaxili verilənlər bazasına görə çeşidlənməsi haqqında
- halqa topologiyası ilə paylanmış sistemdə vəziyyətin ötürülməsi haqqında
Tapşırıq 1. ClusterClient
Paylanmış sistemin N ölçülü surətindən K-nin səmərəli seçilməsi üçün alqoritm təklif etmək lazım idi:
Komandanıza N qovşaqdan ibarət kütləvi şəkildə paylanmış çoxluq üçün müştəri kitabxanası hazırlamaq tapşırılıb. Kitabxana qovşaqlarla əlaqəli müxtəlif metaməlumatları (məsələn, onların gecikmələri, 4xx/5xx cavab dərəcələri və s.) izləyəcək və onlara W1..WN üzən nöqtə çəkiləri təyin edəcək. Paralel icra strategiyasını dəstəkləmək üçün kitabxana N qovşaqdan K-ni təsadüfi seçə bilməlidir - seçilmə şansı düyünün çəkisinə mütənasib olmalıdır.
Düyünləri səmərəli seçmək üçün alqoritm təklif edin. Böyük O qeydindən istifadə edərək onun hesablama mürəkkəbliyini qiymətləndirin.
Niyə hər şey ingilis dilindədir?
Çünki bu formada konfrans iştirakçıları onlarla mübarizə aparırdılar və ingilis dili Hydranın rəsmi dili olduğundan. Tapşırıqlar belə görünürdü:
Kağız və qələm götür, düşünün, dərhal spoyler açmağa tələsməyin 🙂
Həllin təhlili (video)
5:53-dən başlayaraq, cəmi 4 dəqiqə:
Flipçartlı uşaqlar öz həll yollarını necə təqdim etdilər:
Həllin təhlili (mətn)
Aşağıdakı həll səthdə yerləşir: bütün replikaların çəkilərini cəmləyin, 0-dan bütün çəkilərin cəminə təsadüfi bir ədəd yaradın, sonra i-replikasını seçin ki, replika çəkilərinin cəmi 0-dan (i-1)-ə qədər olsun. təsadüfi ədəddən azdır və 0-dan i-ciyə qədər olan replika çəkilərinin cəmi ondan çoxdur. Beləliklə, bir replikanı seçmək mümkün olacaq və növbətisini seçmək üçün seçilmiş replikanı nəzərə almadan bütün proseduru təkrarlamaq lazımdır. Belə bir alqoritmlə bir replikanın seçilməsinin mürəkkəbliyi O(N), K replikasının seçilməsinin mürəkkəbliyi O(N K) ~ O(N2) təşkil edir.
Kvadrat mürəkkəblik pisdir, lakin onu təkmilləşdirmək olar. Bunun üçün biz tikəcəyik çəkilərin cəmi üçün. lg N dərinliyində bir ağac əldə ediləcək, onun yarpaqlarında replika çəkilər, qalan qovşaqlarda isə ağacın kökündəki bütün çəkilərin cəminə qədər qismən məbləğlər olacaqdır. Sonra 0-dan bütün çəkilərin cəminə qədər təsadüfi bir ədəd yaradırıq, i-ci replikanı tapırıq, onu ağacdan çıxarırıq və qalan replikaları tapmaq üçün proseduru təkrar edirik. Bu alqoritmlə ağacın qurulmasının mürəkkəbliyi O(N), i-ci replikanın tapılması və onun ağacdan çıxarılmasının mürəkkəbliyi O(lg N), K replikasının seçilməsinin mürəkkəbliyi O(N+K)-dir. lg N) ~ O(N lg N) .
Xətti log mürəkkəbliyi kvadratik mürəkkəblikdən daha gözəldir, xüsusən də böyük K üçün.
Bu alqoritmdir Layihədən ClusterClient kitabxanaları "". (Orada ağac O(N lg N) şəklində qurulur, lakin bu, alqoritmin son mürəkkəbliyinə təsir etmir.)
Tapşırıq 2. Zebra
Yaddaşdakı sənədlərin ixtiyari indeksləşdirilməmiş sahə ilə səmərəli çeşidlənməsi üçün bir alqoritm təklif etmək lazım idi:
Komandanızın tapşırığı yaddaşdaxili sənəd verilənlər bazası yaratmaqdır. Ümumi iş yükü M ölçülü kolleksiyadan (adətən N < 100 << M) ixtiyari (indekslənməmiş) rəqəmli sahə ilə çeşidlənmiş ən yaxşı N sənədi seçməkdir. Bir az daha az ümumi iş yükü yuxarı S sənədlərini (S ~ N) atladıqdan sonra üst N-i seçmək olardı.
Bu cür sorğuları səmərəli şəkildə yerinə yetirmək üçün alqoritm təklif edin. Orta vəziyyətdə və ən pis vəziyyət ssenarilərində böyük O qeydindən istifadə edərək onun hesablama mürəkkəbliyini qiymətləndirin.
Həllin təhlili (video)
34:50-dən başlayaraq, cəmi 6 dəqiqə:
Həllin təhlili (mətn)
Səthi həll: bütün sənədləri çeşidləyin (məsələn ), sonra N+S sənədlərini götürün. Bu halda çeşidləmənin mürəkkəbliyi orta hesabla O(M lg M), ən pis halda O(M2) olur.
Aydındır ki, bütün M sənədləri çeşidləmək və sonra onların yalnız kiçik bir hissəsini götürmək səmərəsizdir. Bütün sənədləri çeşidləməmək üçün bir alqoritm uyğun gəlir , istədiyiniz sənədlərdən N + S seçəcək (onları istənilən alqoritmlə sıralamaq olar). Bu halda mürəkkəblik orta hesabla O(M) səviyyəsinə qədər azalacaq, ən pis halda isə dəyişməz qalacaq.
Bununla belə, bunu daha da səmərəli edə bilərsiniz - alqoritmdən istifadə edin . Bu halda, ilk N+S sənədləri min- və ya max-heap-a əlavə olunur (çeşidləmə istiqamətindən asılı olaraq) və sonra hər bir növbəti sənəd cari minimum və ya maksimum sənədi ehtiva edən ağacın kökü ilə müqayisə edilir, və lazım olduqda ağaca əlavə edilir. . Bu halda, ən pis halda, ağacı daim yenidən qurmaq məcburiyyətində qaldığınız zaman mürəkkəblik O(M lg M) olur, orta hesabla mürəkkəblik Quickselectdə olduğu kimi O(M) olur.
Bununla belə, yığın axını daha səmərəli olur, ona görə ki, praktikada sənədlərin çoxu yığını onun kök elementi ilə bir dəfə müqayisə etdikdən sonra yenidən qurmadan atmaq olar. Belə çeşidləmə Konturda işlənib hazırlanmış və istifadə olunan Zebra yaddaşdaxili sənədlər bazasında həyata keçirilir.
Tapşırıq 3. Dövlət svopları
Vəziyyətlərin dəyişdirilməsi üçün ən səmərəli alqoritmi təklif etmək lazım idi:
Komandanıza N qovşaqdan ibarət paylanmış çoxluq üçün zərif dövlət mübadiləsi mexanizmini hazırlamaq tapşırılıb. i-ci qovşağın vəziyyəti (i+1)-ci qovşağa, N-ci qovşağın vəziyyəti birinci qovşağa köçürülməlidir. Dəstəklənən yeganə əməliyyat, iki qovşaq öz dövlətlərini atomik şəkildə dəyişdirdikdə vəziyyət mübadiləsidir. Məlumdur ki, dövlət mübadiləsi M millisaniyə çəkir. Hər bir qovşaq istənilən anda vahid dövlət mübadiləsində iştirak edə bilər.
Bir klasterdəki bütün qovşaqların vəziyyətlərini köçürmək nə qədər vaxt aparır?
Həllin təhlili (mətn)
Səthi həll: birinci və ikinci elementin vəziyyətini, sonra birinci və üçüncü, sonra birinci və dördüncü və s. Hər mübadilədən sonra bir elementin vəziyyəti istənilən vəziyyətdə olacaq. Siz O(N) dəyişdirmələri etməli və O(NM) vaxtını sərf etməlisiniz.
Xətti vaxt uzundur, ona görə də elementlərin vəziyyətlərini cüt-cüt mübadilə edə bilərsiniz: birincisi ikinci ilə, üçüncüsü dördüncü ilə və s. Hər bir dövlət mübadiləsindən sonra hər ikinci element düzgün mövqedə olacaq. Siz O(lg N) dəyişdirmələrini etməli və O(M lg N) vaxtını sərf etməlisiniz.
Bununla belə, yerdəyişməni daha da səmərəli etmək mümkündür - xətti deyil, sabit vaxtda. Bunu etmək üçün, ilk addımda, birinci elementin vəziyyətini sonuncu ilə, ikincinin sondan əvvəlki ilə və s. Son elementin vəziyyəti düzgün vəziyyətdə olacaq. İndi biz ikinci elementin vəziyyətini sonuncu ilə, üçüncü elementin sondan əvvəlki elementlə və s. Bu mübadilə raundundan sonra bütün elementlərin vəziyyətləri düzgün mövqedə olacaq. Ümumilikdə O(2M) ~ O(1) dəyişmələri olacaq.
Belə bir həll fırlanmanın iki eksenel simmetriyanın tərkibi olduğunu hələ də xatırlayan bir riyaziyyatçını heç təəccübləndirməyəcəkdir. Yeri gəlmişkən, bir deyil, K <N mövqeləri ilə bir yerdəyişmə üçün trivial şəkildə ümumiləşdirilir. (Dəqiq necə olduğunu şərhlərdə yazın.)
Bulmacaları bəyəndinizmi? Başqa həll yollarını bilirsinizmi? Şərhlərdə paylaşın.
Və sonda bəzi faydalı bağlantılar var:
- haqqında daha çox öyrən konturda
- daxili qeydlərə baxın paylanmış sistemlər haqqında
- video mühazirələr seriyasına baxın»
- səhifəmizə abunə olun
Mənbə: www.habr.com