c++ - 带更新的加权随机数生成器

Question

我的问题是这个问题的延伸:Weighted random numbers

I'm trying to implement a weighted random numbers. I'm currently justbanging my head against the wall and cannot figure this out.

In my project (Hold'em hand-ranges, subjective all-in equityanalysis), I'm using Boost's random -functions. So, let's say I wantto pick a random number between 1 and 3 (so either 1, 2 or 3). Boost'smersenne twister generator works like a charm for this. However, Iwant the pick to be weighted for example like this:

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

Does Boost have some sort of functionality for this?

扩展:允许用户动态更改给定 key 的权重。

如何最优地解决问题？

天真的解决方案可能是扫描所有元素，根据新权重调整所有元素的权重...但这是更新的 O(n)。这是非常低效的。我们如何做得更好？

我希望 update(key, w) 和 get() 优于或等于 O(logn)

Answer 1

一种可能的解决方案来自算术编码和Fenwick trees .

如果你有一个非负数列表，[a_0, ... a_n]类型 T , Fenwick 树数据结构允许您在 O(log n) 中实现以下两个功能时间:

1. Index upper_bound(T p) : 对于给定值 p , 计算最小指数 i ，使得前缀和 a_0 + ... + a_i > p .
2. set(Index i, T p) : 更新a_i <- p .

生成随机数的算法i很简单:生成一个随机数 k在 [0, sum a_i) 范围内均匀分布然后使用 i = upper_bound(k)寻找i .

简单的例子:

i            0 1 2 3 4 5 6 7
a_i          0 1 0 0 3 4 0 2
prefix_sum   0 1 1 1 4 8 8 10

k                   0 1 2 3 4 5 6 7 8 9
i = upper_bound(k)  1 4 4 4 5 5 5 5 7 7

P.Fenwick. A New Data Structure for Cumulative Frequency Tables (PDF, 1994)

My C++ implementation of a Fenwick tree (未经彻底测试)