c++ - 加权随机数

Question

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

在我的项目(德州扑克手牌范围、主观全押权益分析)中，我使用 Boost 的随机函数。因此，假设我想选择 1 到 3 之间的随机数(即 1、2 或 3)。 Boost 的梅森扭曲生成器对此很有魅力。但是，我希望对选秀权进行加权，例如如下所示:

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

<小时/>

如果您的权重很少改变，但您经常随机选择一个，并且只要您的容器存储指向对象的指针或长度超过几十个项目(基本上，您必须进行分析才能知道这是否有帮助)或阻碍)，然后有一个优化:

通过存储每个项目的累积重量总和，您可以使用 binary search拾取与拾取重量相对应的元素。

<小时/>

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