arrays - 从数组中加权随机选择

Question

我想从数组中随机选择一个元素，但每个元素都有一个已知的选择概率。

所有机会加在一起(在数组内)总和为 1。

您认为哪种算法最快且最适合大型计算？

例子:

id => chance
array[
    0 => 0.8
    1 => 0.2
]

对于这个伪代码，所讨论的算法应该在多次调用中统计地返回 id 0 上的四个元素，而 id 1 上有一个元素。

Answer 1

计算列表的离散累积密度函数 (CDF)，或者简单地说，计算权重的累积和数组。然后生成一个介于 0 和所有权重之和之间的随机数(在你的情况下可能为 1)，进行二进制搜索以在你的离散 CDF 数组中找到这个随机数并获得与该条目对应的值 - 这个是您的加权随机数。