[c++] 加权随机数



Answers

更新了对旧问题的回答。 你可以很容易地在C ++ 11中用std :: lib来做到这一点:

#include <iostream>
#include <random>
#include <iterator>
#include <ctime>
#include <type_traits>
#include <cassert>

int main()
{
    // Set up distribution
    double interval[] = {1,   2,   3,   4};
    double weights[] =  {  .90, .56, .04};
    std::piecewise_constant_distribution<> dist(std::begin(interval),
                                                std::end(interval),
                                                std::begin(weights));
    // Choose generator
    std::mt19937 gen(std::time(0));  // seed as wanted
    // Demonstrate with N randomly generated numbers
    const unsigned N = 1000000;
    // Collect number of times each random number is generated
    double avg[std::extent<decltype(weights)>::value] = {0};
    for (unsigned i = 0; i < N; ++i)
    {
        // Generate random number using gen, distributed according to dist
        unsigned r = static_cast<unsigned>(dist(gen));
        // Sanity check
        assert(interval[0] <= r && r <= *(std::end(interval)-2));
        // Save r for statistical test of distribution
        avg[r - 1]++;
    }
    // Compute averages for distribution
    for (double* i = std::begin(avg); i < std::end(avg); ++i)
        *i /= N;
    // Display distribution
    for (unsigned i = 1; i <= std::extent<decltype(avg)>::value; ++i)
        std::cout << "avg[" << i << "] = " << avg[i-1] << '\n';
}

在我的系统上输出:

avg[1] = 0.600115
avg[2] = 0.373341
avg[3] = 0.026544

请注意,上面的大部分代码都致力于显示和分析输出。 实际的一代只是几行代码。 输出结果表明已经获得了所请求的“概率”。 您必须将请求的输出除以1.5,因为这是请求总和。

Question

我试图实现一个加权的随机数。 我现在只是将我的头撞在墙上,无法弄清楚。

在我的项目(Hold'em hand-ranges,主观全面股权分析)中,我使用了Boost的随机函数。 所以,假设我想选择一个1到3之间的随机数(所以1,2或3)。 Boost的mersenne扭曲发生器就像是一个魅力。 不过,我希望这个选项权重如下所示:

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

Boost是否具有某种功能?




如果你的权重变化比他们绘制得慢,C ++ 11 discrete_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 runs
int N = 100000;
std::vector<int> samples(N);
for(auto & i: samples)
    i = dist(gen);
//do something with your samples...

但是请注意,c ++ 11 discrete_distribution计算初始化的所有累计和。 通常情况下,您需要这样做,因为它可以加快O(N)次成本的一次采样时间。 但是对于快速变化的分布来说,它会产生沉重的计算(和记忆)成本。 例如,如果权重表示有多少个项目,并且每次绘制一个项目时都删除它,那么您可能需要一个自定义算法。

Will的回答https://.com/a/1761646/837451避免了这种开销,但是比C ++ 11的绘制速度慢,因为它不能使用二分搜索。

要看到它这样做,你可以看到相关的行(我的Ubuntu 16.04 + GCC 5.3安装中的/usr/include/c++/5/bits/random.tcc ):

  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;
    }



在[0,1)上选择一个随机数,这应该是升压RNG的默认运算符()。 选择累积概率密度函数> =该数字的项目:

template <class It,class P>
It choose_p(It begin,It end,P const& p)
{
    if (begin==end) return end;
    double sum=0.;
    for (It i=begin;i!=end;++i)
        sum+=p(*i);
    double choice=sum*random01();
    for (It i=begin;;) {
        choice -= p(*i);
        It r=i;
        ++i;
        if (choice<0 || i==end) return r;
    }
    return begin; //unreachable
}

random01()返回double> = 0和<1。 请注意,以上不要求概率总和为1; 它会为你规范它们。

p只是为集合中的项目分配概率的函数[开始,结束]。 如果你只是有一系列概率,你可以忽略它(或使用一个标识)。




Related