Tengo dos algoritmos de búsqueda de primos, en Python. El bucle interno de cada uno parece ejecutarse el mismo número de veces, y es igualmente simple. Sin embargo, uno de ellos toma 10 veces más que el otro. Mi pregunta es:¿Por qué dos algoritmos para encontrar números primos difieren tanto en velocidad a pesar de que parecen hacer el mismo número de iteraciones?
¿Por qué? ¿Es esta una peculiaridad de Python que puede optimizarse (¿cómo?), ¿O me falta algo más?
El problema que estoy resolviendo es esencialmente el http://www.spoj.pl/problems/PRIME1/. En mi caso, tengo N = 10 ** 9, delta = 10 ** 5, y quiero encontrar todos los números primos entre N-delta y delta. También tengo smallprimes, una lista pre-hechos de todos los primos menor o igual a la raíz cuadrada de N. El primer algoritmo es muy simple:
def range_f1(lo, hi, smallprimes):
"""Finds all primes p with lo <= p <= hi.
smallprimes is the sorted list of all primes up to (at least) square root of hi.
hi & lo might be large, but hi-lo+1 miust fit into a long."""
primes =[]
for i in xrange(hi-lo+1):
n = lo + i
isprime = True
for p in smallprimes:
if n % p == 0:
isprime = False
break
if isprime:
primes.append(n)
return primes
Calling range_f1(N-delta,N,smallprimes) lleva mucho tiempo (unos 10 segundos). El ciclo interno se llama 195170 veces. También tengo una versión de este algoritmo que reemplaza el ciclo con una lista de comprensión (esa es la que realmente uso para crear perfiles, vea el final de la pregunta) pero eso no es más rápido.
La segunda versión es (una implementación feo de) la criba de Eratóstenes:
def range_sieve(lo, hi, smallprimes):
"""Parameters as before"""
# So ugly! But SO FAST!! How??
delta = hi-lo+1
iamprime = [True] * delta # iamprime[i] says whether lo + i is prime
if lo<= 1:
iamprime[1 - lo] = False
def sillyfun(): # For profiling & speed comparison
pass
for p in smallprimes:
rem = lo % p
if rem == 0:
iamprime[0] = False
for i in xrange(p - rem, delta, p):
iamprime[i] = False
sillyfun()
if p >= lo and p <= hi:
iamprime[p - lo] = True
return [p + lo for (p, ami) in enumerate(iamprime) if ami]
Esto es aproximadamente 10 veces más rápido, toma menos de 2 segundos. Sin embargo, el bucle interno (sillyfun()) se llama 259982 veces, más que en el último caso. No entiendo por qué esto es rápido.
Pensé que tal vez la razón es porque el ciclo interno del primer algoritmo contiene aritmética modular, mientras que el segundo solo tiene una asignación. Sin embargo, la siguiente parece dar a entender que la asignación es no más rápido que la aritmética modular:
>>> from timeit import timeit
>>> timeit("10**9 % 2341234")
0.23445186469234613
>>> timeit("a[5000]=False", "a = [True] * 10000")
0.47924750212666822
Aquí está el (menos legible) versión del primer algoritmo de hecho utilizo:
def range_f2(lo, hi, smallprimes):
primes =[]
for i in xrange(hi-lo+1):
n = lo + i
try:
(1 for p in smallprimes if n % p ==0).next()
except StopIteration:
primes.append(n)
return primes
Aquí están el resultado de llamar el perfilador para range_f2() (observe el número de tiempo la generación de la expresión se evalúa):
>>> from cProfile import run as prof
>>> prof("range_f2(N-delta,N,sp)")
200005 function calls in 13.866 CPU seconds
Ordered by: standard name
ncalls tottime percall cumtime percall filename:lineno(function)
1 0.000 0.000 13.866 13.866 <string>:1(<module>)
195170 12.632 0.000 12.632 0.000 prime1.py:101(<genexpr>)
1 1.224 1.224 13.865 13.865 prime1.py:90(range_f2)
4832 0.009 0.000 0.009 0.000 {method 'append' of 'list' objects}
1 0.000 0.000 0.000 0.000 {method 'disable' of '_lsprof.Profiler' objects}
Este es el resultado de perfiles para range_sieve():
>>> prof("range_sieve(N-delta,N,sp)")
259985 function calls in 1.370 CPU seconds
Ordered by: standard name
ncalls tottime percall cumtime percall filename:lineno(function)
1 0.003 0.003 1.370 1.370 <string>:1(<module>)
1 0.877 0.877 1.367 1.367 prime1.py:39(range_sieve)
259982 0.490 0.000 0.490 0.000 prime1.py:51(sillyfun)
1 0.000 0.000 0.000 0.000 {method 'disable' of '_lsprof.Profiler' objects}
Finalmente, aquí está él código completo que genera las listas de los pequeños números primos (de una manera muy tonta) para que pueda comprobar lo que da como resultado que se obtiene: http://pastebin.com/7sfN4mG4
ACTUALIZACIÓN Por demanda popular, los datos de generación de perfiles para el primer fragmento de código. No hay datos sobre cuántas veces se ejecuta el ciclo interno, pero parece bastante claro que es el mismo que el tercero.
>>> prof("range_f1(N-delta,N,sp)")
4835 function calls in 14.184 CPU seconds
Ordered by: standard name
ncalls tottime percall cumtime percall filename:lineno(function)
1 0.000 0.000 14.184 14.184 <string>:1(<module>)
1 14.162 14.162 14.183 14.183 prime1.py:69(range_f1)
4832 0.021 0.000 0.021 0.000 {method 'append' of 'list' objects}
1 0.000 0.000 0.000 0.000 {method 'disable' of '_lsprof.Profiler' objects}
Creo que tiene que ver con su lógica 'try ... catch'. ¿Puedes probar los dos primeros trozos de código en su lugar? – Blender
No tengo una computadora cerca para probarla ahora, pero creo que es porque en el primer caso itera sobre la lista más veces en comparación con xrange, mientras que en el segundo caso itera sobre el generador xrange más veces en comparación con la lista. ¿Lo ves? iteraciones sobre generadores como xrange es mucho más rápido en comparación con las iteraciones en las listas regulares – Timur
@Blender: el primer trozo de código es solo un poco más lento que el tercero. Creo que el intento ... captar solo los anuncios de arriba cuando la excepción se plantea, creo. Pero no hay problema, agregaré los datos de perfil. –