1. 問題
ある広告システムにはN個の候補があり、各重みは選択される相対的な確率を表します。初期化の後に単一アイテムの抽出が何百万回も行われるため、重みの一括更新を可能にしつつ、各抽出はO(1)に近づける必要があります。エイリアステーブルを設計し、重み0、浮動小数点誤差、乱数の境界値を考慮してください。
2. 制約と明確化事項
- まずは復元抽出（1回の抽出）から始めます。非復元抽出や単一の重み更新は発展課題です。
- 重みは非負であり、その合計は正でなければなりません。重み0のアイテムが選択されてはなりません。
- サンプラーは、一様分布の整数と
[0, 1)の一様分布の実数を使用して構いません。 - 重みの一括更新後に
O(N)で再構築することは許容されますが、古いテーブルで新しい重みを表すことはできません。
3. コアアプローチ
各重みを、平均が1になるようにp_i = w_i * N / sum(w)にスケーリングします。長さNのprob配列とalias配列を保持します。あるバケットはprob[i]の確率で自身を返し、それ以外の場合はalias[i]にジャンプします。前処理では、1未満の値をsmallに、1以上の値をlargeに入れます。両側から1つずつペアにし、小さいバケットを満たして、余った容量を大きいバケットに戻すという操作を、すべてのバケットが完了するまで繰り返します。
サンプリングでは、まずバケットを一様に選択し、次に1つの一様実数とprob[i]を比較します。元の各アイテムに割り当てられた合計面積は正規化された確率と等しくなるため、長期的な出現頻度はその重みに比例します。
4. 参照実装
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. 計算量と正当性
前処理にはO(N)の時間と空間がかかります。各サンプリングには、一様なバケット選択1回、比較1回、最大1回の配列参照が必要なため、O(1)となります。残留浮動小数点誤差の発生後は、probを[0, 1]内にクランプします。最後のバケットを取りこぼさないように、整数の範囲は半開区間として定義してください。
検証には、単に数回抽出する以上のことが求められます。十分なサンプルを生成し、観測された各頻度をw_i / sum(w)と比較し、信頼区間やカイ二乗検定を使用して有意な偏りを検出します。再構築したテーブルはアトミックに置き換え、サンプラーが混在したバージョンを参照しないようにします。
6. 発展課題と落とし穴
- エイリアステーブルは、静的または一括更新される分布に適しています。頻繁に単一の重みが変更される場合は、フェニック木（Fenwick tree）やセグメント木の方が適している可能性があります。
- 正規化の前に合計値がオーバーフローすると比率が崩れます。より精度の高い型を使用するか、事前にスケーリングを行ってください。
- 「O(1)」には再構築のコストは含まれず、また乱数生成器のコストが無料になるわけではありません。
- 合計が0の場合は分布を定義できません。すべてのアイテムを一様に返すのではなく、拒否してください。
7. 参考資料
累積和と二分探索、フェニック木、リザーバサンプリング、エイリアステーブルを比較してください。累積和構造はO(log N)のサンプリングによる動的更新をサポートし、リザーバはストリームに適しており、エイリアステーブルは高スループットなO(1)の抽出のためにO(N)の前処理をトレードオフにします。
8. 面接の採点ポイント
小さいバケットと大きいバケットを構築できるか
候補者は、平均容量が1になるように重みをスケーリングし、小さいバケットと大きいバケットの間で余剰容量を移動させることについて説明できる必要があります。
サンプリング確率を証明できるか
単にコードを暗誦するだけでなく、一様なバケット選択と1回のエイリアスジャンプによって、各アイテムがどのように目標とする合計面積を得るかを示す必要があります。
数値および境界ケースを処理できるか
重み0、合計0、浮動小数点数のクランプ、半開区間の乱数範囲、およびアトミックなテーブル置き換えに対応できる必要があります。
適切なデータ構造を選択できるか
一括再構築コストと動的更新を比較し、エイリアステーブルの代わりにフェニック木や累積和をいつ使用すべきかを理解している必要があります。