Почему два алгоритма нахождения простых чисел так сильно различаются по скорости, даже если кажется, что они выполняют одинаковое количество итераций?

У меня есть два алгоритма поиска простых чисел в Python. Кажется, что внутренний цикл каждого из них выполняется одинаковое количество раз и одинаково прост. Тем не менее, один из них занимает в 10 раз больше, чем другой. Мой вопрос:

Почему? Это какая-то особенность Python, которую можно оптимизировать (как?), Или я что-то упускаю?

Проблема, которую я решаю, по сути изhttp://www.spoj.pl/problems/PRIME1/, В моем случае у меня N = 10 ** 9, дельта = 10 ** 5, и я хочу найти все простые числа между N-дельтой и дельтой. у меня тоже естьsmallprimes, предварительно составленный список всех простых чисел, меньших или равных квадратному корню из N. Первый алгоритм очень прост:

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

призваниеrange_f1(N-delta,N,smallprimes) занимает много времени (около 10 секунд). Внутренний цикл называется 195170 раз. У меня также есть версия этого алгоритма, которая заменяет цикл на понимание списка (это та, которую я фактически использую для профилирования; см. Конец вопроса), но это не быстрее.

Вторая версия - это (уродливая реализация) сито Эратосфена:

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]

Это примерно в 10 раз быстрее, занимает не более 2 секунд. Однако внутренний цикл (sillyfun ()) вызывается 259982 раза, больше, чем в последнем случае. Я затрудняюсь объяснить, почему это так быстро.

Я подумал, что, возможно, причина в том, что внутренний цикл первого алгоритма содержит модульную арифметику, а второй имеет только присваивание. Однако следующее, по-видимому, подразумевает, что присваивание не быстрее, чем модульная арифметика:

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

Вот (менее читаемая) версия первого алгоритма, который я фактически использую:

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

Вот результат вызова профилировщика для range_f2 () (обратите внимание, что оценивается число генерирующих время выражений):

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

Вот результат профилировщика для 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}

Наконец, вот полный код, который генерирует списки небольших простых чисел (очень глупо), чтобы вы могли проверить, какие результаты вы получите:http://pastebin.com/7sfN4mG4

ОБНОВИТЬ По многочисленным просьбам данные профилирования для первого куска кода. Нет данных о том, сколько раз выполнялся внутренний цикл, но кажется достаточно ясным, что он такой же, как и третий.

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

Ответы на вопрос(1)

Ваш ответ на вопрос