如何高效地进行加权随机选择和替换？

带替换和不带替换的加权随机选择

从列表中选择带或不带替换的随机元素是编程中的常见任务。虽然已建立了未加权选择和无需替换的加权选择的方法，但选择替换的加权元素提出了独特的挑战。

替换加权选择的别名方法

一个对于这种情况，最有效的方法是 Alias 方法。它涉及创建有效表示加权列表的相同大小的 bin。

实现步骤：

1. 标准化权重：调整权重，以便它们的总和为 1.0，代表选择概率。
2. 创建分区：确定大于元素数量的最小 2 次幂并创建那么多分区。
3. 分配权重：将权重最小的元素放置在空分区中，尽可能填充它。
4. 填充分区：如果分区未满，则添加具有最高权重的元素来填充剩余空间。
5. 重复：继续分配权重，直到所有元素都被考虑在内。

运行时选择：

1. 生成一个 0 到 1 之间的随机数。
2. 按分区数的对数对数字进行位移（假设位移在您的平台上很快） ).
3. 如果分区被分割，则使用移位数的小数部分来决定选择哪个元素。

别名方法的优点：

• 通过替换进行快速高效的选择。
• 避免使用储库方法进行大量选择。
• 实现简单且内存高效。

以上是如何高效地进行加权随机选择和替换？的详细内容。更多信息请关注PHP中文网其他相关文章！