Temu duga pengekodan: Melaksanakan pensampelan takungan berwajaran

1. Gesaan dan konteks

Setiap rekod dalam strim mempunyai wajaran positif, tetapi bilangan item mahupun jumlah keseluruhan wajaran tidak diketahui. Laksanakan sampel berwajaran bersaiz k tanpa penggantian: setiap rekod muncul paling banyak sekali, peluang rangkumannya berkadar dengan wajarannya, dan strim diimbas sekali sahaja. Terangkan penjanaan kunci, penyelenggaraan calon, wajaran ekstrem dan ujian taburan.

2. Perkara yang diuji oleh penemu duga

Sama ada anda membezakan pensampelan dengan dan tanpa penggantian serta memahami kebarangkalian yang berkadar dengan wajaran.
Sama ada anda boleh menukar pensampelan berwajaran kepada mengekalkan k keutamaan rawak atau kunci eksponen teratas.
Sama ada anda memilih min-heap bersaiz k dan memberikan kemas kini O(log k) bagi setiap rekod.
Sama ada anda mengendalikan wajaran sifar, sangat besar atau sangat kecil, sempadan rawak, ID pendua dan benih (seed) yang boleh dihasilkan semula.

3. Soalan penjelasan sebelum menjawab

Adakah wajaran merupakan nombor positif terhingga, dan patutkah rekod berwajaran sifar digugurkan atau dikekalkan?
Adakah pensampelan ini tanpa penggantian, atau bolehkah rekod muncul lebih daripada sekali?
Adakah hanya sampel akhir yang diperlukan, atau adakah setiap awalan (prefix) mesti mempunyai taburan yang betul?
Adakah beberapa serpihan (shards) perlu digabungkan, keadaan dikekalkan (persisted), atau hasil dihasilkan semula dengan tepat?

4. Rangka kerja jawapan 30 saat

Jana kunci rawak bebas bagi setiap rekod dengan wajaran w dan kekalkan k kunci terbesar. Bentuk yang stabil mengambil u secara seragam daripada (0, 1] dan mengira key = log(u) / w; disebabkan kunci adalah negatif, ini bersamaan dengan mengekalkan k kunci yang paling hampir dengan sifar. Simpan sampel semasa dalam min-heap bersaiz k yang akarnya merupakan kunci terkecil; gantikannya hanya apabila kunci baharu lebih besar. Satu laluan mengambil masa O(n log k) dan ruang tambahan O(k). Sahkan wajaran dan jadikan sumber rawak boleh disuntik (injectable).

5. Jawapan mendalam langkah demi langkah

Langkah 1: Tentukan taburan

Pensampelan berwajaran tanpa penggantian bukanlah k cabutan bebas dengan kebarangkalian w / total, kerana ini boleh mengulangi rekod. Sasaran adalah set bersaiz k yang taburan statistik tertibnya bersamaan dengan mencabut item yang belum dipilih secara berulang kali berkadar dengan baki wajarannya. Takungan mestilah sampel yang sah selepas setiap awalan, bukan sahaja selepas strim berakhir.

Langkah 2: Jana kunci yang stabil dari segi berangka

Perlumbaan eksponen memberikan pelaksanaan yang mudah: cabut u secara seragam dan kira key = log(u) / w, kemudian kekalkan kunci terbesar. Apabila u menghampiri sifar, log(u) menjadi lebih negatif; wajaran yang lebih besar menjadikan kunci lebih dekat kepada sifar dan oleh itu lebih berkemungkinan untuk memasuki k teratas. Elakkan u ** (1 / w), yang boleh mengalami limpah bawah (underflow) atau kehilangan pemisahan bagi wajaran ekstrem.

text

sample_key(weight):
    require finite(weight) and weight > 0
    u = uniform_random_open_interval()
    return log(u) / weight

Langkah 3: Kekalkan k-teratas dengan min-heap

Simpan (key, sequence, item) dalam timbunan, menggunakan jujukan untuk memutuskan seri kunci yang sama. Tolak masuk selagi takungan belum penuh. Setelah penuh, bandingkan kunci baharu dengan akar dan ganti hanya jika ia lebih besar. Jika k adalah sifar, buang setiap rekod. Menyusun semula tatasusunan selepas setiap rekod akan menjadikan kemas kini berkerumitan O(k log k) dan bukannya O(log k).

Langkah 4: Kendalikan sempadan input dan kerawakan

Tolak NaN, infiniti dan wajaran negatif. Rekod berwajaran sifar tidak boleh dipilih oleh sampel berwajaran positif dan boleh dilangkau. Sumber rawak tidak boleh menghasilkan sifar, jika tidak log(0) menjadi tidak boleh digunakan; cabut semula atau hadkan (clamp) kepada nilai titik terapung positif terkecil. Anggap ID pendua sebagai rekod berasingan melainkan masalah tersebut secara jelas meminta penyahduplikasian ID. Suntik sumber pseudo-rawak dalam ujian supaya kegagalan boleh dihasilkan semula.

Langkah 5: Kerumitan, pengesahan dan lanjutan teragih

Untuk n rekod, pelaksanaan mesin tunggal mengambil masa O(n log k) dan ruang tambahan O(k). Gunakan simulasi Monte Carlo wajaran tetap untuk memeriksa bahawa rangkuman marginal meningkat mengikut wajaran, dan lakukan penegasan (assert) bahawa sampel tidak mempunyai pendua. Dalam strim teragih, setiap serpihan boleh menjana kunci dengan peraturan yang sama dan penyelaras boleh menggabungkan calon k-teratas serpihan; keadaan, kemas kini, pemadaman, benih dan kos komunikasi masih memerlukan reka bentuk yang jelas. Hanya melakukan pensampelan secara seragam daripada takungan serpihan akan kehilangan maklumat rekod yang dibuang.

6. Contoh jawapan berkualiti tinggi

Bagi setiap rekod berwajaran positif, saya menjana key = log(u) / w, dengan u adalah seragam pada selang terbuka, dan mengekalkan k kunci terbesar. Kunci adalah negatif, jadi wajaran yang lebih besar cenderung lebih dekat kepada sifar. Min-heap berkapasiti k menyimpan sampel; apabila penuh, kunci baharu hanya menggantikan akar terkecil jika ia lebih besar. Saya menentukan tingkah laku bagi wajaran tidak sah, nilai rawak sifar, k = 0 dan rekod pendua. Imbasan mengambil masa O(n log k) dan ruang O(k). Saya mengesahkan taburan dengan simulasi wajaran tetap berulang dan menggabungkan calon teragih mengikut peraturan kunci k-teratas global yang sama.

7. Kesilapan lazim

Mencabut secara bebas dengan w / total → menghasilkan pendua dan bukan pensampelan tanpa penggantian → gunakan kunci rawak dan k-teratas.
Mengira u ** (1 / w) secara terus → limpah bawah (underflow) bagi wajaran ekstrem → bandingkan kunci logaritma.
Menggunakan max-heap untuk k-teratas → memerlukan pencarian nilai terkecil → gunakan min-heap supaya titik penggantian adalah pada akarnya.
Membenarkan u = 0 → log(0) menjadi infiniti negatif → gunakan sumber selang terbuka atau cabut semula.
Menguji satu output sahaja → terlepas berat sebelah (bias) jangka panjang → jalankan ujian Monte Carlo wajaran tetap dan tegaskan tiada pendua.

8. Soalan susulan dan respons

Mengapakah key = log(u) / w menghasilkan pensampelan berwajaran?

Anggap -log(u) sebagai pemboleh ubah eksponen dengan kadar satu. Membahagikannya dengan w memberikan masa eksponen dengan kadar w. Masa eksponen terkecil lebih berkemungkinan datang daripada kadar yang lebih besar; menjadikannya negatif bermaksud mengekalkan kunci terbesar, yang menghasilkan pensampelan berwajaran tanpa penggantian.

Bagaimanakah anda membuatkan keputusan boleh dihasilkan semula?

Suntik sumber pseudo-rawak dengan benih (seed) yang jelas dan rekodkan pengecam item, versi wajaran dan versi algoritma dalam metadata eksperimen. Jangan bergantung pada penjadualan bebenang (thread) atau keadaan rawak global, jika tidak input yang sama mungkin menghasilkan sampel yang berbeza.

Bolehkah dua takungan yang telah dibina digabungkan?

Jika kedua-dua serpihan menjana kunci bebas di bawah peraturan yang sama, gabungkan kunci calon mereka dan ambil k teratas global. Menganggap hanya dua takungan akhir sebagai data biasa dan melakukan pensampelan semula akan kehilangan maklumat tentang rekod yang telah dibuang. Kunci yang disimpan serta kemas kini atau pemadaman serpihan juga memerlukan tingkah laku yang ditakrifkan.

Bagaimana jika wajaran berubah mengikut masa?

Mengubah wajaran akan mengubah taburan sasaran, jadi kunci lama tidak lagi mewakili wajaran baharu. Jana semula kunci untuk rekod yang terjejas atau masukkan semula peristiwa dengan versi wajaran ke dalam strim. Nyatakan sama ada anggaran jangka pendek boleh diterima dan bagaimana sampel lama dilupuskan.

Temu duga pengekodan: Melaksanakan pensampelan takungan berwajaran

Soalan