blocks|key|1516660|text|如果数组很小，我会给数组一个长度，在本例中为5，并根据需要赋值：|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1516661|array[
++++0+=>+0
++++1+=>+0
++++2+=>+0
++++3+=>+0
++++4+=>+1
]|code-block|syntax|javascript|1516662|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|1516688|text|计算列表的离散累积密度函数(CDF)+--或者简单地说，就是权重的累积和数组。然后在0和所有权重的总和之间生成一个随机数(在您的示例中可能是1)，执行二进制搜索以在离散CDF数组中查找此随机数并获得与此条目对应的值--这是您的加权随机数。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1516689|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|3993741|text|算法简单明了|type|unstyled|depth|inlineStyleRanges|entityRanges|data|3993742|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|3993743|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|329964|text|ruby中的一个示例|type|unstyled|depth|inlineStyleRanges|entityRanges|data|329965|#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|329966|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|2398028|text|这可以在每个样本的O(1)预期时间内完成，如下所示。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|2398029|计算每个元素i的CDF+F(i)是小于或等于i的概率之和。|2398030|将元素i的范围r(i)定义为区间F(i+-+1)，F(i)。|2398031|对于每个间隔(i+-+1)/n，i/n，创建一个存储桶，该存储桶由范围与间隔重叠的元素列表组成。只要您相当小心，整个数组总共需要O(n)个时间。|2398032|当您随机采样数组时，只需计算随机数在哪个存储桶中，并与列表中的每个元素进行比较，直到找到包含它的间隔。|2398033|样本的成本是O(随机选择列表的预期长度)+<=+2。|2398034|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|1516767|text|技巧可能是对具有反映概率的元素重复的辅助数组进行采样|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1516768|给定与其概率相关联的元素，以百分比表示：|1516769|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|1516770|如果您希望尽可能通用，则需要根据最大小数位数计算乘数，并在100的位置使用它：|1516771|m+=+10**h.values.collect{%7Ce%7C+e.to_s.split(".").last.size+}.max|1516772|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|1516787|text|我假设大于或等于0.8但小于1.0的数字选择第三个元素。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1516788|换句话说：|1516789|X是介于0和1之间的随机数|1516790|如果0.0+>=+x<+0.2+:第1项|1516791|如果0.2+>=+x<+0.8+:第2项|1516792|如果0.8+>=+x<+1.0+:第3项|1516793|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|1516801|text|下面是Ruby的一个实现：|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1516802|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|1516803|使用方法：|1516804|weights+=+{'a'+=>+0.4,+'b'+=>+0.4,+'c'+=>+0.2,+'d'+=>+0.0}

weighted_rand+weights|1516805|粗略估计会发生什么：|1516806|sample+=+1000.times.map+{+weighted_rand+weights+}
sample.count('a')+#+396
sample.count('b')+#+406
sample.count('c')+#+198
sample.count('d')+#+0|1516807|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|2398174|text|使用pickup+gem的Ruby解决方案|type|unstyled|depth|inlineStyleRanges|entityRanges|offset|length|data|2398175|require+'pickup'

chances+=+{0=>80,+1=>20}
picker+=+Pickup.new(chances)|code-block|syntax|javascript|2398176|示例：|2398177|5.times.collect+{
++picker.pick(5)
}|2398178|给出输出：|2398179|[[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]]|2398180|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|1516838|text|我将改进https://stackoverflow.com/users/626341/masciugo+answer。|type|unstyled|depth|inlineStyleRanges|entityRanges|offset|length|data|1516839|基本上，你可以做一个很大的数组，其中元素出现的次数与权重成比例。|1516840|它有一些缺点。|1516841|1516842|权重可能不是整数。假设元素1的概率为pi，元素2的概率为1-pi。你是如何划分的？或者想象一下，如果有成百上千个这样的元素，|ordered-list-item|1516843|创建的数组可能非常大。想象一下，如果最小公共乘数是100,000，那么我们将需要一个包含100,000个元素的数组，该数组是我们要挑选的。|1516844|1516845|为了应对这种情况，你可以这样做。|1516846|创建这样的数组，但只随机插入一个元素。元素被插入的概率与权重成正比。|1516847|然后从通常的随机元素中选择。|1516848|因此，如果有3个具有不同权重的元素，您只需从1-3个元素的数组中选择一个元素。|1516849|如果构造的元素为空，则可能会出现问题。也就是说，由于元素掷骰子的方式不同，所以在数组中没有元素出现。|1516850|在这种情况下，我建议元素被插入的概率是p(插入的)=wi/wmax。|1516851|这样，将插入一个元素，即具有最高概率的元素。其他元素将按相对概率插入。|1516852|假设我们有两个对象。|1516853|元素1显示了当时的.20%25。元素2显示了时间的.40%25，并且具有最高的概率。|1516854|在数组中，元素2将一直出现。元素1将在一半的时间内显示。|1516855|因此，元素2将被称为元素1的2倍。为了通用性，所有其他元素将被称为与它们的权重成比例。而且，它们的所有概率之和都是1，因为数组始终至少有1个元素。|1516856|entityMap|0|LINK|mutability|MUTABLE|url|https://stackoverflow.com/users/626341/masciugo^0|4|1B|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0^^$0|@$1|2|3|4|5|6|7|1I|8|@]|9|@$A|1J|B|1K|1|1L]]|C|$]]|$1|D|3|E|5|6|7|1M|8|@]|9|@]|C|$]]|$1|F|3|G|5|6|7|1N|8|@]|9|@]|C|$]]|$1|H|3|-4|5|6|7|1O|8|@]|9|@]|C|$]]|$1|I|3|J|5|K|7|1P|8|@]|9|@]|C|$]]|$1|L|3|M|5|K|7|1Q|8|@]|9|@]|C|$]]|$1|N|3|-4|5|6|7|1R|8|@]|9|@]|C|$]]|$1|O|3|P|5|6|7|1S|8|@]|9|@]|C|$]]|$1|Q|3|R|5|6|7|1T|8|@]|9|@]|C|$]]|$1|S|3|T|5|6|7|1U|8|@]|9|@]|C|$]]|$1|U|3|V|5|6|7|1V|8|@]|9|@]|C|$]]|$1|W|3|X|5|6|7|1W|8|@]|9|@]|C|$]]|$1|Y|3|Z|5|6|7|1X|8|@]|9|@]|C|$]]|$1|10|3|11|5|6|7|1Y|8|@]|9|@]|C|$]]|$1|12|3|13|5|6|7|1Z|8|@]|9|@]|C|$]]|$1|14|3|15|5|6|7|20|8|@]|9|@]|C|$]]|$1|16|3|17|5|6|7|21|8|@]|9|@]|C|$]]|$1|18|3|19|5|6|7|22|8|@]|9|@]|C|$]]|$1|1A|3|-4|5|6|7|23|8|@]|9|@]|C|$]]]|1B|$1C|$5|1D|1E|1F|C|$1G|1H]]]]

I am going to improve on <a href="https://stackoverflow.com/users/626341/masciugo">https://stackoverflow.com/users/626341/masciugo</a> answer.

Basically you make one big array where the number of times an element shows up is proportional to the weight.

It has some drawbacks.

<ol>
<li>The weight might not be integer. Imagine element 1 has probability of pi and element 2 has probability of 1-pi. How do you divide that? Or imagine if there are hundreds of such elements.</li>
<li>The array created can be very big. Imagine if least common multiplier is 1 million, then we will need an array of 1 million element in the array we want to pick.</li>
</ol>

To counter that, this is what you do.

Create such array, but only insert an element randomly. The probability that an element is inserted is proportional the the weight.

Then select random element from usual.

So if there are 3 elements with various weight, you simply pick an element from an array of 1-3 elements.

Problems may arise if the constructed element is empty. That is it just happens that no elements show up in the array because their dice roll differently.

In which case, I propose that the probability an element is inserted is p(inserted)=wi/wmax.

That way, one element, namely the one that has the highest probability, will be inserted. The other elements will be inserted by the relative probability.

Say we have 2 objects.

element 1 shows up .20% of the time.
element 2 shows up .40% of the time and has the highest probability.

In thearray, element 2 will show up all the time. Element 1 will show up half the time.

So element 2 will be called 2 times as many as element 1. For generality all other elements will be called proportional to their weight. Also the sum of all their probability are 1 because the array will always have at least 1 element.

blocks|key|2398234|text|这是我在生产环境中使用的PHP代码：|type|unstyled|depth|inlineStyleRanges|entityRanges|data|2398235|/**
+*+@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|2398236|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|3994069|text|“财富之轮”O(n)，仅用于小数组：|type|unstyled|depth|inlineStyleRanges|entityRanges|data|3994070|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|3994071|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>

blocks|key|330330|text|另一种可能性是将从exponential+distribution中提取的随机数与该元素的权重所给出的参数相关联，与数组的每个元素相关联。然后选择具有最低“排序编号”的元素。在这种情况下，特定元素具有阵列的最低排序编号的概率与阵列元素的权重成正比。|type|unstyled|depth|inlineStyleRanges|entityRanges|offset|length|data|330331|这是O(n)，不涉及任何重新排序或额外的存储，并且选择可以在数组的一次遍历过程中完成。权重必须大于零，但不必与任何特定值相加。|330332|这还有一个进一步的优点，如果您将排序编号与每个数组元素一起存储，您可以选择通过增加排序编号来对数组进行排序，以获得具有较高权重的元素提前到达的概率较高的数组的随机排序(我发现这在决定选择哪个DNS+SRV记录、决定查询哪台计算机时很有用)。|330333|有替换的重复随机采样每次都需要通过数组进行一次新的遍历；对于没有替换的随机选择，可以按序号递增的顺序对数组进行排序，并按此顺序读出k个元素。|330334|参见对数(特别是关于这种变量集合的最小值分布的注释)，以证明上述情况是正确的，并指向生成此类变量的技术:如果T在[0,1)中具有均匀的随机分布，则Z=-+Wikipedia+page+about+the+exponential+distribution+(1-T)/w(其中w是分布的参数；这里是相关元素的权重)具有指数分布。|330335|这就是：|330336|对于数组中的每个元素i，计算zi+=+-log(T)/wi+(或zi+=+-log(1-T)/wi)，其中T是从[0,1)中的均匀分布中提取的，wi是第i个元素的权重，该元素具有最低的zi。|330337|元素i将以概率wi/(w1%2Bw2%2B...%2Bwn)被选择。|330338|请参见下面的Python中的示例，该Python对10000次试验中的每一次都进行一次通过权重数组的操作。|330339|import+math,+random

random.seed()

weights+=+[10,+20,+50,+20]
nw+=+len(weights)
results+=+[0+for+i+in+range(nw)]

n+=+10000
while+n+>+0:+#+do+n+trials
++++smallest_i+=+0
++++smallest_z+=+-math.log(1-random.random())/weights[0]
++++for+i+in+range(1,+nw):
++++++++z+=+-math.log(1-random.random())/weights[i]
++++++++if+z+<+smallest_z:
++++++++++++smallest_i+=+i
++++++++++++smallest_z+=+z

++++results[smallest_i]+%2B=+1+#+accumulate+our+choices

++++n+-=+1

for+i+in+range(nw):
++++print("{}+->+{}".format(weights[i],+results[i]))|code-block|syntax|javascript|330340|330341|编辑(历史)：在发布了这篇文章后，我确信我不可能是第一个想到它的人，另一个考虑到这个解决方案的搜索显示确实是这样的。|style|BOLD|330342|330343|在一篇answer+to+a+similar+question中，Joe+K提出了这个算法(同时也指出，其他人肯定已经想到了它，同时，他指出了Efraimidis+and+Spirakis+(preprint)，它描述了一种类似的方法。|unordered-list-item|330344|我非常确定，看着它，Efraimidis和Spirakis实际上是相同的指数分布算法，这一点得到了Wikipedia+page+about+Reservoir+sampling中的一句话的证实，即“相当地，该算法的一个更稳定的公式”是上面的指数分布算法。这里提到的是a+sequence+of+lecture+notes+by+Richard+Arratia；指数分布的相关性质在1.3节中提到(它提到类似的东西在某些圈子里是一个“熟悉的事实”)，但不是它与Efraimidis和|330345|算法的关系。|330346|entityMap|0|LINK|mutability|MUTABLE|url|https://en.wikipedia.org/wiki/Exponential_distribution|1|2|https://stackoverflow.com/a/30226926/375147|3|https://stackoverflow.com/users/854793/joe-k|4|https://doi.org/10.1016/j.ipl.2005.11.003|5|https://docdro.id/XTglD09|6|https://en.wikipedia.org/wiki/Reservoir_sampling|7|https://arxiv.org/abs/1305.0941^0|9|O|0|0|0|0|0|25|1D|1|0|0|0|0|0|0|0|0|7|0|0|3|S|2|X|5|3|1Z|N|4|2O|8|5|0|1D|13|6|3P|1A|7|0|0^^$0|@$1|2|3|4|5|6|7|1W|8|@]|9|@$A|1X|B|1Y|1|1Z]]|C|$]]|$1|D|3|E|5|6|7|20|8|@]|9|@]|C|$]]|$1|F|3|G|5|6|7|21|8|@]|9|@]|C|$]]|$1|H|3|I|5|6|7|22|8|@]|9|@]|C|$]]|$1|J|3|K|5|6|7|23|8|@]|9|@$A|24|B|25|1|26]]|C|$]]|$1|L|3|M|5|6|7|27|8|@]|9|@]|C|$]]|$1|N|3|O|5|6|7|28|8|@]|9|@]|C|$]]|$1|P|3|Q|5|6|7|29|8|@]|9|@]|C|$]]|$1|R|3|S|5|6|7|2A|8|@]|9|@]|C|$]]|$1|T|3|U|5|V|7|2B|8|@]|9|@]|C|$W|X]]|$1|Y|3|-4|5|6|7|2C|8|@]|9|@]|C|$]]|$1|Z|3|10|5|6|7|2D|8|@$A|2E|B|2F|11|12]]|9|@]|C|$]]|$1|13|3|-4|5|6|7|2G|8|@]|9|@]|C|$]]|$1|14|3|15|5|16|7|2H|8|@]|9|@$A|2I|B|2J|1|2K]|$A|2L|B|2M|1|2N]|$A|2O|B|2P|1|2Q]|$A|2R|B|2S|1|2T]]|C|$]]|$1|17|3|18|5|16|7|2U|8|@]|9|@$A|2V|B|2W|1|2X]|$A|2Y|B|2Z|1|30]]|C|$]]|$1|19|3|1A|5|6|7|31|8|@]|9|@]|C|$]]|$1|1B|3|-4|5|6|7|32|8|@]|9|@]|C|$]]]|1C|$1D|$5|1E|1F|1G|C|$1H|1I]]|1J|$5|1E|1F|1G|C|$1H|1I]]|1K|$5|1E|1F|1G|C|$1H|1L]]|1M|$5|1E|1F|1G|C|$1H|1N]]|1O|$5|1E|1F|1G|C|$1H|1P]]|1Q|$5|1E|1F|1G|C|$1H|1R]]|1S|$5|1E|1F|1G|C|$1H|1T]]|1U|$5|1E|1F|1G|C|$1H|1V]]]]

Another possibility is to associate, with each element of the array, a random number drawn from an <a href="https://en.wikipedia.org/wiki/Exponential_distribution" rel="nofollow noreferrer">exponential distribution</a> with parameter given by the weight for that element. Then pick the element with the lowest such ‘ordering number’. In this case, the probability that a particular element has the lowest ordering number of the array is proportional to the array element's weight.
This is O(n), doesn't involve any reordering or extra storage, and the selection can be done in the course of a single pass through the array. The weights must be greater than zero, but don't have to sum to any particular value.
This has the further advantage that, if you store the ordering number with each array element, you have the option to sort the array by increasing ordering number, to get a random ordering of the array in which elements with higher weights have a higher probability of coming early (I've found this useful when deciding which DNS SRV record to pick, to decide which machine to query).
Repeated random sampling with replacement requires a new pass through the array each time; for random selection without replacement, the array can be sorted in order of increasing ordering number, and k elements can be read out in that order.
See the <a href="https://en.wikipedia.org/wiki/Exponential_distribution" rel="nofollow noreferrer">Wikipedia page about the exponential distribution</a> (in particular the remarks about the distribution of the minima of an ensemble of such variates) for the proof that the above is true, and also for the pointer towards the technique of generating such variates: if T has a uniform random distribution in [0,1), then Z=-log(1-T)/w (where w is the parameter of the distribution; here the weight of the associated element) has an exponential distribution.
That is:
<ol>
<li>For each element i in the array, calculate zi = -log(T)/wi (or zi = -log(1-T)/wi), where T is drawn from a uniform distribution in [0,1), and wi is the weight of the I'th element.</li>
<li>Select the element which has the lowest zi.</li>
</ol>
The element i will be selected with probability wi/(w1+w2+...+wn).
See below for an illustration of this in Python, which takes a single pass through the array of weights, for each of 10000 trials.
<pre><code>import math, random

random.seed()

weights = [10, 20, 50, 20]
nw = len(weights)
results = [0 for i in range(nw)]

n = 10000
while n &gt; 0: # do n trials
 smallest_i = 0
 smallest_z = -math.log(1-random.random())/weights[0]
 for i in range(1, nw):
 z = -math.log(1-random.random())/weights[i]
 if z &lt; smallest_z:
 smallest_i = i
 smallest_z = z

 results[smallest_i] += 1 # accumulate our choices

 n -= 1

for i in range(nw):
 print(&quot;{} -&gt; {}&quot;.format(weights[i], results[i]))
</code></pre>
<hr />
Edit (for history): after posting this, I felt sure I couldn't be the first to have thought of it, and another search with this solution in mind shows that this is indeed the case.
<ul>
<li>In an <a href="https://stackoverflow.com/a/30226926/375147">answer to a similar question</a>, <a href="https://stackoverflow.com/users/854793/joe-k">Joe K</a> suggested this algorithm (and also noted that someone else must have thought of it before).</li>
<li>Another <a href="https://stackoverflow.com/a/20548895/375147">answer to that question</a>, meanwhile, pointed to <a href="https://doi.org/10.1016/j.ipl.2005.11.003" rel="nofollow noreferrer">Efraimidis and Spirakis</a> (<a href="https://docdro.id/XTglD09" rel="nofollow noreferrer">preprint</a>), which describes a similar method.</li>
<li>I'm pretty sure, looking at it, that the Efraimidis and Spirakis is in fact the same exponential-distribution algorithm in disguise, and this is corroborated by a passing remark in the <a href="https://en.wikipedia.org/wiki/Reservoir_sampling" rel="nofollow noreferrer">Wikipedia page about Reservoir sampling</a> that ‘[e]quivalently, a more numerically stable formulation of this algorithm’ is the exponential-distribution algorithm above. The reference there is to <a href="https://arxiv.org/abs/1305.0941" rel="nofollow noreferrer">a sequence of lecture notes by Richard Arratia</a>; the relevant property of the exponential distribution is mentioned in Sect.1.3 (which mentions that something similar to this is a ‘familiar fact’ in some circles), but not its relationship to the Efraimidis and Spirakis algorithm.</li>
</ul>

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

翻译质量差，导致语言生硬或混乱。

没有提供实际的解决方法或示例。

解答不清晰，无法理解或解决问题。

页面排版不美观，阅读体验差。

文章

问答

视频

学习中心

腾讯云实验室

直播

竞赛

腾讯云代码分析专区

腾讯iOA零信任安全管理系统专区

腾讯云架构师技术同盟交流圈

腾讯云数据库专区

腾讯云顾问专区

腾讯云原生专区

腾讯混元专区

腾讯云TCE专区

腾讯云Lighthouse专区

腾讯云HAI专区

腾讯云Edgeone专区

腾讯云存储专区

腾讯云智能专区

腾讯轻联专区 

腾讯云开发专区

TAPD专区

腾讯轻量云游戏服专区

腾讯云最具价值专家

腾讯云架构师技术同盟

腾讯云创作之星

腾讯云开发者先锋

腾讯云代码助手

云原生构建

TAPD 敏捷项目管理

Cloud Studio

SDK中心

API中心

命令行工具

涵盖代码开发、场景应用、自动测试全流程，助你从零构建专属AI助手

一站式MCP教程库，解锁AI应用新玩法

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

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

Stack Overflow用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

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