c++ - 根据给定的概率分布从集合中提取值

Question

我必须解决这个问题:

vector<int> myset={1,2,3,4};
vector<double> distribution ={0.01,0.1,0.3,0.59};

我必须根据给定的分布从myset 中选择一些值。实际上 distribution 和 myset 并不是固定的。它们具有相同的维度，但是这个维度可以变化并且也非常大。我可以统一提取 [0 100] 范围内的数字，然后这样做:

int extracted_numb;
int numb = rand(0,100);
if(numb<1)
  extracted_numb=myset[0];
else if(numb<11)
  extracted_numb=myset[1];
else if(numb<41)
  extracted_numb=myset[2];
else
  extracted_numb=myset[3];

但我再说一遍，在真实情况下我不知道 distribution 和 myset 的维度(因为是用户参数)因此我不知道有多少 if 要做。

我问这个问题是否有一个好的算法，也许一些 C++ 或 Boost 的本地库已经完成了它

(我使用的是 Boost 1.63 和 C++11)

Answer 1

对于 C++11，使用 random::discrete_distribution在 myset 中选择一个索引。 (Boost 具有类似的功能。)

示例(改编自 cppreference 链接):

#include <iostream>
#include <map>
#include <random>
#include <vector>

int main()
{
    std::vector<int> myset = {10,22,35,47};
    std::vector<double> distribution = {0.01,0.1,0.3,0.59};
    std::random_device rd;
    std::mt19937 gen(rd());
    std::discrete_distribution<> d(distribution.begin(), distribution.end());
    std::map<int, int> m;
    for(int n=0; n<10000; ++n) {
        ++m[myset[d(gen)]];
    }
    for(auto p : m) {
        std::cout << p.first << " generated " << p.second << " times\n";
    }
}

( Live on coliru )