python - 我可以通过更改算法来增加随机性吗？

Question

这是我目前正在使用的生成器:

from random import Random

def shuffle(size):
    """Yield random items from range(size) without replacement."""
    pool = list(range(size))
    rng = Random()
    while pool:
        yield pool.pop(rng.randrange(len(pool)))

当我使用这个生成器时，它似乎没有它应有的随机性。例如，前 4 项通常都出现在结果的前半部分或后半部分。

我正在考虑进行此更改:

def shuffle(size):
    """Yield random items from range(size) without replacement."""
    pool = list(range(size))
    rng = Random()
    while pool:
        i = rng.randrange(len(pool))
        yield pool[i]
        pool[i] = pool[-1]
        del pool[-1]

这类似于 random.sample (第 326 行)确实如此。我不知道这是为了速度还是因为它在不牺牲速度的情况下使它更加随机。

为了简单起见，我更喜欢第一个例子，但第二个例子有点困惑，我不知道 PRNG 是否符合真正的随机性。有没有办法证明第二个例子是否会更随机，也许是通过引用 Mersenne Twister 算法(Python 使用的算法)的弱点？

如果无法以一种或另一种方式证明任何事情，我将如何测试这两种算法的随机性？我知道我需要编写一个包含很多试验的测试，但我不知道如何分析结果。

我不想使用 random.sample，因为我希望我的最终列表是部分排序的，而且我认为生成器更适合。

Answer 1

假设您有一个 list(range(10)) 列表，并且您正在跟踪返回数字 5 的时间。

在随机情况下，如果算法运行 100 次，数字 5 将作为第一个数字和最后一个数字返回。因此，如果您按频率跟踪返回位置的 map ，您可能会看到类似以下内容:

[{0: 10, 1: 11, 
2: 8, 3: 12, 
4: 10, 5: 10, 
6: 9, 7: 10, 
8: 10, 9: 10] 

您或许可以使用 Kolmogorov–Smirnov 检验之类的东西来证明分布是不同的还是相同的。