在Python3中使用`random.random`作为关键字参数时`random.shuffle`运行时间更短

Question

我刚刚发现，在使用Python3的时候，用random.shuffle来打乱一个列表时，如果我明确地给random这个参数传入random.random这个函数，运行时间大约只需要一半。我检查了一下Python2，发现这个问题只出现在Python3上。

我用以下代码来测量这两个版本的运行时间：

from timeit import Timer
t1 = Timer("random.shuffle(l)", "import random; l = list(range(100000))")
t2 = Timer("random.shuffle(l, random = random.random)", "import random; l = list(range(100000))")
print("With default rand: %s" % t1.repeat(10,1))
print("With custom rand: %s" % t2.repeat(10,1))

我在ideone上做了一个测试案例，你可以看到Python3的代码，还有一个Python2的相同代码。

根据shuffle的文档，当我省略可选的random参数时，默认情况下会使用同样的random.random函数，所以我给它传入同样的随机数生成函数时，应该没有区别。

我查看了Lib/random.py文件夹中shuffle函数的源代码（Python2和Python3），发现它们的行为是一样的，前提是我在Python3中明确调用这个random参数。如果我省略这个参数，Python3会使用一个叫_randbelow的辅助函数，这可能就是我遇到问题的根源。我不明白为什么Python3会使用_randbelow，因为这会让shuffle变慢。根据我的理解，它的好处在于可以生成任意大的随机数，但在我这个只有100000个元素（远小于2^32）的列表中，打乱列表的速度不应该变慢。

有没有人能告诉我，为什么在使用Python3时，运行时间会有这么大的差异，虽然它们在使用Python3时应该更接近呢？

附注：请注意，我并不想知道为什么Python2的运行时间比Python3好，我只想了解在Python3中使用rand=rand.rand这个参数和不使用它时的运行时间差异。

Answer 1

在函数 random.shuffle 的文档说明里，有些内容和实际代码不一致。

在 Python 2.7.2 及以上版本中，文档说明是正确的：

    def shuffle(self, x, random=None, int=int):
    """x, random=random.random -> shuffle list x in place; return None.

    Optional arg random is a 0-argument function returning a random
    float in [0.0, 1.0); by default, the standard random.random.
    """

    if random is None:
        random = self.random
    for i in reversed(xrange(1, len(x))):
        # pick an element in x[:i+1] with which to exchange x[i]
        j = int(random() * (i+1))
        x[i], x[j] = x[j], x[i]

但是在 Python 3.2 版本中，我们发现：

def shuffle(self, x, random=None, int=int):
    """x, random=random.random -> shuffle list x in place; return None.

    Optional arg random is a 0-argument function returning a random
    float in [0.0, 1.0); by default, the standard random.random.
    """

    randbelow = self._randbelow
    for i in reversed(range(1, len(x))):
        # pick an element in x[:i+1] with which to exchange x[i]
        j = randbelow(i+1) if random is None else int(random() * (i+1))
        x[i], x[j] = x[j], x[i]

所以文档说明还是在讲以前的事情，但现在默认使用的函数是 random.randbelow。