Shorter runtime di `random.shuffle` quando si utilizza` random.random` argomento come parola chiave nel python3

Question

Ho appena notato che quando si utilizza python3 il rimescolamento di una lista con random.shuffle ha bisogno di circa la metà il tempo di esecuzione al momento della presentazione in modo esplicito la funzione random.random per la Argomento parola chiave random. Ho verificato se Python2 ha lo stesso problema ma ho scoperto che si verifica solo con Python3.

Io uso il seguente codice per misurare il tempo di esecuzione delle due versioni:

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

Ho fatto una testcase at ideone per voi a vedere con python3 e lo stesso codice con Python2.

Secondo il documentation for shuffle la stessa funzione random.random viene utilizzata in caso di default quando Tralascio l'argomento parola chiave opzionale random, quindi non ci dovrebbe essere alcuna differenza quando mi danno la stessa funzione per generare il numero casuale, come nel caso di default .

Ho controllato le rispettive fonti (python2 vs. python3) per la funzione shuffle nelle Lib/random.py cartelle e ha scoperto che si comportano allo stesso modo se chiamo esplicitamente la versione python3 con una funzione per la parola chiave random. Se ometto questo argomento, Python3 usa la funzione helper _randbelow quindi dovrebbe esserci la root per il mio problema. Non vedo perché Python3 usi _randbelow perché rallenta shuffle. Per quanto ho capito, il suo vantaggio sta nel generare numeri casuali arbitrari di grandi dimensioni, ma non dovrebbe rallentare il mio mescolamento di un elenco che ha meno di 2^32 elementi (100000 nel mio caso).

Qualcuno può spiegarmi perché sto vedendo una tale differenza nei tempi di esecuzione anche se dovrebbero essere più vicini quando uso Python3?

P.S .: Si noti che non mi interessa perché il runtime con Python2 è migliore rispetto a Python3, ma la differenza in runtime quando si utilizza l'argomento argomento rand=rand.rand in Python3 rispetto a non utilizzarlo solo in Python3.

Answer 1

La docstring nella funzione random.shuffle contraddice il codice. in Python 2.7.2+ la docstring è corretto:

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] 

Ma in Python 3.2 troviamo:

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] 

Così il docstring dice ancora la vecchia storia, ma ora la funzione predefinita utilizzata è casuale .randbelow