加权随机数

Question

加权随机数

我在尝试实现一个加权随机数。我现在只是把头撞在墙上，弄不明白。

在我的项目中，我使用的是Boost的随机函数(保持手范围，主观的全股权分析)。那么，假设我想选择一个介于1到3之间的随机数(所以要么是1，2，要么是3)。Boost的Mersenne旋风发生器工作起来就像一种魅力。但是，我希望对这个选项进行加权，例如：

1 (weight: 90)
2 (weight: 56)
3 (weight:  4)

Boost有某种功能吗？

Answer 1

有一个简单的算法可以随机挑选一个项目，其中项目有单独的权重：1)计算所有权重之和。2)选择一个0或更大且小于权重之和的随机数。3)一次只检查一项，从你的随机数中减去它们的权重，直到得到随机数小于该项目重量的项目为止伪代码说明了这一点：int&nbsp;sum_of_weight&nbsp;=&nbsp;0;for(int&nbsp;i=0;&nbsp;i<num_choices;&nbsp;i++)&nbsp;{ &nbsp;&nbsp;&nbsp;sum_of_weight&nbsp;+=&nbsp;choice_weight[i];}int&nbsp;rnd&nbsp;=&nbsp;random(sum_of_weight);for(int&nbsp;i=0;&nbsp;i<num_choices;&nbsp;i++)&nbsp;{ &nbsp;&nbsp;if(rnd&nbsp;<&nbsp;choice_weight[i]) &nbsp;&nbsp;&nbsp;&nbsp;return&nbsp;i; &nbsp;&nbsp;rnd&nbsp;-=&nbsp;choice_weight[i];}assert(!"should&nbsp;never&nbsp;get&nbsp;here");这应该是直接的，以适应您的Boost容器和诸如此类。如果您的权重很少更改，但您经常随机选择一个，并且只要您的容器存储指向对象的指针，或者超过几十个项(基本上，您必须了解这是否有帮助或阻碍)，那么就会有一个优化：通过在每个项目中存储累积权重和，可以使用二进制搜索选择与拾取重量相对应的项目。如果您不知道列表中的项目数，那么有一个非常简洁的算法储层取样可以调整为加权。

Answer 2

如果你的重量变化比画的慢，C+11discrete_distribution将是最简单的：#include&nbsp;<random>#include&nbsp;<vector>std::vector<double>&nbsp;weights{90,56,4};std::discrete_distribution<int>&nbsp; dist(std::begin(weights),&nbsp;std::end(weights));std::mt19937&nbsp;gen;gen.seed(time(0)); //if&nbsp;you&nbsp;want&nbsp;different&nbsp;results&nbsp;from&nbsp;different&nbsp;runsint&nbsp;N&nbsp;=&nbsp;100000;std::vector<int>&nbsp;samples(N);for(auto&nbsp;&&nbsp;i:&nbsp;samples) &nbsp;&nbsp;&nbsp;&nbsp;i&nbsp;=&nbsp;dist(gen);//do&nbsp;something&nbsp;with&nbsp;your&nbsp;samples...但是，请注意，c+11discrete_distribution计算初始化时的所有累积和。通常，您需要这样做，因为它加快了采样时间的一次O(N)成本。但是，对于快速变化的分布，它将招致沉重的计算(和内存)成本。例如，如果权重表示有多少项，并且每次绘制一个项时，您都会删除它，您可能需要一个自定义算法。威尔的回答https://stackoverflow.com/a/1761646/837451避免了这种开销，但是比C+11更慢，因为它不能使用二进制搜索。要看到它这样做，您可以看到相关的行(/usr/include/c++/5/bits/random.tcc在我的Ubuntu 16.04+GCC 5.3安装上)：&nbsp;&nbsp;template<typename&nbsp;_IntType> &nbsp;&nbsp;&nbsp;&nbsp;void &nbsp;&nbsp;&nbsp;&nbsp;discrete_distribution<_IntType>::param_type:: &nbsp;&nbsp;&nbsp;&nbsp;_M_initialize() &nbsp;&nbsp;&nbsp;&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if&nbsp;(_M_prob.size()&nbsp;<&nbsp;2) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;_M_prob.clear(); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;return; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;const&nbsp;double&nbsp;__sum&nbsp;=&nbsp;std::accumulate(_M_prob.begin(), &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;_M_prob.end(),&nbsp;0.0); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;//&nbsp;Now&nbsp;normalize&nbsp;the&nbsp;probabilites. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;__detail::__normalize(_M_prob.begin(),&nbsp;_M_prob.end(),&nbsp;_M_prob.begin(), &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;__sum); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;//&nbsp;Accumulate&nbsp;partial&nbsp;sums. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;_M_cp.reserve(_M_prob.size()); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;std::partial_sum(_M_prob.begin(),&nbsp;_M_prob.end(), &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;std::back_inserter(_M_cp)); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;//&nbsp;Make&nbsp;sure&nbsp;the&nbsp;last&nbsp;cumulative&nbsp;probability&nbsp;is&nbsp;one. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;_M_cp[_M_cp.size()&nbsp;-&nbsp;1]&nbsp;=&nbsp;1.0; &nbsp;&nbsp;&nbsp;&nbsp;}