加权随机选择阵列 [英] 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
]

这个伪code，算法有问题应该在多个呼叫统计返回的ID四个要素 0 有关标识一个元素 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屋！