加权随机数

Question

我正在尝试实现加权随机数。我目前只是把头撞在墙上，无法弄清楚。

在我的项目（Hold’em hand-ranges，主观全押权益分析）中，我使用了 Boost 的随机函数。所以，假设我想在 1 和 3 之间选择一个随机数（所以是 1、2 或 3）。 Boost 的 mersenne twister 发生器对此很有魅力。但是，我希望选择权重，例如：

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

Boost 是否为此提供了某种功能？

原文由 nhaa123 发布，翻译遵循 CC BY-SA 4.0 许可协议

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 容器等。

---

如果您的权重很少更改，但您经常随机选择一个，并且只要您的容器存储指向对象的指针或长度超过几十个项目（基本上，您必须分析以了解这是否有帮助或阻碍） ，然后有一个优化：

通过将累积权重和存储在每个项目中，您可以使用 二分搜索 来选择与选择权重相对应的项目。

---

如果您不知道列表中的项目数，那么有一种非常简洁的算法，称为 水库采样，可以适应加权。

原文由 Will 发布，翻译遵循 CC BY-SA 3.0 许可协议

Answer 2

我刚刚通过“ will ”实现了给定的解决方案

#include <iostream>
#include <map>

using namespace std;

template < class T >
class WeightedRandomSample
{
public:
    void SetWeigthMap( map< T , unsigned int >& WeightMap )
    {
        m_pMap = &WeightMap;
    }

    T GetRandomSample()
    {
        unsigned int sum_of_weight = GetSumOfWeights();
        unsigned int rnd = (rand() % sum_of_weight);
        map<T , unsigned int>& w_map = *m_pMap;
        typename map<T , unsigned int>::iterator it;
        for(it = w_map.begin() ; it != w_map.end() ; ++it )
        {
            unsigned int w = it->second;
            if(rnd < w)
                return (it->first);
            rnd -= w;
        }
        //assert(!"should never get here");
        T* t = NULL;
        return *(t);
    }

    unsigned int GetSumOfWeights()
    {
        if(m_pMap == NULL)
            return 0;
        unsigned int sum = 0;
        map<T , unsigned int>& w_map = *m_pMap;
        typename map<T , unsigned int>::iterator it;

        for(it = w_map.begin() ; it != w_map.end() ; ++it )
        {
            sum += it->second;
        }
        return sum;
    }


protected:
    map< T , unsigned int>* m_pMap = NULL;

};

typedef pair<int , int> PAIR_INT_INT;
typedef map<PAIR_INT_INT ,unsigned int> mul_table_weighted_map;

int main()
{

    mul_table_weighted_map m;
    m[PAIR_INT_INT(2,3)] = 10;
    m[PAIR_INT_INT(4,5)] = 20;
    m[PAIR_INT_INT(2,5)] = 10;

    WeightedRandomSample<PAIR_INT_INT> WRS;
    WRS.SetWeigthMap(m);
    unsigned int sum_of_weight = WRS.GetSumOfWeights();
    cout <<"Sum of weights : " << sum_of_weight << endl;

    unsigned int number_of_test = 10000;
    cout << "testing " << number_of_test << " ..." << endl;
    map<PAIR_INT_INT , unsigned int> check_map;
    for(int i = 0 ; i < number_of_test ; i++)
    {
        PAIR_INT_INT res = WRS.GetRandomSample();
        check_map[res]++;
        //cout << i+1 << ": random = " << res.first << " * " << res.second << endl;
    }
    cout << "results: " << endl;

    for(auto t : check_map)
    {
        PAIR_INT_INT p = t.first;
        unsigned int expected = (number_of_test * m[p]) / sum_of_weight;
        cout << " pair " << p.first << " * " << p.second
            << ", counted = " << t.second
            << ", expected = " << expected
            << endl;
    }

    return 0;
}

原文由 mohtashami740 发布，翻译遵循 CC BY-SA 4.0 许可协议