У меня есть два алгоритма поиска простых чисел в 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}