加权随机数

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 sum_of_weight = 0;for(int i=0; i<num_choices; i++) {
   sum_of_weight += choice_weight[i];}int rnd = random(sum_of_weight);for(int i=0; i<num_choices; i++) {
  if(rnd < choice_weight[i])
    return i;
  rnd -= choice_weight[i];}assert(!"should never get here");

这应该是直接的，以适应您的Boost容器和诸如此类。

---

如果您的权重很少更改，但您经常随机选择一个，并且只要您的容器存储指向对象的指针，或者超过几十个项(基本上，您必须了解这是否有帮助或阻碍)，那么就会有一个优化：

通过在每个项目中存储累积权重和，可以使用二进制搜索选择与拾取重量相对应的项目。

---

如果您不知道列表中的项目数，那么有一个非常简洁的算法储层取样可以调整为加权。

Answer 2

如果你的重量变化比画的慢，C+11discrete_distribution将是最简单的：

#include <random>#include <vector>std::vector<double> weights{90,56,4};std::discrete_distribution<int> 
dist(std::begin(weights), std::end(weights));std::mt19937 gen;gen.seed(time(0));
//if you want different results from different runsint N = 100000;std::vector<int> samples(N);for(auto & i: samples)
    i = dist(gen);//do something with your 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安装上)：

  template<typename _IntType>
    void
    discrete_distribution<_IntType>::param_type::
    _M_initialize()
    {
      if (_M_prob.size() < 2)
        {
          _M_prob.clear();
          return;
        }

      const double __sum = std::accumulate(_M_prob.begin(),
                                           _M_prob.end(), 0.0);
      // Now normalize the probabilites.
      __detail::__normalize(_M_prob.begin(), _M_prob.end(), _M_prob.begin(),
                            __sum);
      // Accumulate partial sums.
      _M_cp.reserve(_M_prob.size());
      std::partial_sum(_M_prob.begin(), _M_prob.end(),
                       std::back_inserter(_M_cp));
      // Make sure the last cumulative probability is one.
      _M_cp[_M_cp.size() - 1] = 1.0;
    }