置換を伴う重み付きランダム選択に適したアプローチは何ですか?

重み付きランダム選択: 置換の制限を克服

最近、多くの開発者は、リストからの要素の重み付きランダム選択という課題に直面しています。交換ありと交換なし。非重み付け選択と置換なしの重み付け選択には効果的なアルゴリズムが存在しますが、置換を伴う重み付け選択に適したソリューションを見つけるのは難しいことが判明しています。

効率と簡素化を実現する革新的なアプローチの 1 つは、エイリアス法です。これは、重み付きリストに対して同じサイズのビンを作成することで機能します。これらのビンはビット操作を使用して効率的にインデックス付けされ、時間のかかるバイナリ検索を回避します。

エイリアス ルックアップ テーブルを形成するには:

1. 合計が 1.0 になるように重みを正規化します (例: (1 から) , 1, 1, 1, 1) から (0.2, 0.2, 0.2, 0.2, 0.2)).
2. 変数の数以上の最小の 2 のべき乗を決定し、その数のパーティションを作成します。 5 つの選択肢の例では、8 つのパーティションを作成します。
3. 空のパーティションに残りの最小の重みを割り当てます (例: パーティション 1 の重みは 0.075 になります)。
4. パーティションがいっぱいでない場合、同様に最も多くの重みを割り当てます (例: パーティション 2 の重みは 0.075 と 0.15 です)。

元の重みがすべて割り当てられるまで手順 3 と 4 を繰り返します。

runtime:

1. [0, 1] の範囲で乱数を生成します (例: 0.001100000)。
2. 乱数を log2(num_partitions) だけシフトして、関連するパーティションを見つけます (例: 001.1 はパーティション 2 にマップされます)。
3. パーティションが分割されている場合は、シフトされた乱数の小数部分を使用して分割を決定します。

このメソッドは重み付きランダムを効果的に処理します。置換による選択により、特にリストの大部分を選択する場合に、リザーバーベースのアプローチと比較してパフォーマンスが大幅に向上します。

以上が置換を伴う重み付きランダム選択に適したアプローチは何ですか?の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。