1

众所周知，Python 使用 Mersenne Twister (MT) 算法来处理其随机数。然而，尽管周期很长（~2^19937），但众所周知，当您对大于 2080 个元素的序列进行洗牌时（因为 !2081 > 2^19937），您无法达到每个随机排列。当我处理排列和统计属性对我来说很重要时，我试图找出将 Python 生成器与额外的随机源混合或重新播种以避免重复的最佳方法。

目前，我的概念是使用系统随机数生成器（SystemRandom）为MT生成器添加一个外部随机源。我可以想到两种方法来做到这一点：

  1. 将 SystemRandom 随机数与 MT 随机数异或
  2. 使用 SystemRandom 重新播种 MT

第一种方法由硬件随机数生成器以某种频率使用，以减少它们的偏差趋势。但是，它的效率非常低。在 Windows XP 机器上，SystemRandom 比标准 Python 随机函数慢 50 倍。当您的大部分功能都涉及改组时，这对性能造成了巨大的影响。鉴于此，使用 SystemRandom 重新播种 MT 应该会更加有效。

但是，这种方法也存在两个问题。首先，在运行期间重新播种 MT 可能会破坏其统计特性。我相当肯定，如果 MT 运行的时间足够长，这应该不是问题，因为每次运行的 MT 值都应该是格式正确的（无论起点如何）。然而，它确实表明在 MT 重新播种之间有一个相当长的时期是优选的。其次，有一个问题是什么是触发重新播种的最有效方法。处理此问题的最简单方法是使用计数器。然而，更有效的方法可能是可能的。

那么，关于这一点有三个问题：

  1. 有没有人读过任何关于在每 N 个样本后用随机值重新播种 MT 会改变其理想的统计特性的内容？
  2. 有没有人知道比增加计数器来触发重新播种更有效的方法？
  3. 最后，如果有人知道解决这个问题的一般更好的方法，我会全力以赴。
4

2 回答 2

4

重新播种不会帮助你。它只会跳入（非常非常）长的 MT 序列的其他地方。你确定洗牌你的数据会给你一个有偏见的结果吗？因为在宇宙的生命周期中，你永远不会有足够的时间来生成所有可能的序列。因此，即使您知道某些序列可能永远无法生成，但这并不意味着生成的序列会有偏差。我想你最好的选择就是简单地使用 shuffle 命令。

如果您查看numpy.random.shuffle 源代码（第 4376 行），这里基本上是使用的算法（为了清楚起见，我对其进行了简化）：

i = len(x) - 1
while i > 0:
    j = randint(0, i)
    x[i], x[j] = x[j], x[i]
    i = i - 1

换句话说，从末尾开始，它将值与数组中在它之前随机获取的随机值交换，直到所有值都被交换。最终状态不仅取决于随机生成器，还取决于数组的初始状态。这意味着理论上，如果您执行足够的洗牌，您应该能够访问所有排列。

于 2013-02-06T17:53:52.290 回答
1

I realise this was more than a year ago, but in case you glance back, there's an easy solution: Just grab a new value from SystemRandom to XOR with the output from the MT RNG every kth time, for some sufficiently large k, instead of every time. E.g. if SystemRandom is 50 times slower and you set k = 5000, your new combined RNG should only be ~1% slower, and (assuming that SystemRandom is "really" random) any permutation can be reached in every run involving more than 5000 RNG calls.

于 2014-07-22T00:30:25.050 回答