c - 加权随机整数

Question

我想为随机生成的数字分配权重，权重如下所示。

  0  |  1  |  2  |  3  |  4  |  5  |  6
─────────────────────────────────────────
  X  |  X  |  X  |  X  |  X  |  X  |  X
  X  |  X  |  X  |  X  |  X  |  X  |   
  X  |  X  |  X  |  X  |  X  |     |   
  X  |  X  |  X  |  X  |     |     |   
  X  |  X  |  X  |     |     |     |   
  X  |  X  |     |     |     |     |   
  X  |     |     |     |     |     |   

最有效的方法是什么？

Answer 1

@Kerrek 的回答很好。

但是如果权重的直方图不是全是小整数，你就需要更强大的东西:

将 [0..1] 分成由权重决定的区间。此处您需要相对大小比率为 7:6:5:4:3:2:1 的段。所以一个区间单元的大小是1/(7+6+5+4+3+2+1)=1/28，区间的大小是7/28，6/28，... 1/28.

它们构成概率分布，因为它们总和为 1。

现在求累积分布:

P        x
7/28  => 0
13/28 => 1
18/28 => 2
22/28 => 3
25/28 => 4
27/28 => 5
28/28 => 6

现在生成一个随机的r [0..1] 中的数字，并通过找到最小的 x 在该表中查找它这样 r <= P(x) .这是您想要的随机值。

表查找可以用二分查找来完成，当直方图有很多 bin 时这是个好主意。

请注意，您正在有效地构造反累积密度函数，因此有时将此称为 inverse transforms 的方法.