¿Por qué mi Tamiz de Eratóstenes funciona más rápido con enteros que con booleanos?

Escribí un simple Tamiz de Eratóstenes, que usa una lista de unos y los convierte en ceros, si no es primo, de esta manera:

def eSieve(n): #Where m is fixed-length list of all integers up to n '''Creates a list of primes less than or equal to n''' m = [1]*(n+1) for i in xrange(2,int((n)**0.5)+1): if m[i]: for j in xrange(i*i,n+1,i): m[j]=0 return [i for i in xrange(2,n) if m[i]] 

%timeit la velocidad que corría con %timeit y obtuve:

 #n: t #10**1: 7 μs #10**2: 26.6 μs #10**3: 234 μs #10**4: 2.46 ms #10**5: 26.4 ms #10**6: 292 ms #10**7: 3.27 s 

Supuse que si cambiaba [1] y 0 a booleanos, se ejecutaría más rápido … pero hace lo contrario:

 #n: t #10**1: 7.31 μs #10**2: 29.5 μs #10**3: 297 μs #10**4: 2.99 ms #10**5: 29.9 ms #10**6: 331 ms #10**7: 3.7 s 

¿Por qué los booleanos son más lentos?

Esto sucede porque True y False son buscados como globales en Python 2. Los literales 0 y 1 son solo constantes, buscados por una referencia de matriz rápida, mientras que los globales son búsquedas de diccionario en el espacio de nombres global ):

 >>> import dis >>> def foo(): ... a = True ... b = 1 ... >>> dis.dis(foo) 2 0 LOAD_GLOBAL 0 (True) 3 STORE_FAST 0 (a) 3 6 LOAD_CONST 1 (1) 9 STORE_FAST 1 (b) 12 LOAD_CONST 0 (None) 15 RETURN_VALUE 

El valor True se busca con el bytecode LOAD_GLOBAL , mientras que el valor literal 1 se copia a la stack con LOAD_CONST .

Si False locals True y False , puedes hacerlos igual de rápido otra vez:

 def eSieve(n, True=True, False=False): m = [True]*(n+1) for i in xrange(2,int((n)**0.5)+1): if m[i]: for j in xrange(i*i,n+1,i): m[j]=False return [i for i in xrange(2,n) if m[i]] 

La asignación de True y False como valores predeterminados para argumentos proporciona a la función esos nombres como locales, con los mismos valores exactos; otra vez usando una versión simplificada:

 >>> def bar(True=True, False=False): ... True == False ... >>> dis.dis(bar) 2 0 LOAD_FAST 0 (True) 3 LOAD_FAST 1 (False) 6 COMPARE_OP 2 (==) 9 POP_TOP 10 LOAD_CONST 0 (None) 13 RETURN_VALUE 

Tenga en cuenta los LOAD_FAST , ahora con índices como los LOAD_CONST byte LOAD_CONST ; los locales en una función CPython se almacenan en una matriz al igual que las constantes de bytecode.

Con ese cambio, el uso de valores booleanos gana, aunque sea por un pequeño margen; mis tiempos:

 # n integers globals locals # 10**1 4.31 µs 4.2 µs 4.2 µs # 10**2 17.1 µs 17.3 µs 16.5 µs # 10**3 147 µs 158 µs 144 µs # 10**4 1.5 ms 1.66 ms 1.48 ms # 10**5 16.4 ms 18.2 ms 15.9 ms # 10**6 190 ms 215 ms 189 ms # 10**7 2.21 s 2.47 s 2.18 s 

La diferencia no es realmente tan grande porque los booleanos de Python son solo una subclase int .

Tenga en cuenta que en Python 3, True y False han convertido en palabras clave y ya no se pueden asignar, lo que hace posible tratarlos como literales enteros.