blocks|key|847225|text|如果数组很小，我会给数组一个长度，在本例中为5，并根据需要赋值：|type|unstyled|depth|inlineStyleRanges|entityRanges|data|847226|array[
++++0+=>+0
++++1+=>+0
++++2+=>+0
++++3+=>+0
++++4+=>+1
]|code-block|syntax|javascript|847227|entityMap^0|0|0^^$0|@$1|2|3|4|5|6|7|I|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|J|8|@]|9|@]|A|$E|F]]|$1|G|3|-4|5|6|7|K|8|@]|9|@]|A|$]]]|H|$]]

If the array is small, I would give the array a length of, in this case, five and assign the values as appropriate:

<pre><code>array[
 0 =&gt; 0
 1 =&gt; 0
 2 =&gt; 0
 3 =&gt; 0
 4 =&gt; 1
]
</code></pre>

blocks|key|1061642|text|计算列表的离散累积密度函数(CDF)+--或者简单地说，就是权重的累积和数组。然后在0和所有权重的总和之间生成一个随机数(在您的示例中可能是1)，执行二进制搜索以在离散CDF数组中查找此随机数并获得与此条目对应的值--这是您的加权随机数。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1061643|entityMap^0|0^^$0|@$1|2|3|4|5|6|7|D|8|@]|9|@]|A|$]]|$1|B|3|-4|5|6|7|E|8|@]|9|@]|A|$]]]|C|$]]

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.

blocks|key|1061664|text|算法简单明了|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1061665|rand_no+=+rand(0,1)
for+each+element+in+array+
+++++if(rand_num+<+element.probablity)
++++++++++select+and+break
+++++rand_num+=+rand_num+-+element.probability|code-block|syntax|javascript|1061666|entityMap^0|0|0^^$0|@$1|2|3|4|5|6|7|I|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|J|8|@]|9|@]|A|$E|F]]|$1|G|3|-4|5|6|7|K|8|@]|9|@]|A|$]]]|H|$]]

The algorithm is straight forward

<pre><code>rand_no = rand(0,1)
for each element in array 
 if(rand_num &lt; element.probablity)
 select and break
 rand_num = rand_num - element.probability
</code></pre>

blocks|key|847367|text|ruby中的一个示例|type|unstyled|depth|inlineStyleRanges|entityRanges|data|847368|#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+{+%7Ce,w%7C+a[e]+=+acc%2B=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{+%7Ce,w%7C+w>r+}

p+selected[0]|code-block|syntax|javascript|847369|entityMap^0|0|0^^$0|@$1|2|3|4|5|6|7|I|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|J|8|@]|9|@]|A|$E|F]]|$1|G|3|-4|5|6|7|K|8|@]|9|@]|A|$]]]|H|$]]

An example in ruby

<pre><code>#each element is associated with its probability
a = {1 =&gt; 0.25 ,2 =&gt; 0.5 ,3 =&gt; 0.2, 4 =&gt; 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&gt;r }

p selected[0]
</code></pre>

blocks|key|847426|text|这可以在每个样本的O(1)预期时间内完成，如下所示。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|847427|计算每个元素i的CDF+F(i)是小于或等于i的概率之和。|847428|将元素i的范围r(i)定义为区间F(i+-+1)，F(i)。|847429|对于每个间隔(i+-+1)/n，i/n，创建一个存储桶，该存储桶由范围与间隔重叠的元素列表组成。只要您相当小心，整个数组总共需要O(n)个时间。|847430|当您随机采样数组时，只需计算随机数在哪个存储桶中，并与列表中的每个元素进行比较，直到找到包含它的间隔。|847431|样本的成本是O(随机选择列表的预期长度)+<=+2。|847432|entityMap^0|0|0|0|0|0|0^^$0|@$1|2|3|4|5|6|7|N|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|O|8|@]|9|@]|A|$]]|$1|D|3|E|5|6|7|P|8|@]|9|@]|A|$]]|$1|F|3|G|5|6|7|Q|8|@]|9|@]|A|$]]|$1|H|3|I|5|6|7|R|8|@]|9|@]|A|$]]|$1|J|3|K|5|6|7|S|8|@]|9|@]|A|$]]|$1|L|3|-4|5|6|7|T|8|@]|9|@]|A|$]]]|M|$]]

This can be done in O(1) expected time per sample as follows.

Compute the CDF F(i) for each element i to be the sum of probabilities less than or equal to i.

Define the range r(i) of an element i to be the interval [F(i - 1), F(i)].

For each interval [(i - 1)/n, i/n], create a bucket consisting of the list of the elements whose range overlaps the interval. This takes O(n) time in total for the full array as long as you are reasonably careful.

When you randomly sample the array, you simply compute which bucket the random number is in, and compare with each element of the list until you find the interval that contains it.

The cost of a sample is O(the expected length of a randomly chosen list) &lt;= 2.

blocks|key|847499|text|技巧可能是对具有反映概率的元素重复的辅助数组进行采样|type|unstyled|depth|inlineStyleRanges|entityRanges|data|847500|给定与其概率相关联的元素，以百分比表示：|847501|h+=+{1+=>+0.5,+2+=>+0.3,+3+=>+0.05,+4+=>+0.05+}

auxiliary_array+=+h.inject([]){%7Cmemo,(k,v)%7C+memo+%2B=+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|code-block|syntax|javascript|847502|如果您希望尽可能通用，则需要根据最大小数位数计算乘数，并在100的位置使用它：|847503|m+=+10**h.values.collect{%7Ce%7C+e.to_s.split(".").last.size+}.max|847504|entityMap^0|0|0|0|0|0^^$0|@$1|2|3|4|5|6|7|O|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|P|8|@]|9|@]|A|$]]|$1|D|3|E|5|F|7|Q|8|@]|9|@]|A|$G|H]]|$1|I|3|J|5|6|7|R|8|@]|9|@]|A|$]]|$1|K|3|L|5|F|7|S|8|@]|9|@]|A|$G|H]]|$1|M|3|-4|5|6|7|T|8|@]|9|@]|A|$]]]|N|$]]

the trick could be to sample an auxiliary array with elements repetitions which reflect the probability

Given the elements associated with their probability, as percentage:

<pre><code>h = {1 =&gt; 0.5, 2 =&gt; 0.3, 3 =&gt; 0.05, 4 =&gt; 0.05 }

auxiliary_array = h.inject([]){|memo,(k,v)| memo += Array.new((100*v).to_i,k) } 

ruby-1.9.3-p194 &gt; auxiliary_array 
 =&gt; [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
</code></pre>

if you want to be as generic as possible, you need to calculate the multiplier based on the max number of fractional digits, and use it in the place of 100:

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

blocks|key|1061878|text|我假设大于或等于0.8但小于1.0的数字选择第三个元素。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1061879|换句话说：|1061880|X是介于0和1之间的随机数|1061881|如果0.0+>=+x<+0.2+:第1项|1061882|如果0.2+>=+x<+0.8+:第2项|1061883|如果0.8+>=+x<+1.0+:第3项|1061884|entityMap^0|0|0|0|0|0|0^^$0|@$1|2|3|4|5|6|7|N|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|O|8|@]|9|@]|A|$]]|$1|D|3|E|5|6|7|P|8|@]|9|@]|A|$]]|$1|F|3|G|5|6|7|Q|8|@]|9|@]|A|$]]|$1|H|3|I|5|6|7|R|8|@]|9|@]|A|$]]|$1|J|3|K|5|6|7|S|8|@]|9|@]|A|$]]|$1|L|3|-4|5|6|7|T|8|@]|9|@]|A|$]]]|M|$]]

I would imagine that numbers greater or equal than 0.8 but less than 1.0 selects the third element.

In other terms:

x is a random number between 0 and 1

if 0.0 >= x &lt; 0.2 : Item 1

if 0.2 >= x &lt; 0.8 : Item 2

if 0.8 >= x &lt; 1.0 : Item 3

blocks|key|847585|text|下面是Ruby的一个实现：|type|unstyled|depth|inlineStyleRanges|entityRanges|data|847586|def+weighted_rand(weights+=+{})
++raise+'Probabilities+must+sum+up+to+1'+unless+weights.values.inject(&:%2B)+==+1.0
++raise+'Probabilities+must+not+be+negative'+unless+weights.values.all?+{+%7Cp%7C+p+>=+0+}
++#+Do+more+sanity+checks+depending+on+the+amount+of+trust+in+the+software+component+using+this+method,
++#+e.g.+don't+allow+duplicates,+don't+allow+non-numeric+values,+etc.
++
++#+Ignore+elements+with+probability+0
++weights+=+weights.reject+{+%7Ck,+v%7C+v+==+0.0+}+++#+e.g.+=>+{"a"=>0.4,+"b"=>0.4,+"c"=>0.2}

++#+Accumulate+probabilities+and+map+them+to+a+value
++u+=+0.0
++ranges+=+weights.map+{+%7Cv,+p%7C+[u+%2B=+p,+v]+}+++#+e.g.+=>+[[0.4,+"a"],+[0.8,+"b"],+[1.0,+"c"]]

++#+Generate+a+(pseudo-)random+floating+point+number+between+0.0(included)+and+1.0(excluded)
++u+=+rand+++#+e.g.+=>+0.4651073966724186
++
++#+Find+the+first+value+that+has+an+accumulated+probability+greater+than+the+random+number+u
++ranges.find+{+%7Cp,+v%7C+p+>+u+}.last+++#+e.g.+=>+"b"
end|code-block|syntax|javascript|847587|使用方法：|847588|weights+=+{'a'+=>+0.4,+'b'+=>+0.4,+'c'+=>+0.2,+'d'+=>+0.0}

weighted_rand+weights|847589|粗略估计会发生什么：|847590|sample+=+1000.times.map+{+weighted_rand+weights+}
sample.count('a')+#+396
sample.count('b')+#+406
sample.count('c')+#+198
sample.count('d')+#+0|847591|entityMap^0|0|0|0|0|0|0^^$0|@$1|2|3|4|5|6|7|Q|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|R|8|@]|9|@]|A|$E|F]]|$1|G|3|H|5|6|7|S|8|@]|9|@]|A|$]]|$1|I|3|J|5|D|7|T|8|@]|9|@]|A|$E|F]]|$1|K|3|L|5|6|7|U|8|@]|9|@]|A|$]]|$1|M|3|N|5|D|7|V|8|@]|9|@]|A|$E|F]]|$1|O|3|-4|5|6|7|W|8|@]|9|@]|A|$]]]|P|$]]

Here is an implementation in Ruby:
<pre class="lang-rb prettyprint-override"><code>def weighted_rand(weights = {})
 raise 'Probabilities must sum up to 1' unless weights.values.inject(&amp;:+) == 1.0
 raise 'Probabilities must not be negative' unless weights.values.all? { |p| p &gt;= 0 }
 # Do more sanity checks depending on the amount of trust in the software component using this method,
 # e.g. don't allow duplicates, don't allow non-numeric values, etc.
 
 # Ignore elements with probability 0
 weights = weights.reject { |k, v| v == 0.0 } # e.g. =&gt; {&quot;a&quot;=&gt;0.4, &quot;b&quot;=&gt;0.4, &quot;c&quot;=&gt;0.2}

 # Accumulate probabilities and map them to a value
 u = 0.0
 ranges = weights.map { |v, p| [u += p, v] } # e.g. =&gt; [[0.4, &quot;a&quot;], [0.8, &quot;b&quot;], [1.0, &quot;c&quot;]]

 # Generate a (pseudo-)random floating point number between 0.0(included) and 1.0(excluded)
 u = rand # e.g. =&gt; 0.4651073966724186
 
 # Find the first value that has an accumulated probability greater than the random number u
 ranges.find { |p, v| p &gt; u }.last # e.g. =&gt; &quot;b&quot;
end
</code></pre>
How to use:
<pre class="lang-rb prettyprint-override"><code>weights = {'a' =&gt; 0.4, 'b' =&gt; 0.4, 'c' =&gt; 0.2, 'd' =&gt; 0.0}

weighted_rand weights
</code></pre>
What to expect roughly:
<pre class="lang-rb prettyprint-override"><code>sample = 1000.times.map { weighted_rand weights }
sample.count('a') # 396
sample.count('b') # 406
sample.count('c') # 198
sample.count('d') # 0
</code></pre>

blocks|key|847626|text|使用pickup+gem的Ruby解决方案|type|unstyled|depth|inlineStyleRanges|entityRanges|offset|length|data|847627|require+'pickup'

chances+=+{0=>80,+1=>20}
picker+=+Pickup.new(chances)|code-block|syntax|javascript|847628|示例：|847629|5.times.collect+{
++picker.pick(5)
}|847630|给出输出：|847631|[[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]]|847632|entityMap|0|LINK|mutability|MUTABLE|url|https://github.com/fl00r/pickup^0|2|A|0|0|0|0|0|0|0^^$0|@$1|2|3|4|5|6|7|Y|8|@]|9|@$A|Z|B|10|1|11]]|C|$]]|$1|D|3|E|5|F|7|12|8|@]|9|@]|C|$G|H]]|$1|I|3|J|5|6|7|13|8|@]|9|@]|C|$]]|$1|K|3|L|5|F|7|14|8|@]|9|@]|C|$G|H]]|$1|M|3|N|5|6|7|15|8|@]|9|@]|C|$]]|$1|O|3|P|5|F|7|16|8|@]|9|@]|C|$G|H]]|$1|Q|3|-4|5|6|7|17|8|@]|9|@]|C|$]]]|R|$S|$5|T|U|V|C|$W|X]]]]

Ruby solution using the <a href="https://github.com/fl00r/pickup" rel="nofollow">pickup gem</a>:

<pre><code>require 'pickup'

chances = {0=&gt;80, 1=&gt;20}
picker = Pickup.new(chances)
</code></pre>

Example:

<pre><code>5.times.collect {
 picker.pick(5)
}
</code></pre>

gave output:

<pre><code>[[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]]
</code></pre>

blocks|key|1061987|text|这是我在生产环境中使用的PHP代码：|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1061988|/**
+*+@return+\App\Models\CdnServer
*/
protected+function+selectWeightedServer(Collection+$servers)
{
++++if+($servers->count()+==+1)+{
++++++++return+$servers->first();
++++}

++++$totalWeight+=+0;

++++foreach+($servers+as+$server)+{
++++++++$totalWeight+%2B=+$server->getWeight();
++++}

++++//+Select+a+random+server+using+weighted+choice
++++$randWeight+=+mt_rand(1,+$totalWeight);
++++$accWeight+=+0;

++++foreach+($servers+as+$server)+{
++++++++$accWeight+%2B=+$server->getWeight();

++++++++if+($accWeight+>=+$randWeight)+{
++++++++++++return+$server;
++++++++}
++++}
}|code-block|syntax|javascript|1061989|entityMap^0|0|0^^$0|@$1|2|3|4|5|6|7|I|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|J|8|@]|9|@]|A|$E|F]]|$1|G|3|-4|5|6|7|K|8|@]|9|@]|A|$]]]|H|$]]

This is a PHP code I used in production:

<pre><code>/**
 * @return \App\Models\CdnServer
*/
protected function selectWeightedServer(Collection $servers)
{
 if ($servers-&gt;count() == 1) {
 return $servers-&gt;first();
 }

 $totalWeight = 0;

 foreach ($servers as $server) {
 $totalWeight += $server-&gt;getWeight();
 }

 // Select a random server using weighted choice
 $randWeight = mt_rand(1, $totalWeight);
 $accWeight = 0;

 foreach ($servers as $server) {
 $accWeight += $server-&gt;getWeight();

 if ($accWeight &gt;= $randWeight) {
 return $server;
 }
 }
}
</code></pre>

blocks|key|847690|text|“财富之轮”O(n)，仅用于小数组：|type|unstyled|depth|inlineStyleRanges|entityRanges|data|847691|function+pickRandomWeighted(array,+weights)+{
++++var+sum+=+0;
++++for+(var+i=0;+i<weights.length;+i%2B%2B)+sum+%2B=+weights[i];
++++for+(var+i=0,+pick=Math.random()*sum;+i<weights.length;+i%2B%2B,+pick-=weights[i])
++++++++if+(pick-weights[i]<0)+return+array[i];
}|code-block|syntax|javascript|847692|entityMap^0|0|0^^$0|@$1|2|3|4|5|6|7|I|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|J|8|@]|9|@]|A|$E|F]]|$1|G|3|-4|5|6|7|K|8|@]|9|@]|A|$]]]|H|$]]

"Wheel of Fortune" O(n), use for small arrays only:

<pre><code>function pickRandomWeighted(array, weights) {
 var sum = 0;
 for (var i=0; i&lt;weights.length; i++) sum += weights[i];
 for (var i=0, pick=Math.random()*sum; i&lt;weights.length; i++, pick-=weights[i])
 if (pick-weights[i]&lt;0) return array[i];
}
</code></pre>

I would like to randomly select one element from an array, but each element has a known probability of selection.

All chances together (within the array) sums to 1.

What algorithm would you suggest as the fastest and most suitable for huge calculations?

Example:

<pre><code>id =&gt; chance
array[
 0 =&gt; 0.8
 1 =&gt; 0.2
]
</code></pre>

for this pseudocode, the algorithm in question should on multiple calls statistically return four elements on id <code>0</code> for one element on id <code>1</code>.

Weighted random selection from array

我想从数组中随机选择一个元素，但每个元素都有一个已知的选择概率。所有机会加在一起(在数组中)总和为1。你认为哪种算法是最快的，最适合进行大规模计算？示例：id => chancearray[    0 => 0.8    1 => 0.2]对于这个伪代码，所讨论的算法应该在多个调用上为id 0上的一个元素在id 1上统...

问从数组中加权随机选择
EN

社区

活动

资源

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问从数组中加权随机选择EN

社区

活动

资源

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问从数组中加权随机选择
EN