从数组中加权随机select

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

所有机会在一起（在数组内）总和为1。

你会build议什么algorithm最快，最适合巨大的计算？

例：

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

对于这个伪代码，所讨论的algorithm应该在多个调用中统计地返回ID为0四个元素，用于ID 1上的一个元素。

Answer 1

计算列表的离散累积密度函数（CDF） – 或者用简单的方式计算权重累积和的数组。 然后生成一个介于0和所有权重之和（在你的情况下可能是1）的范围内的随机数，在你的离散CDF数组中find这个随机数并得到对应于这个条目的值 – 这个是你的加权随机数。

Answer 2

该algorithm是直接的

 rand_no = rand(0,1) for each element in array if(rand_num < element.probablity) select and break rand_num = rand_num - element.probability 

Answer 3

ruby的例子

 #each element is associated with its probability a = {1 => 0.25 ,2 => 0.5 ,3 => 0.2, 4 => 0.05} #at some point, convert to ccumulative probability acc = 0 a.each { |e,w| a[e] = acc+=w } #to select an element, pick a random between 0 and 1 and find the first #cummulative probability that's greater than the random number r = rand selected = a.find{ |e,w| w>r } p selected[0] 

Answer 4

这可以在O（1）每个样品的预期时间完成如下。

计算每个元素i的CDF F（i）为概率小于或等于i的总和。

将元素i的范围r（i）定义为区间[F（i-1），F（i）]。

对于每个区间[（i-1）/ n，i / n]，创build一个由范围与区间重叠的元素列表组成的区块。 只要你相当小心，这整个arrays总共花费O（n）时间。

随机抽样数组时，只需计算随机数所在的桶，然后与列表中的每个元素进行比较，直到find包含它的时间间隔。

样本的成本是O（随机select列表的预期长度）<= 2。

Answer 5

另一个ruby的例子：

 def weighted_rand(weights = {}) raise 'Probabilities must sum up to 1' unless weights.values.inject(&:+) == 1.0 u = 0.0 ranges = Hash[weights.map{ |v, p| [u += p, v] }] u = rand ranges.find{ |p, _| p > u }.last end 

如何使用：

 weights = {'a' => 0.4, 'b' => 0.4, 'c' => 0.2} weighted_rand weights 

期待什么：

 d = 1000.times.map{ weighted_rand weights } d.count('a') # 396 d.count('b') # 406 d.count('c') # 198 

Answer 6

我发现这篇文章对于充分理解这个问题是最有用的。 这个stackoverflow的问题也可能是你在找什么。

---

我相信最佳的解决scheme是使用别名方法（维基百科） 。 它需要O（n）时间来初始化， O（1）时间做出select，并且O（n）存储器。

下面是用于生成加权n边模的结果的algorithm（从这里开始，从长度n数组中select一个元素是微不足道的）。 笔者假设你有滚动公平的模具（ floor(random() * n) ）和翻转有偏见的硬币的function（ random() < p ）。

algorithm：Vose的别名方法

初始化：

1. 创build数组Alias和Prob ，每个大小为n 。
2. 创build两个工作清单， 小和大 。
3. 用n乘以每个概率。
4. 对于每个缩放概率p _i ：
   1. 如果p _i <1 ，则将i添加到Small 。
   2. 否则（ p i≥1 ），将i加到Large中 。
5. Small和Large不是空的（ Large可能先被清空）
   1. 从Small中删除第一个元素; 称之为l 。
   2. 从Large中删除第一个元素; 称之为g 。
   3. 设置Prob [l] = p _l 。
   4. 设置别名[l] = g 。
   5. 设p _g ：=（p _g + p _l ）-1 。 （这是一个更为数字稳定的选项。）
   6. 如果p <1 ，则将g添加到小 。
   7. 否则（ p g≥1 ），将g加到Large中 。
6. 虽然大不是空的：
   1. 从Large中删除第一个元素; 称之为g 。
   2. 设置Prob [g] = 1 。
7. 虽然小不是空的：这是唯一可能的，由于数值不稳定。
   1. 从Small中删除第一个元素; 称之为l 。
   2. 设置Prob [l] = 1 。

代：

1. 从一个n- died骰子生成一个公平的模具卷; 打电话给我 。
2. 翻转出现概率为Prob [i]的有偏见的硬币。
3. 如果硬币出现“头”，回报我 。
4. 否则，返回Alias [i] 。

Answer 7

Ruby解决scheme使用拾取gem ：

 require 'pickup' chances = {0=>80, 1=>20} picker = Pickup.new(chances) 

例：

 5.times.collect { picker.pick(5) } 

给出了输出：

 [[0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 1, 1], [0, 0, 0, 0, 0], [0, 0, 0, 0, 1]] 

Answer 8

如果数组很小，我会给数组一个长度，在这种情况下，五，并分配适当的值：

 array[ 0 => 0 1 => 0 2 => 0 3 => 0 4 => 1 ] 

Answer 9

诀窍可能是采用反映概率的元素重复来对辅助数组进行采样

鉴于与其概率相关的要素，例如：

 h = {1 => 0.5, 2 => 0.3, 3 => 0.05, 4 => 0.05 } auxiliary_array = h.inject([]){|memo,(k,v)| memo += Array.new((100*v).to_i,k) } ruby-1.9.3-p194 > auxiliary_array => [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 4, 4, 4, 4, 4] auxiliary_array.sample 

如果您希望尽可能通用，则需要根据最大小数位数来计算乘数，并将其用于100：

 m = 10**h.values.collect{|e| e.to_s.split(".").last.size }.max 

Answer 10

这是我在生产中使用的一个PHP代码：

 /** * @return \App\Models\CdnServer */ protected function selectWeightedServer(Collection $servers) { if ($servers->count() == 1) { return $servers->first(); } $totalWeight = 0; foreach ($servers as $server) { $totalWeight += $server->getWeight(); } // Select a random server using weighted choice $randWeight = mt_rand(1, $totalWeight); $accWeight = 0; foreach ($servers as $server) { $accWeight += $server->getWeight(); if ($accWeight >= $randWeight) { return $server; } } } 

Answer 11

我会想象大于或等于0.8但小于1.0的数字select第三个元素。

换句话说：

x是0和1之间的随机数

如果0.0> = x <0.2：第1项

如果0.2> = x <0.8：第2项

如果0.8> = x <1.0：项目3

Answer 12

我将改善https://stackoverflow.com/users/626341/masciugo答案。;

基本上你做一个大arrays，一个元素出现的次数与权重成正比。

它有一些缺点。

1. 权重可能不是整数。 设想元素1具有pi的概率，元素2具有1-pi的概率。 你怎么划分呢？ 或者想象一下，如果有数百个这样的元素。
2. 创build的arrays可能非常大。 想象一下，如果最小公倍数是100万，那么我们需要一个100万个元素的数组，我们要挑选。

为了反击，这就是你所做的。

创build这样的数组，但只是随机插入一个元素。 插入元素的概率与权重成正比。

然后从通常的select随机元素。

所以如果有3个不同重量的元素，你只需从1-3个元素的数组中select一个元素。

如果构造元素为空，则可能会出现问题。 那只是没有元素出现在数组中，因为他们的骰子滚动不同。

在这种情况下，我提出元素插入的概率是p（插入）= wi / wmax。

这样，一个元素，即具有最高概率的元素将被插入。 其他元素将以相对概率插入。

说我们有2个对象。

元素1显示了20％的时间。 元素2显示了40％的时间，并具有最高的概率。

在数组中，元素2会一直出现。 元素1将显示一半的时间。

所以元素2将被称为元素1的2倍。一般来说，所有其他元素将被称为与他们的权重成正比。 所有的概率之和也是1，因为数组总是至less有1个元素。