![How to Perform Weighted Random Selection with Replacement Efficiently?](https://img.php.cn/upload/article/000/000/000/172998756542002.jpg)
带替换和不带替换的加权随机选择
从列表中选择带或不带替换的随机元素是编程中的常见任务。虽然已建立了未加权选择和无需替换的加权选择的方法,但选择替换的加权元素提出了独特的挑战。
替换加权选择的别名方法
一个对于这种情况,最有效的方法是 Alias 方法。它涉及创建有效表示加权列表的相同大小的 bin。
实现步骤:
-
标准化权重:调整权重,以便它们的总和为 1.0,代表选择概率。
-
创建分区:确定大于元素数量的最小 2 次幂并创建那么多分区。
-
分配权重:将权重最小的元素放置在空分区中,尽可能填充它。
-
填充分区:如果分区未满,则添加具有最高权重的元素来填充剩余空间。
-
重复:继续分配权重,直到所有元素都被考虑在内。
运行时选择:
- 生成一个 0 到 1 之间的随机数。
- 按分区数的对数对数字进行位移(假设位移在您的平台上很快) ).
- 如果分区被分割,则使用移位数的小数部分来决定选择哪个元素。
别名方法的优点:
- 通过替换进行快速高效的选择。
- 避免使用储库方法进行大量选择。
- 实现简单且内存高效。
以上是如何高效地进行加权随机选择和替换?的详细内容。更多信息请关注PHP中文网其他相关文章!