Shorter run time of `random.shuffle` when using` random.random` as a keyword argument in Python3

Question

I just noticed that when using Python3, shuffling the list with random.shuffle takes about half the execution time when explicitly passing the random.random function to the random keyword argument. I checked if Python2 has the same problem, but found that this only happens with Python3.

I use the following code to measure the runtime of two versions:

 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)) 

I did a testcase on ideone so you can see the same code with python2 with Python3 .

According to the documentation for shuffling, the same random.random function random.random used in the default case when I omit the optional argument of the random keyword, so there should be no difference when I give it the same function to generate a random number as in the case of by default.

I checked the appropriate sources (Python2 vs. Python3) for the shuffle function in the Lib/random.py and found that they behave the same if I explicitly call the Python3 version with the function for the random keyword. If I omit this argument, Python3 uses helper function _randbelow , so there should be a root for my problem. I do not understand why Python3 uses _randbelow because it slows down shuffle . As far as I understand, its advantage is the generation of arbitrary large random numbers, but this should not slow down my shuffling of a list that has less than 2 ^ 32 elements (in my case, 100,000).

Can someone explain to me why I see such a difference at runtime, although they should be closer to each other when I use Python3?

PS: Please note that I am not interested in why the runtime with Python2 is better than with Python3, but the difference in runtime when using the argument rand=rand.rand in Python3, and not in use only in Python3.

Answer 1

The doctrine in the random.shuffle function contradicts the code. In python 2.7.2+, the document line is correct:

  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] 

But in Python 3.2 we find:

 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] 

So the doctrine is still telling the old story, but now the default function used is random.rand below