Tengo dos algoritmos para encontrar 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é? ¿Es esta una peculiaridad de Python que se puede optimizar (cómo?), O me falta algo más?

El problema que estoy resolviendo es esencialmente dehttp: //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. Tambien tengosmallprimes, una lista prefabricada de todos los números primos menores o iguales 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

Callingrange_f1(N-delta,N,smallprimes) lleva mucho tiempo (unos 10 segundos). El bucle interno se llama 195170 veces. También tengo una versión de este algoritmo que reemplaza el bucle con una comprensión de la lista (esa es la que realmente uso para el perfil; vea el final de la pregunta) pero eso no es más rápido.

a segunda versión es (una implementación fea de) el tamiz 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 puedo explicar por qué esto es rápido.

Pensé que tal vez la razón es porque el bucle interno del primer algoritmo contiene aritmética modular, mientras que el segundo solo tiene una asignación. Sin embargo, lo siguiente parece implicar que la asignación no es más rápida 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á la versión (menos legible) del primer algoritmo que realmente uso:

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 al generador de perfiles para range_f2 () (tenga en cuenta el número de veces que se evalúa la expresión generadora):

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

Aquí está el resultado del generador 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á el código completo que genera las listas de primos pequeños (de una manera muy tonta) para que pueda verificar qué resultados obtiene:http: //pastebin.com/7sfN4mG

ACTUALIZA Por demanda popular, los datos de perfil para el primer fragmento de código. No hay datos sobre cuántas veces se ejecuta el bucle interno, pero parece bastante claro que es lo 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}