1. Soalan
Satu sistem iklan mempunyai N calon, dengan setiap pemberat mewakili peluang relatif untuk pemilihan. Permulaan diikuti oleh berjuta-juta cabutan item tunggal, jadi setiap cabutan haruslah hampir kepada O(1) sementara kemas kini pemberat secara kelompok kekal boleh dilakukan. Reka bentuk jadual alias dan rangkumi pemberat sifar, ralat titik apung, serta sempadan nombor rawak.
2. Kekangan dan penjelasan
- Mulakan dengan satu cabutan dengan penggantian; pensampelan tanpa penggantian dan kemas kini pemberat tunggal adalah lanjutan.
- Pemberat adalah bukan negatif dan jumlahnya mestilah positif; item dengan pemberat sifar tidak boleh sama sekali dipilih.
- Pensampel boleh menggunakan integer seragam dan nombor nyata seragam dalam
[0, 1). - Pembinaan semula dalam
O(N)selepas suatu kelompok pemberat boleh diterima, tetapi jadual lama tidak boleh mewakili pemberat baharu.
3. Pendekatan teras
Skalakan setiap pemberat kepada p_i = w_i * N / sum(w), yang puratanya ialah 1. Kekalkan tatasusunan prob dan alias dengan panjang N. Suatu baldi mengembalikan dirinya sendiri dengan kebarangkalian prob[i]; jika tidak, ia melompat ke alias[i]. Semasa pra-pemprosesan, letakkan nilai di bawah 1 dalam small dan nilai di atas 1 dalam large; pasangkan satu daripada setiap sisi, isi baldi kecil, dan kembalikan baki kapasiti kepada baldi besar sehingga semua baldi selesai.
Pensampelan pertama-tama memilih baldi secara seragam, kemudian membandingkan satu nombor nyata seragam dengan prob[i]. Jumlah luas yang diperuntukkan kepada setiap item asal bersamaan dengan kebarangkalian ternormalnya, jadi kekerapan jangka panjangnya adalah berkadar terus dengan pemberatnya.
4. Pelaksanaan rujukan
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. Kerumitan dan ketepatan
Pra-pemprosesan mengambil masa dan ruang O(N). Setiap sampel memerlukan satu pilihan baldi seragam, satu perbandingan, dan paling banyak satu carian tatasusunan, jadi ia adalah O(1). Apit prob ke dalam [0, 1] selepas ralat titik apung sisa; takrifkan julat integer sebagai separuh terbuka supaya baldi terakhir tidak terlepas.
Pengesahan memerlukan lebih daripada sekadar beberapa cabutan. Jana sampel yang mencukupi, bandingkan setiap kekerapan yang diperhatikan dengan w_i / sum(w), dan gunakan selang keyakinan atau ujian khi-kuasa dua untuk mengesan pincang yang ketara. Gantikan jadual yang dibina semula secara atomik supaya pensampel tidak pernah melihat versi yang bercampur.
6. Susulan dan perangkap
- Jadual alias sesuai untuk taburan statik atau dikemas kini secara kelompok. Untuk perubahan pemberat tunggal yang kerap, pokok Fenwick atau pokok segmen mungkin lebih sesuai.
- Melimpahkan jumlah sebelum penormalan merosakkan nisbah; gunakan kepersisan yang lebih luas atau skalakan terlebih dahulu.
- "O(1)" mengecualikan kos pembinaan semula dan tidak menjadikan penjana nombor rawak bebas kos.
- Jumlah sifar tidak mentakrifkan sebarang taburan. Tolak situasi ini daripada mengembalikan setiap item secara seragam.
7. Bacaan lanjut
Bandingkan hasil tambah awalan dengan carian binari, pokok Fenwick, pensampelan takungan, dan jadual alias: struktur awalan menyokong kemas kini dinamik dengan pensampelan O(log N), takungan sesuai untuk strim, dan jadual alias menukar pra-pemprosesan O(N) untuk cabutan O(1) thôngput tinggi.
8. Poin pemarkahan temu duga
Boleh membina baldi kecil dan besar
Calon harus menerangkan penskalaan pemberat kepada kapasiti purata 1 dan memindahkan baki kapasiti antara baldi kecil dan baldi besar.
Boleh membuktikan kebarangkalian pensampelan
Mereka harus menunjukkan bagaimana pemilihan baldi seragam ditambah satu lompatan alias memberikan setiap item jumlah luas sasarannya dan bukannya sekadar menghafal kod.
Boleh mengendalikan kes berangka dan sempadan
Mereka harus merangkumi pemberat sifar, jumlah sifar, pengapitan titik apung, julat rawak separuh terbuka, dan penggantian jadual secara atomik.
Boleh memilih struktur data yang betul
Mereka harus membandingkan kos pembinaan semula kelompok dengan kemas kini dinamik serta mengetahui masa untuk menggunakan pokok Fenwick atau hasil tambah awalan dan bukannya jadual alias.