从数组中加权随机select

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

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

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

例:

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

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

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

该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 

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] 

这可以在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。

另一个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 

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


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

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

algorithm:Vose的别名方法

初始化:

  1. 创build数组AliasProb ,每个大小为n
  2. 创build两个工作清单,
  3. n乘以每个概率。
  4. 对于每个缩放概率p i
    1. 如果p i <1 ,则将i添加到Small
    2. 否则( p i≥1 ),将i加到Large中
  5. SmallLarge不是空的( 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]

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]] 

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

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

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

鉴于与其概率相关的要素,例如:

 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 

这是我在生产中使用的一个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; } } } 

我会想象大于或等于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

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

基本上你做一个大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个元素。