python - 调用 np.random.shuffle() 后随机状态如何更新？待洗牌列表的长度对它有何影响？

Question

调用 np.random.shuffle() 后随机状态如何更新？待洗牌列表的长度如何影响它？

这是实验:

np.random.seed(3)
print(np.random.get_state()[0],str(np.random.get_state()[1][:5]))
delta = 7
for t in [3,7,8, 9, 10]:
    print('-'*20)
    x = np.power(2, t)
    np.random.seed(3)
    a =np.arange(x-delta)
    np.random.shuffle(a)
    print(x-delta, np.random.get_state()[0],str(np.random.get_state()[1][:5]))
    np.random.seed(3)
    a =np.arange(x)
    np.random.shuffle(a)
    print(x, np.random.get_state()[0],str(np.random.get_state()[1][:5]))
    np.random.seed(3)
    a =np.arange(x+delta)
    np.random.shuffle(a)
    print(x+delta, np.random.get_state()[0],str(np.random.get_state()[1][:5]))

结果:

MT19937 [         3 1142332464 3889748055 3734916391 3619205944]
--------------------
1 MT19937 [         3 1142332464 3889748055 3734916391 3619205944]
8 MT19937 [2266350226  522119106 3046352735  732669494 2548320174]
15 MT19937 [2266350226  522119106 3046352735  732669494 2548320174]
--------------------
121 MT19937 [2266350226  522119106 3046352735  732669494 2548320174]
128 MT19937 [2266350226  522119106 3046352735  732669494 2548320174]
135 MT19937 [2266350226  522119106 3046352735  732669494 2548320174]
--------------------
249 MT19937 [2266350226  522119106 3046352735  732669494 2548320174]
256 MT19937 [2266350226  522119106 3046352735  732669494 2548320174]
263 MT19937 [2266350226  522119106 3046352735  732669494 2548320174]
--------------------
505 MT19937 [3210938781 3041878801 2995991318 2989044749 4131327847]
512 MT19937 [3210938781 3041878801 2995991318 2989044749 4131327847]
519 MT19937 [3210938781 3041878801 2995991318 2989044749 4131327847]
--------------------
1017 MT19937 [2643427254 2135041851 1650564992  768318449  937622320]
1024 MT19937 [2643427254 2135041851 1650564992  768318449  937622320]
1031 MT19937 [2643427254 2135041851 1650564992  768318449  937622320]

非常感谢。

Answer 1

快速查看 NumPy 0.14.x 源代码。显然用的是Fisher-Yates，就地版本，你可以看一下Efficiently yield elements from large list in (pseudo) random order算法如何工作。我看到的唯一区别是 NumPy 以相反的顺序进行洗牌(从 n 到 1)。

因此对整数范围内 RNG 的调用次数等于数组长度。但这里有一个问题 - 为了让整数内部数字生成器可能被多次调用，这里有一个 while 循环。

因此，这个故事的寓意是 - 要对大小为 n 的数组进行洗牌，RNG 将被调用 >= n 次。

更新

这里是间隔 RNG 的样子(Win10，x64):

unsigned long rk_interval(unsigned long max, rk_state *state) {
    unsigned long mask = max, value;

    if (max == 0) {
        return 0;
    }
    /* Smallest bit mask >= max */
    mask |= mask >> 1;
    mask |= mask >> 2;
    mask |= mask >> 4;
    mask |= mask >> 8;
    mask |= mask >> 16;

    /* Search a random value in [0..mask] <= max */
    while ((value = (rk_ulong(state) & mask)) > max);

    return value;
}

rk_ulong(state) 很像 Mersenne Twister 的一些包装

你看，有一个掩码构建，但掩码值可能超出最大值，因此 while 循环是必要的，这就是使得对 MT 的调用次数 >= 中的项目数的原因要洗牌的数组。