为什么 numpy.random.choice 不使用算术编码？

Question

如果我评估如下：

numpy.random.choice(2, size=100000, p=[0.01, 0.99])

使用一个均匀分布的随机数float，例如r，并决定是否r < 0.01会浪费许多生成的随机位（熵）。我听说（二手）生成伪随机数的计算成本很高，所以我认为numpy不会这样做，而是会在这种情况下使用算术编码之类的方案。

然而，乍一看似乎确实为它所要求的每个样本choice生成了一个。float此外，快速timeit实验表明，生成均匀浮点数实际上比 中的样本n更快。np=[0.01, 0.99]

>>> timeit.timeit(lambda : numpy.random.choice(2, size=100000, p=[0.01, 0.99]), number=1000)
1.74494537999999
>>> timeit.timeit(lambda : numpy.random.random(size=100000), number=1000)
0.8165735180009506

真的会像看起来那样为每个样本choice生成一个吗？在某些情况下（特别是当数据很大且分布不均匀时），float使用某种压缩算法不会显着提高性能吗？如果没有，为什么不呢？sizep

Answer 1

从 NumPy 1.17 开始，原因很大程度上是向后兼容性。另请参阅这个问题和这个问题。

根据 NumPy的新 RNG 政策，从 NumPy 1.17 开始numpy.random.*，包括 在内的函数numpy.random.choice都是遗留函数，并且“应保持与当前相同”，该政策还为 NumPy 引入了新的随机生成系统。使它们成为遗留功能的原因包括避免全局状态的建议。然而，即便如此，NumPy 并没有弃用版本 1.17 中的任何函数，尽管 NumPy 的未来版本可能会弃用。numpy.random.*

回想一下，在您的示例中，numpy.random.choice采用 s 数组float作为权重。整数权重数组将导致更精确的随机数生成。尽管任何都float可以转换为有理数（导致有理值权重，从而产生整数权重），但旧版 NumPy 似乎并没有这样做。numpy.random.choice在不破坏向后兼容性的情况下，无法更改这些和其他实现决策。

顺便说一句，算术编码并不是唯一试图避免浪费比特的算法。也许离散分布采样的规范算法是 Knuth 和 Yao 算法（1976），它根据所涉及的概率的二元展开精确地选择一个随机整数，并将问题视为二叉树上的随机游走。（该算法平均使用距理论下界最多 2 位的数据。）任何其他整数生成算法最终都可以用相同的方式描述，即二叉树上的随机游走。例如，快速加载骰子滚轮是一种最新算法，其使用的平均位数有一个有保证的界限（在本例中，与理论下限相差不超过 6 位）。Han 和 Hoshi 算法（1997 年）是另一种此类算法，但使用累积概率。另请参阅我的部分“替换的加权选择”。