加权随机选择阵列

加权随机选择阵列

本文介绍了加权随机选择阵列的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!

问题描述

我想随机地从一个阵列中选择一个元素,但每个元素有选择的已知概率。

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.

这篇关于加权随机选择阵列的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持!

08-23 16:03