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

Question

如果我评估类似的东西：numpy.random.choice(2, size=100000, p=[0.01, 0.99])使用一个均匀分布的 random float，比如说r，并决定是否r < 0.01可能会浪费许多生成的随机位（熵）。我听说（二手）生成伪随机数在计算上很昂贵，所以我假设不会这样做numpy，而是在这种情况下使用像算术编码这样的方案。然而，乍一看似乎确实为每个被要求的样本choice生成了一个。float此外，一项快速timeit实验表明，生成n统一的浮点数实际上比n来自p=[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在某些情况下使用某种压缩算法是否不会显着提高性能（特别是如果size它很大且p分布不均匀）？如果不是，为什么不呢？

Answer 1

从 NumPy 1.17 开始，原因主要是向后兼容性。

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

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

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