如何生成加权随机数：拒绝采样与迭代权重求和？

生成加权随机数

简介

在各种应用中，经常需要从一组选项中选择一个随机数，其中每个选项都被分配了一个特定的被选择概率。这个概念称为生成加权随机数。

拒绝采样方法

生成加权随机数的一种方法是通过拒绝采样。这种方法涉及创建一个查找表，其中每个选项出现的次数与其指定的权重一样多。例如，如果选项 A 有 80% 的概率，它会在查找表中出现 80 次。要生成随机数，需要在表中选择一个随机位置，并返回相应的选项。

拒绝采样的优点和缺点

拒绝采样提供常数- 构建查找表后选择随机数的时间性能。然而，它需要线性算法性能来构建表格，这对于大量选项或具有高精度权重的选项可能会出现问题。

迭代权重求和方法

另一种方法是迭代权重求和。这里，在 [0,1) 范围内生成一个随机数，并将其与权重的累积和进行比较。与超过随机数的权重相关的选项被选为加权随机数。

迭代权重求和的优缺点

与拒绝采样相比，迭代权重求和没有前期成本，但具有与集合中选项数量相关的线性平均算法性能。它还假设权重总和为 1。

实现注意事项

实现这些方法时，建议创建一个采用权重规范的高阶函数并返回一个生成加权随机数的函数。这允许可重用​​性，并避免构建查找表或多次累加权重的开销。

以上是如何生成加权随机数：拒绝采样与迭代权重求和？的详细内容。更多信息请关注PHP中文网其他相关文章！