Tenho dois algoritmos para encontrar números primos, em Python. O loop interno de cada um parece ser executado o mesmo número de vezes e é igualmente simples. No entanto, um deles leva 10 vezes mais que o outro. Minha pergunta é

Por quê? Isso é uma peculiaridade do Python que pode ser otimizada (como?) Ou estou perdendo outra coisa?

O problema que estou resolvendo é essencialmente dehttp: //www.spoj.pl/problems/PRIME1. No meu caso, tenho N = 10 ** 9, delta = 10 ** 5 e quero encontrar todos os números primos entre N-delta e delta. Eu também tenhosmallprimes, uma lista pré-criada de todos os números primos menores ou iguais à raiz quadrada de N. O primeiro algoritmo é muito simples:

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) demora muito tempo (cerca de 10 segundos). O loop interno é chamado 195170 vezes. Também tenho uma versão desse algoritmo que substitui o loop por uma compreensão de lista (essa é a que eu realmente uso para criação de perfil; veja o final da pergunta), mas isso não é mais rápid

A segunda versão é (uma feia implementação) da peneira 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]

Isso é cerca de 10 vezes mais rápido, leva menos de 2 segundos. No entanto, o loop interno (sillyfun ()) é chamado 259982 vezes, mais do que no último caso. Não sei explicar por que isso é rápido.

Pensei que talvez o motivo seja porque o loop interno do primeiro algoritmo contém aritmética modular, enquanto o segundo apenas possui uma atribuição. No entanto, o seguinte parece sugerir que a atribuição não é mais rápida que a aritmética modular:

>>> from timeit import timeit
>>> timeit("10**9 % 2341234")
0.23445186469234613
>>> timeit("a[5000]=False", "a = [True] * 10000")
0.47924750212666822

Aqui está a versão (menos legível) do primeiro algoritmo que eu 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

Aqui estão o resultado de chamar o criador de perfil para range_f2 () (observe o número de vezes que a expressão da geração é avaliada):

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

Aqui está o resultado do criador de perfil 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, aqui está o código completo que gera as listas de pequenos números primos (de uma maneira muito boba), para que você possa verificar quais resultados obtém:http: //pastebin.com/7sfN4mG

ATUALIZA Por demanda popular, os dados de criação de perfil para o primeiro pedaço de código. Não há dados sobre quantas vezes o loop interno é executado, mas parece bastante claro que é o mesmo que o terceir

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