加权随机数

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

Boost是否具有某种function？

1）计算所有权重的总和

2）select一个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");` `

` `#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` `

• 随机数的10％可以是1
• 随机数的30％可以是2
• 随机数的60％可以是3

` `weight = rand() % 10; switch( weight ) { case 0: randomNumber = 1; break; case 1: case 2: case 3: randomNumber = 2; break; case 4: case 5: case 6: case 7: case 8: case 9: randomNumber = 3; break; }` `

` `#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...` `

Will的回答https://stackoverflow.com/a/1761646/837451避免了这个开销，但是比C ++ 11更慢，因为它不能使用二进制search。

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

build立一个包（或std ::向量）的所有可以挑选的项目。

• 1 60％
• 2 35％
• 3 5％

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

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