从数组中加权随机select

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

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

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

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

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

` `/** * @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; } } }` `

x是0和1之间的随机数

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