1. Pertanyaan
Sebuah sistem iklan memiliki N kandidat, dengan setiap bobot mewakili peluang relatif untuk dipilih. Inisialisasi diikuti oleh jutaan pengambilan item tunggal, sehingga setiap pengambilan harus mendekati O(1) sementara pembaruan bobot secara batch tetap memungkinkan. Rancang tabel alias dan tangani bobot nol, kesalahan floating-point, serta batas-batas bilangan acak.
2. Batasan dan klarifikasi
- Mulailah dengan satu pengambilan dengan pengembalian (sampling with replacement); pengambilan sampel tanpa pengembalian dan pembaruan bobot tunggal merupakan ekstensi.
- Bobot bernilai non-negatif dan jumlah totalnya harus positif; item berbobot nol tidak boleh terpilih sama sekali.
- Pengambil sampel dapat menggunakan bilangan bulat seragam dan bilangan riil seragam dalam
[0, 1). - Membangun ulang dalam
O(N)setelah pembaruan batch bobot dapat diterima, tetapi tabel lama tidak dapat merepresentasikan bobot baru.
3. Pendekatan utama
Skalakan setiap bobot ke p_i = w_i * N / sum(w), yang rata-ratanya adalah 1. Pertahankan larik prob dan alias sepanjang N. Sebuah bucket mengembalikan dirinya sendiri dengan probabilitas prob[i]; jika tidak, ia melompat ke alias[i]. Selama prapemrosesan, masukkan nilai di bawah 1 ke dalam small dan nilai di atas 1 ke dalam large; pasangkan satu dari masing-masing sisi, isi bucket kecil, dan kembalikan sisa kapasitas ke bucket besar hingga semua bucket selesai.
Pengambilan sampel pertama-tama memilih sebuah bucket secara seragam, lalu membandingkan satu bilangan riil seragam dengan prob[i]. Total area yang dialokasikan untuk setiap item asli sama dengan probabilitas ternormalisasinya, sehingga frekuensi jangka panjangnya sebanding dengan bobotnya.
4. Referensi implementasi
build(weights):
n = len(weights)
scale = n / sum(weights)
scaled = [w * scale for w in weights]
prob = array(n)
alias = array(n)
small, large = [], []
for i, value in enumerate(scaled):
(small if value < 1 else large).append(i)
while small and large:
s = small.pop()
l = large.pop()
prob[s] = scaled[s]
alias[s] = l
scaled[l] -= 1 - scaled[s]
(small if scaled[l] < 1 else large).append(l)
for i in small + large:
prob[i] = 1
alias[i] = i
return prob, alias
sample(prob, alias, rng):
i = rng.uniform_int(0, len(prob))
return i if rng.uniform01() < prob[i] else alias[i]5. Kompleksitas dan kebenaran
Prapemrosesan membutuhkan waktu dan ruang O(N). Setiap sampel memerlukan satu pemilihan bucket seragam, satu perbandingan, dan paling banyak satu pencarian larik, sehingga kompleksitasnya adalah O(1). Lakukan clamp prob ke dalam [0, 1] setelah memperhitungkan sisa galat floating-point; tentukan rentang bilangan bulat sebagai setengah-terbuka agar bucket terakhir tidak terlewat.
Validasi memerlukan lebih dari sekadar beberapa kali pengambilan. Hasilkan sampel yang cukup, bandingkan setiap frekuensi yang diamati dengan w_i / sum(w), dan gunakan interval kepercayaan atau uji chi-squared untuk mendeteksi bias yang signifikan. Ganti tabel yang dibangun ulang secara atomik sehingga pengambil sampel tidak pernah melihat versi campuran.
6. Tindak lanjut dan jebakan
- Tabel alias cocok untuk distribusi statis atau yang diperbarui secara batch. Untuk perubahan bobot tunggal yang sering, Fenwick tree atau segment tree mungkin lebih cocok.
- Terjadinya overflow pada total bobot sebelum normalisasi merusak rasio; gunakan presisi yang lebih tinggi atau skalakan terlebih dahulu.
- "O(1)" tidak termasuk biaya pembangunan ulang dan tidak membuat generator bilangan acak menjadi tanpa biaya.
- Total nol tidak mendefinisikan distribusi apa pun. Tolak kondisi ini alih-alih mengembalikan setiap item secara seragam.
7. Bacaan lebih lanjut
Bandingkan prefix sum dengan binary search, Fenwick tree, reservoir sampling, dan tabel alias: struktur prefix mendukung pembaruan dinamis dengan pengambilan sampel O(log N), reservoir sampling cocok untuk streaming data, dan tabel alias menukar prapemrosesan O(N) demi pengambilan sampel throughput tinggi O(1).
8. Poin penilaian wawancara
Mampu membangun bucket kecil dan besar
Kandidat harus menjelaskan penskalaan bobot ke kapasitas rata-rata 1 dan memindahkan sisa kapasitas antara bucket kecil dan bucket besar.
Mampu membuktikan probabilitas pengambilan sampel
Kandidat harus menunjukkan bagaimana pemilihan bucket seragam ditambah satu lompatan alias menghasilkan total area target bagi setiap item, bukan sekadar menghafal kode.
Mampu menangani kasus numerik dan batas
Kandidat harus mencakup bobot nol, total nol, floating-point clamping, rentang acak setengah-terbuka, dan penggantian tabel atomik.
Mampu memilih struktur data yang tepat
Kandidat harus membandingkan biaya pembangunan ulang batch dengan pembaruan dinamis dan mengetahui kapan harus menggunakan Fenwick tree atau prefix sum alih-alih tabel alias.