Kedadeyan sawetara dina kepungkur Konferensi Hydra. Wong lanang saka JUG.ru Group ngundang pamicara ngimpi (Leslie Lamport! Cliff Click! Martin Kleppmann!) Kontur minangka salah siji saka telung mitra konferensi kasebut. Kita ngomong ing booth, ngomong babagan panyimpenan sing disebarake, main bingo, lan ngrampungake teka-teki.

Iki minangka kiriman kanthi analisis tugas ing stand Kontur saka penulis teks kasebut. Sapa sing ana ing Hydra - iki minangka alesan kanggo ngelingi pengalaman sing nyenengake, sing ora - kasempatan kanggo nggedhekake otak amba O- notasi.

Malah ana peserta sing mbongkar flipchart dadi slide kanggo nulis keputusane. Aku ora guyon - dheweke nyerahake tumpukan kertas iki kanggo verifikasi:

Ana telung tugas total:

• babagan milih replika kanthi bobot kanggo imbangan beban
• babagan ngurutake asil pitakon marang database ing memori
• ing transfer negara ing sistem mbagekke karo topologi ring

Tugas 1. ClusterClient

Sampeyan perlu ngusulake algoritma kanggo pilihan efisien K saka N replika bobot saka sistem sing disebarake:

Tim sampeyan ditugasake ngembangake perpustakaan klien kanggo kluster N node sing disebarake kanthi akeh. Perpustakaan bakal nglacak macem-macem metadata sing ana gandhengane karo simpul (contone, latensi, 4xx / 5xx tingkat respon, lsp.) lan menehi bobot titik ngambang W1..WN kanggo dheweke. Kanggo ndhukung strategi eksekusi bebarengan, perpustakaan kudu bisa milih K saka N simpul kanthi acak-kasempatan kanggo dipilih kudu proporsional karo bobot simpul.

Usulake algoritma kanggo milih simpul kanthi efisien. Ngitung kerumitan komputasi nggunakake notasi O gedhe.

Apa kabeh ing Inggris?

Amarga ing wangun iki peserta konferensi perang karo wong-wong mau lan amarga Inggris minangka basa resmi Hydra. Tugas katon kaya iki:

Njupuk kertas lan potlot, mikir, aja cepet-cepet mbukak spoiler langsung 🙂

Analisis solusi (video)

Wiwit jam 5:53, mung 4 menit:

Lan iki carane wong lanang nganggo flipchart menehi solusi:

Analisis solusi (teks)

Solusi ing ngisor iki dumunung ing permukaan: jumlah bobot kabeh replika, ngasilake nomer acak saka 0 nganti jumlah kabeh bobot, banjur pilih replika i supaya jumlah bobot replika saka 0 nganti (i-1) th. kurang saka nomer acak, lan jumlah bobot tiron saka 0 kanggo i-th - luwih saka iku. Dadi bakal bisa milih siji tiron, lan kanggo milih sing sabanjure, sampeyan kudu mbaleni kabeh prosedur tanpa nimbang replika sing dipilih. Kanthi algoritma kasebut, kerumitan milih replika yaiku O(N), kerumitan milih replika K yaiku O(N K) ~ O(N2).

Kompleksitas kuadrat ora apik, nanging bisa ditambah. Kanggo nindakake iki, kita bakal mbangun wit segmen kanggo jumlah bobot. Wit sing ambane lg N bakal dipikolehi, ing godhong sing bakal ana bobot replika, lan ing node sing isih ana - jumlah parsial, nganti jumlah kabeh bobot ing oyod wit. Sabanjure, kita ngasilake nomer acak saka 0 kanggo jumlah kabeh bobot, golek replika i-th, mbusak saka wit, lan baleni prosedur kanggo nemokake tiron isih. Kanthi algoritma iki, kerumitan mbangun wit yaiku O(N), kerumitan nemokake replika i-th lan mbusak saka wit kasebut yaiku O(lg N), kerumitan milih replika K yaiku O(N + K. lg N) ~ O(N lg N) .

Kompleksitas log linear luwih apik tinimbang kompleksitas kuadrat, utamane kanggo K sing gedhe.

Iku algoritma iki dipun ginakaken ing kode Pustaka ClusterClient saka proyek "Wétan". (Ana, wit dibangun ing O(N lg N), nanging iki ora mengaruhi kerumitan final saka algoritma.)

Tugas 2. Zebra

Sampeyan perlu ngusulake algoritma kanggo ngurutake dokumen kanthi efisien ing memori kanthi lapangan sing ora diindeks kanthi sewenang-wenang:

Tim sampeyan ditugasake ngembangake basis data dokumen ing memori sing rusak. Beban kerja sing umum yaiku milih dokumen N ndhuwur sing diurutake miturut kolom numerik arbitrer (ora diindeks) saka koleksi ukuran M (biasane N <100 << M). Beban kerja sing rada kurang umum yaiku milih N ndhuwur sawise ngliwati dokumen S ndhuwur (S ~ N).

Usulake algoritma kanggo nglakokake pitakon kasebut kanthi efisien. Ngira kerumitan komputasi nggunakake notasi O gedhe ing kasus rata-rata lan skenario paling awon.

Analisis solusi (video)

Wiwit jam 34:50, mung 6 menit:

Analisis solusi (teks)

Solusi lumahing: urut kabeh dokumen (contone karo cepet-cepet), banjur njupuk N+S dokumen. Ing kasus iki, kerumitan ngurutake rata-rata O (M lg M), paling awon O (M2).

Temenan yen ngurutake kabeh dokumen M banjur njupuk mung bagean cilik ora efisien. Supaya ora ngurutake kabeh dokumen, algoritma cocok cepet milih, sing bakal milih N + S saka dokumen sing dikarepake (bisa diurutake miturut algoritma apa wae). Ing kasus iki, kerumitan bakal suda kanggo O (M) ing rata-rata, nalika kasus paling awon bakal tetep padha.

Nanging, sampeyan bisa nindakake malah luwih irit - nggunakake algoritma streaming tumpukan biner. Ing kasus iki, dokumen N + S pisanan ditambahake menyang min- utawa max-heap (gumantung saka arah ngurutake), lan banjur saben dokumen sabanjuré dibandhingake ROOT saka wit, kang ngemot dokumen minimal utawa maksimum saiki, lan ditambahake ing wit yen perlu. Ing kasus iki, kerumitan ing kasus paling awon, nalika sampeyan kudu terus-terusan mbangun wit, iku O (M lg M), kerumitan ing rata-rata O (M), minangka karo quickselect.

Nanging, streaming tumpukan dadi luwih efisien amarga kasunyatane ing praktik umume dokumen bisa dibuwang tanpa mbangun maneh tumpukan kasebut sawise mbandhingake siji karo unsur oyod. Pengurutan kasebut ditindakake ing basis data dokumen memori Zebra sing dikembangake lan digunakake ing Kontur.

Tugas 3. Swap negara

Sampeyan perlu ngusulake algoritma sing paling efisien kanggo owah-owahan negara:

Tim sampeyan ditugasake ngembangake mekanisme ijol-ijolan negara sing apik kanggo klompok simpul N sing disebarake. Negara simpul i-th kudu ditransfer menyang simpul (i+1) -th, negara simpul N-th kudu ditransfer menyang simpul pisanan. Siji-sijine operasi sing didhukung yaiku swap negara nalika rong simpul ngganti negara kanthi atom. Dikenal yen swap negara njupuk M milidetik. Saben simpul bisa melu ing swap negara siji ing wektu tartamtu.

Suwene wektu kanggo mindhah status kabeh kelenjar ing kluster?

Analisis solusi (teks)

Solusi lumahing: ngganti negara unsur pisanan lan kaloro, banjur pisanan lan katelu, banjur pisanan lan papat, lan ing. Sawise saben ijol-ijolan, negara siji unsur bakal ana ing posisi sing dikarepake. Sampeyan kudu nggawe O(N) permutasi lan nglampahi wektu O(N M).

Wektu linear dawa, supaya sampeyan bisa ngganti negara unsur ing pasangan: pisanan karo kaloro, katelu karo papat, lan ing. Sawise saben ijol-ijolan negara, saben unsur kapindho bakal ana ing posisi sing bener. Sampeyan kudu nggawe O (lg N) permutasi lan nglampahi O (M lg N) wektu.

Nanging, iku bisa kanggo nggawe shift malah luwih efisien - ora ing linear, nanging ing wektu pancet. Kanggo nindakake iki, ing langkah pisanan, sampeyan kudu ngganti negara unsur pisanan karo pungkasan, kaloro karo penultimate, lan ing. Kahanan unsur pungkasan bakal ana ing posisi sing bener. Lan saiki kita kudu ngganti negara unsur kapindho karo sing pungkasan, katelu karo penultimate, lan sateruse. Sawise babak ijol-ijolan iki, negara kabeh unsur bakal ana ing posisi sing bener. Bakal ana O(2M) ~ O(1) permutasi total.

Solusi kasebut ora bakal kaget karo ahli matematika sing isih ngelingi yen rotasi minangka komposisi saka rong simetri aksial. Miturut cara, iku trivially umum kanggo shift ora dening siji, nanging dening posisi K <N. (Tulis ing komentar carane persis.)

Apa sampeyan seneng teka-teki? Apa sampeyan ngerti solusi liyane? Nuduhake ing komentar.

Lan ing ngisor iki sawetara pranala sing migunani ing pungkasan:

• sinau liyane babagan pembangunan infrastruktur ing kontur
• ndeleng cathetan saka internal flyer karo laporan babagan sistem sing disebarake
• nonton seri video ceramahAlgoritma sing ora biasa kanggo wong biasa»
• langganan kita saluran ing Telegram

Source: www.habr.com