¿Por qué mi Criba de Eratóstenes es tan lenta?

Estoy resolviendo algunos problemas en el Proyecto Euler y tuve que generar 2 millones de números primos para resolver un problema. Mi implementación del Tamiz de Eratóstenes resultó ser extremadamente lenta pero no sé muy bien por qué. ¿Podría alguien explicar los principales problemas con esta implementación? Pensé que era muy bonito, y luego me di cuenta de que es absolutamente terrible :(. Encontré otra implementación en línea y fue mucho más rápida que la mía.

def generatePrimes(upperBound): numbers = range(2,upperBound+1) primes = [] while numbers: prime = numbers[0] primes.append(prime) numbers = filter((lambda x: x%prime),numbers) return primes 

EDIT: ¡Gracias por todas las respuestas! Las conclusiones de esto es que el problema es el filtro, ya que atraviesa cada elemento (en lugar de solo aquellos que deben marcarse como no primos) y porque crea una nueva lista cada vez. Vuelva a escribirlo con buenos viejos para bucles y una ronda de filtrado y funciona mucho más rápido. Nuevo código:

 def generatePrimes(upperBound): numbers = range(2,upperBound+1) for i in xrange(len(numbers)): if(numbers[i] != 0): for j in xrange(i+numbers[i],len(numbers),numbers[i]): numbers[j] = 0 primes = filter(lambda x: x,numbers) return primes 

El Tamiz de Eratóstenes se ve así:

 def sieve(n): primality_flags = [True]*(n+1) primality_flags[0] = primality_flags[1] = False primes = [] for i, flag in enumerate(primality_flags): if flag: primes.append(i) for j in xrange(2*i, n+1, i): primality_flags[i] = False return primes 

Procesa cada número una vez cuando el bucle externo lo alcanza, y una vez por cada primo que lo divide. Aproximadamente la mitad de los números son divisibles por 2, aproximadamente 1/3 son divisibles por 3, y así sucesivamente; En términos asintóticos, el número promedio de veces que se procesará cada número es 1 + la sum de los recíprocos de los primos hasta n. Esta sum se trata de log(log(n)) , por lo que el tamiz tiene una complejidad de tiempo asintótica O(n*log(log(n))) , suponiendo que la aritmética es un tiempo constante. Esto es realmente bueno.


Tu función no hace eso. Su filter repasa todos los elementos en numbers , independientemente de si es divisible por prime . Cada elemento se procesa para cada cebado hasta que el primer cebado que lo divide, y el procesamiento del primo p elimina aproximadamente 1 / p de los elementos de los numbers . Dejar que la secuencia de primos sea p [0], p [1], p [2], etc., y dejar que la secuencia de tamaños de numbers sea ​​n [0], n [1], n [2], etc. , tenemos la siguiente recurrencia aproximada:

 n[0] = upperBound - 1 n[1] = n[0] * (p[0]-1)/p[0] n[2] = n[1] * (p[1]-1)/p[1] ... n[k+1] = n[k] * (p[k]-1)/p[k] 

y su algoritmo toma tiempo aproximadamente proporcional a la sum de los n valores hasta que los numbers estén vacíos. No he analizado el comportamiento de esa serie, pero los cálculos muestran que el crecimiento es mucho peor que O(n*log(log(n))) . (EDITAR: Un análisis que no se me ocurrió al redactar esta respuesta dice que es O ((n / log (n)) ^ 2).)

La ejecución de cProfile muestra que la mayor parte del tiempo se pasa en el filtro. Reemplazar el filtro con una lista de comprensión acelera las cosas en aproximadamente un factor de 2.

 numbers = [n for n in numbers if n%prime != 0] 

Pero esto realmente no soluciona el problema principal, que es que estás recreando la lista de números con cada iteración, y eso es lento. Las implementaciones más rápidas http://groups.google.com/group/comp.lang.python/msg/f1f10ced88c68c2d simplemente marcan los números primos reemplazándolos con 0 o similar.