Berlaku beberapa hari lepas Persidangan Hydra. Lelaki dari Kumpulan JUG.ru menjemput penceramah impian (Leslie Lamport! Cliff Click! Martin Kleppmann!) dan menumpukan dua hari untuk sistem dan pengkomputeran yang diedarkan. Kontur adalah salah seorang daripada tiga rakan kongsi persidangan itu. Kami bercakap di gerai, bercakap tentang storan kami yang diedarkan, bermain bingo dan menyelesaikan teka-teki.

Ini adalah siaran dengan analisis tugas di gerai Kontur daripada pengarang teks mereka. Siapa yang berada di Hydra - ini adalah alasan anda untuk mengingati pengalaman yang menyenangkan, yang tidak - peluang untuk meregangkan otak anda besar O-notasi.

Malah ada peserta yang membongkar carta selak menjadi slaid untuk menulis keputusan mereka. Saya tidak bergurau - mereka menyerahkan timbunan kertas ini untuk pengesahan:

Terdapat tiga tugas secara keseluruhan:

• tentang memilih replika mengikut pemberat untuk pengimbangan beban
• tentang menyusun keputusan pertanyaan terhadap pangkalan data dalam memori
• mengenai pemindahan keadaan dalam sistem teragih dengan topologi cincin

Tugasan 1. KlusterClient

Ia adalah perlu untuk mencadangkan satu algoritma untuk pemilihan cekap K daripada N replika berwajaran sistem teragih:

Pasukan anda ditugaskan untuk membangunkan perpustakaan pelanggan untuk kelompok nod N yang diedarkan secara besar-besaran. Perpustakaan akan menjejaki pelbagai metadata yang dikaitkan dengan nod (cth, latensinya, kadar tindak balas 4xx/5xx, dsb.) dan memberikan pemberat titik terapung W1..WN kepada mereka. Untuk menyokong strategi pelaksanaan serentak, perpustakaan harus dapat memilih K nod N secara rawak—peluang untuk dipilih hendaklah berkadar dengan berat nod.

Cadangkan algoritma untuk memilih nod dengan cekap. Anggarkan kerumitan pengiraannya menggunakan tatatanda O besar.

Kenapa semuanya dalam bahasa Inggeris?

Kerana dalam bentuk ini peserta persidangan bertarung dengan mereka dan kerana bahasa Inggeris adalah bahasa rasmi Hydra. Tugasan kelihatan seperti ini:

Ambil kertas dan pensel, fikir, jangan tergesa-gesa membuka spoiler dengan segera 🙂

Analisis penyelesaian (video)

Bermula pada 5:53, hanya 4 minit:

Dan berikut ialah cara mereka yang mempunyai carta selak melontarkan penyelesaian mereka:

Analisis penyelesaian (teks)

Penyelesaian berikut terletak pada permukaan: jumlahkan pemberat semua replika, hasilkan nombor rawak daripada 0 kepada jumlah semua pemberat, kemudian pilih replika-i supaya jumlah pemberat replika dari 0 hingga (i-1) ke adalah kurang daripada nombor rawak, dan jumlah berat replika dari 0 hingga ke-i - lebih daripada itu. Jadi adalah mungkin untuk memilih satu replika, dan untuk memilih yang seterusnya, anda perlu mengulangi keseluruhan prosedur tanpa mengambil kira replika yang dipilih. Dengan algoritma sedemikian, kerumitan memilih satu replika ialah O(N), kerumitan memilih replika K ialah O(N K) ~ O(N2).

Kerumitan kuadratik adalah buruk, tetapi ia boleh diperbaiki. Untuk melakukan ini, kami akan membina pokok segmen untuk jumlah berat. Pokok kedalaman lg N akan diperolehi, di dalam daunnya terdapat pemberat replika, dan di nod yang tinggal - jumlah separa, sehingga jumlah semua pemberat pada akar pokok. Seterusnya, kami menjana nombor rawak daripada 0 kepada jumlah semua pemberat, cari replika ke-i, keluarkannya daripada pokok, dan ulangi prosedur untuk mencari replika yang tinggal. Dengan algoritma ini, kerumitan membina pokok ialah O(N), kerumitan mencari replika ke-i dan mengeluarkannya daripada pokok ialah O(lg N), kerumitan memilih replika K ialah O(N + K. lg N) ~ O(N lg N) .

Kerumitan log linear lebih bagus daripada kerumitan kuadratik, terutamanya untuk K yang besar.

Ia adalah algoritma ini dilaksanakan dalam kod Pustaka KlusterClient daripada projek "Timur". (Di sana, pokok itu dibina dalam O(N lg N), tetapi ini tidak menjejaskan kerumitan akhir algoritma.)

Tugasan 2. Zebra

Ia adalah perlu untuk mencadangkan algoritma untuk pengisihan dokumen yang cekap dalam ingatan oleh medan tidak diindeks sewenang-wenangnya:

Pasukan anda ditugaskan untuk membangunkan pangkalan data dokumen dalam memori yang dipecahkan. Beban kerja biasa ialah memilih dokumen N teratas yang diisih mengikut medan berangka arbitrari (tidak diindeks) daripada koleksi saiz M (biasanya N < 100 << M). Beban kerja yang kurang biasa ialah memilih N atas selepas melangkau dokumen S atas (S ~ N).

Cadangkan algoritma untuk melaksanakan pertanyaan sedemikian dengan cekap. Anggarkan kerumitan pengiraannya menggunakan tatatanda O besar dalam kes purata dan senario kes terburuk.

Analisis penyelesaian (video)

Bermula pada 34:50, hanya 6 minit:

Analisis penyelesaian (teks)

Penyelesaian permukaan: mengisih semua dokumen (contohnya dengan cepat), kemudian ambil dokumen N+S. Dalam kes ini, kerumitan pengisihan adalah secara purata O(M lg M), paling teruk O(M2).

Jelas sekali bahawa menyusun semua dokumen M dan kemudian mengambil hanya sebahagian kecil daripadanya adalah tidak cekap. Untuk tidak mengisih semua dokumen, algoritma adalah sesuai pilih cepat, yang akan memilih N + S daripada dokumen yang dikehendaki (ia boleh diisih mengikut mana-mana algoritma). Dalam kes ini, kerumitan akan berkurangan kepada O(M) secara purata, manakala kes terburuk akan kekal sama.

Walau bagaimanapun, anda boleh melakukannya dengan lebih cekap - gunakan algoritma penstriman timbunan binari. Dalam kes ini, dokumen N+S pertama ditambahkan pada timbunan min atau maks (bergantung pada arah isihan), dan kemudian setiap dokumen seterusnya dibandingkan dengan akar pokok, yang mengandungi dokumen minimum atau maksimum semasa, dan ditambah pada pokok jika perlu. . Dalam kes ini, kerumitan dalam kes yang paling teruk, apabila anda perlu membina semula pokok secara berterusan, ialah O(M lg M), kerumitan secara purata ialah O(M), seperti pilihan pantas.

Walau bagaimanapun, penstriman timbunan ternyata lebih cekap kerana pada hakikatnya kebanyakan dokumen boleh dibuang tanpa membina semula timbunan selepas satu perbandingan dengan unsur akarnya. Pengisihan sedemikian dilaksanakan dalam pangkalan data dokumen dalam memori Zebra yang dibangunkan dan digunakan dalam Kontur.

Tugasan 3. Pertukaran negeri

Ia adalah perlu untuk mencadangkan algoritma yang paling cekap untuk menukar keadaan:

Pasukan anda ditugaskan untuk membangunkan mekanisme pertukaran keadaan mewah untuk gugusan nod N yang diedarkan. Keadaan nod ke-i harus dipindahkan ke nod (i+1)-ke, keadaan nod ke-N harus dipindahkan ke nod pertama. Satu-satunya operasi yang disokong ialah pertukaran keadaan apabila dua nod menukar keadaan mereka secara atom. Adalah diketahui bahawa pertukaran keadaan mengambil masa M milisaat. Setiap nod boleh mengambil bahagian dalam satu pertukaran keadaan pada bila-bila masa tertentu.

Berapa lama masa yang diambil untuk memindahkan keadaan semua nod dalam kelompok?

Analisis penyelesaian (teks)

Penyelesaian permukaan: tukar keadaan elemen pertama dan kedua, kemudian yang pertama dan ketiga, kemudian yang pertama dan keempat, dan seterusnya. Selepas setiap pertukaran, keadaan satu elemen akan berada dalam kedudukan yang diingini. Anda perlu membuat pilih atur O(N) dan menghabiskan masa O(N M).

Masa linear adalah panjang, jadi anda boleh menukar keadaan unsur secara berpasangan: yang pertama dengan yang kedua, yang ketiga dengan yang keempat, dan seterusnya. Selepas setiap pertukaran negeri, setiap elemen kedua akan berada di kedudukan yang betul. Anda perlu membuat pilih atur O(lg N) dan menghabiskan masa O(M lg N).

Walau bagaimanapun, adalah mungkin untuk membuat anjakan lebih cekap - bukan dalam linear, tetapi dalam masa yang tetap. Untuk melakukan ini, pada langkah pertama, anda perlu menukar keadaan elemen pertama dengan yang terakhir, yang kedua dengan yang terakhir, dan seterusnya. Keadaan elemen terakhir akan berada dalam kedudukan yang betul. Dan sekarang kita perlu menukar keadaan elemen kedua dengan yang terakhir, yang ketiga dengan yang terakhir, dan seterusnya. Selepas pusingan pertukaran ini, keadaan semua elemen akan berada dalam kedudukan yang betul. Akan ada pilih atur O(2M) ~ O(1) secara keseluruhan.

Penyelesaian sedemikian tidak akan mengejutkan ahli matematik yang masih ingat bahawa putaran adalah komposisi dua simetri paksi. Dengan cara ini, ia digeneralisasikan secara remeh untuk anjakan bukan oleh satu, tetapi oleh kedudukan K <N. (Tulis dalam komen bagaimana sebenarnya.)

Adakah anda suka teka-teki? Adakah anda tahu penyelesaian lain? Kongsi dalam komen.

Dan berikut adalah beberapa pautan berguna pada akhirnya:

• ketahui lebih lanjut tentang pembangunan infrastruktur dalam kontur
• lihat rekod dalaman risalah dengan laporan mengenai sistem teragih
• menonton siri ceramah videoAlgoritma yang luar biasa untuk orang biasa»
• melanggan kami saluran dalam Telegram

Sumber: www.habr.com