Temu duga pengekodan: Bagaimanakah anda membuat persampelan secara seragam daripada strim dengan panjang yang tidak diketahui?

Prompt dan kes penggunaan

Anda hanya boleh membaca strim sekali sahaja; panjangnya n tidak diketahui, dan anda memerlukan k item berbeza dengan kebarangkalian yang sama. Anda tidak boleh menyimpan strim atau menunggu indeks rawak akhir. Pensampelan takungan mengekalkan takungan tetap bersaiz k: apabila item i tiba, ia masuk dengan kebarangkalian k/i dan menggantikan slot takungan yang dipilih secara seragam.

Prompt ini menguji algoritma penstriman rawak. Kertas kerja Vitter mengkaji pensampelan satu laluan apabila saiz populasi tidak diketahui, dan nota kursus universiti memberikan induksi keseragaman. Kategori teras ialah coding: tak varian kebarangkalian di bawah kekangan memori, bukan pelaksanaan platform data.

Perkara yang dinilai oleh penemu duga

• Sama ada anda mengenali corak takungan saiz tidak diketahui, satu laluan, dan memori tetap.
• Sama ada anda menerangkan peraturan penggantian k=1 1/i sebelum membuat generalisasi kepada k.
• Sama ada anda membuktikan bahawa selepas item i, setiap item mempunyai kebarangkalian k/i dalam sampel.
• Sama ada anda mengelakkan sampel pendua, andaian n diketahui yang salah, dan integer rawak yang berat sebelah (bias).
• Sama ada anda menyatakan masa O(n), ruang O(k), dan sempadan pensampelan berwajaran.

Penjelasan sebelum menjawab

• Adakah k integer positif? Apakah yang patut berlaku untuk k <= 0 atau item strim yang kurang daripada k?
• Adakah "berbeza" bermaksud rekod berbeza atau penyahduplikasian mengikut nilai?
• Bolehkah strim kosong, tidak terhingga, atau terganggu? Output dan pemulihannya berbeza.
• Adakah takungan akhir satu-satunya output, atau adakah ia mesti boleh diperhatikan semasa imbasan?
• Adakah API rawak menyediakan integer tidak berat sebelah merentasi julat yang diperlukan?
• Adakah sasaran seragam atau berwajaran/berstrata? Pensampelan berwajaran memerlukan tak varian yang berbeza.

Rangka jawapan 30 saat

"Isi takungan dengan k item pertama. Untuk item i, bermula pada satu, jana integer tidak berat sebelah j dalam [0, i-1]. Jika j < k, gantikan reservoir[j]; jika tidak, buang item tersebut. Selepas item i, setiap item mempunyai kebarangkalian k/i: item baharu masuk dengan k/i, dan item lama kekal dengan k/(i-1) darab 1 - 1/i. Algoritma ini adalah satu laluan, masa O(n), dan ruang tambahan O(k)."

Jawapan mendalam langkah demi langkah

Langkah 1: Mulakan dengan k=1.

Simpan item pertama. Untuk item i, gantikan calon semasa dengan kebarangkalian 1/i. Selepas memproses i item, setiap satu mempunyai kebarangkalian 1/i untuk dikekalkan.

Langkah 2: Buat generalisasi kepada k.

Isi k slot pertama. Untuk item i, masukkan dengan kebarangkalian k/i; jika ia masuk, pilih salah satu daripada k slot secara seragam. Integer j dalam [0, i-1] melaksanakan ini: j < k bermaksud gantikan slot j.

Langkah 3: Tulis pseudokod.

reservoir = first k items
for i = k+1 .. n:
  j = uniformInteger(0, i-1)
  if j < k:
    reservoir[j] = item i
return reservoir

Jika strim tidak boleh diisi terlebih dahulu, tambahkan semasa seen <= k, kemudian gunakan cabang yang sama. Penjana integer mesti meliputi julat lengkap tanpa bias.

Langkah 4: Buktikan kebarangkalian item baharu.

Pada item i, kebarangkalian penyertaannya ialah k/i. Setelah disertakan, ia kekal melalui setiap langkah seterusnya dengan kebarangkalian ∏(1 - 1/t) = i/n, kerana slot tertentu digantikan dengan kebarangkalian 1/t. Oleh itu, kebarangkalian akhirnya ialah k/i × i/n = k/n.

Langkah 5: Buktikan kebarangkalian item lama.

Andaikan setiap item lama mempunyai kebarangkalian k/(i-1) selepas item i-1. Pada langkah i, ia digantikan dengan kebarangkalian k/i × 1/k = 1/i, jadi ia kekal dengan 1 - 1/i. Kebarangkalian baharunya ialah k/(i-1) × (i-1)/i = k/i. Item baharu dan lama memenuhi tak varian yang sama.

Langkah 6: Analisis kerumitan dan penjanaan rawak.

Setiap item diproses sekali: masa O(n). Takungan memegang k item: ruang tambahan O(k). Untuk kiraan di luar ketepatan integer selamat, gunakan API integer tidak berat sebelah yang menyokong julat yang diperlukan.

Langkah 7: Kendalikan sempadan input.

Strim kosong mengembalikan sampel kosong. k = 0 mengembalikan sampel kosong atau mencetuskan ralat yang didokumenkan. Jika kurang daripada k item tiba, kembalikan item sebenar atau gagal mengikut kontrak. Penyahduplikasian mengikut nilai memerlukan keadaan tambahan dan mungkin melanggar O(k).

Langkah 8: Terangkan peluasan berwajaran dan teragih.

Pensampelan berwajaran mengubah taburan sasaran, jadi penggantian kebarangkalian sama adalah tidak sah; bincangkan kunci takungan berwajaran seperti Efraimidis–Spirakis. Takungan teragih memerlukan kiraan dan keutamaan/pemberat untuk digabungkan dengan betul; mencantumkan sampel shard secara langsung adalah berat sebelah.

Contoh jawapan berkualiti tinggi

"Saya mengekalkan takungan berkapasiti k. Mengisinya dengan k item pertama. Untuk item i = k+1 dan seterusnya, jana integer tidak berat sebelah j dalam [0, i-1]; jika j < k, gantikan slot j, jika tidak, buang. Item baharu masuk dengan kebarangkalian k/i. Item lama tertentu digantikan dengan kebarangkalian 1/i, jadi kebarangkaliannya berubah daripada k/(i-1) kepada k/(i-1) × (1-1/i) = k/i. Secara induksi, setiap item mempunyai kebarangkalian akhir k/n. Algoritma ini adalah satu laluan, masa O(n), dan ruang O(k). Saya menguji input kosong, k=1, k=0, rekod berulang, simulasi berulang, dan menerbitkan semula tak varian secara eksplisit untuk varian berwajaran atau teragih."

Kesilapan biasa

• Menyimpan keseluruhan strim terlebih dahulu → melanggar kekangan saiz tidak diketahui dan memori → kemas kini takungan secara dalam talian.
• Menggunakan 1/k untuk setiap item baharu → kebarangkalian tidak menyesuaikan dengan i → gunakan k/i.
• Menggunakan random() % i → operasi modulo boleh menjadi berat sebelah → gunakan pensampelan integer tidak berat sebelah.
• Memilih slot penggantian secara tidak seragam → sesetengah gabungan menjadi lebih berkemungkinan → pilih antara k slot secara seragam.
• Menggunakan k/n semasa mengimbas → n tidak diketahui dan kebarangkalian berubah pada setiap langkah → gunakan kiraan semasa i.
• Mengabaikan semantik pendua → rekod berbeza dan nilai berbeza adalah tidak sama → jelaskan penyahduplikasian terlebih dahulu.
• Mencantumkan takungan shard → saiz shard yang tidak sama membiaskan hasil → gabungkan dengan kiraan dan keutamaan.
• Menggunakan semula algoritma seragam untuk wajaran → taburan sasaran telah berubah → gunakan pensampelan takungan berwajaran dengan bukti baharu.

Soalan susulan dan jawapan

Soalan susulan 1: Mengapakah kebarangkalian penggantian item baharu ialah k/i?

Pada item i, algoritma memilih salah satu daripada i kedudukan secara seragam. Sebanyak k kedudukan pertama mewakili takungan, jadi peluang untuk mengenai salah satu daripadanya ialah k/i.

Soalan susulan 2: Bagaimanakah anda membuktikan keadilan untuk k=1?

Item pertama disimpan dengan kebarangkalian satu. Item i menggantikannya dengan 1/i; mana-mana item lama kekal dengan (1/(i-1)) × (1-1/i) = 1/i, memberikan induksi tersebut.

Soalan susulan 3: Bagaimanakah anda menjana integer yang tidak berat sebelah?

Gunakan API uniform-integer, atau rejection sampling yang membuang nilai rawak di luar julat boleh bahagi terbesar. Jangan anggap bahawa operasi modulo mudah sentiasa bebas daripada bias.

Soalan susulan 4: Bagaimana jika strim tamat sebelum k item?

Kembalikan item sebenar atau cetuskan ralat yang didokumenkan. Jangan sesekali mereka entri; nyatakan tingkah laku tersebut sebelum mengekod.

Soalan susulan 5: Bagaimanakah anda membuat persampelan dengan wajaran?

Tentukan taburan sasaran berwajaran, kemudian gunakan kunci rawak weighted-reservoir atau transformasi eksponen/log. Bukti seragam k/i tidak lagi terpakai secara langsung.

Soalan susulan 6: Bagaimanakah anda menggabungkan takungan teragih?

Setiap shard membawa bilangan itemnya dan maklumat keutamaan atau berat rawak yang mencukupi. Gabungkan mengikut peraturan pensampelan global; pencantuman langsung atau pemotongan rawak memihak kepada shard yang lebih kecil.

Soalan susulan 7: Bagaimanakah anda mengesahkan keseragaman?

Jalankan banyak percubaan pada strim pendek yang tetap, bandingkan kekerapan penyertaan setiap item dengan k/n, dan uji sempadan serta benih (seed) yang boleh dihasilkan semula. Statistik boleh mendedahkan bias, tetapi ia tidak menggantikan bukti kebarangkalian.