从数组中加权随机选择 [英] Weighted random selection from array

问题描述

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

I would like to randomly select one element from an array, but each element has a known probability of selection.

所有机会(数组内)的总和为 1.

All chances together (within the array) sums to 1.

您认为哪种算法最快且最适合进行大量计算?

What algorithm would you suggest as the fastest and most suitable for huge calculations?

示例:

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

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

for this pseudocode, the algorithm in question should on multiple calls statistically return four elements on id 0 for one element on id 1.

推荐答案

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

Compute the discrete cumulative density function (CDF) of your list -- or in simple terms the array of cumulative sums of the weights. Then generate a random number in the range between 0 and the sum of all weights (might be 1 in your case), do a binary search to find this random number in your discrete CDF array and get the value corresponding to this entry -- this is your weighted random number.

这篇关于从数组中加权随机选择的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！