«Если бы я видел дальше…»
Функция erat2 из поваренной книги может быть еще более ускорена (примерно на 20-25%):
erat2a
import itertools as it
def erat2a( ):
D = { }
yield 2
for q in it.islice(it.count(3), 0, None, 2):
p = D.pop(q, None)
if p is None:
D[q*q] = q
yield q
else:
# old code here:
# x = p + q
# while x in D or not (x&1):
# x += p
# changed into:
x = q + 2*p
while x in D:
x += 2*p
D[x] = p
Проверка not (x&1) подтверждает, что x нечетно. Однако, поскольку и q, и p нечетны, при добавлении 2*p половина шагов исключается вместе с проверкой на нечетность.
erat3
Если вы не возражаете против некоторой дополнительной фантазии, erat2 можно ускорить на 35-40% со следующими изменениями (NB: требуется Python 2.7+ или Python 3+ из-за функции itertools.compress):
import itertools as it
def erat3( ):
D = { 9: 3, 25: 5 }
yield 2
yield 3
yield 5
MASK= 1, 0, 1, 1, 0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0,
MODULOS= frozenset( (1, 7, 11, 13, 17, 19, 23, 29) )
for q in it.compress(
it.islice(it.count(7), 0, None, 2),
it.cycle(MASK)):
p = D.pop(q, None)
if p is None:
D[q*q] = q
yield q
else:
x = q + 2*p
while x in D or (x%30) not in MODULOS:
x += 2*p
D[x] = p
Функция erat3 использует тот факт, что все простые числа (кроме 2, 3, 5) по модулю 30 дают только восемь чисел: те, которые включены в морозильное устройство MODULOS. Таким образом, после получения начальных трех простых чисел, мы начинаем с 7 и работаем только с кандидатами.
Фильтрация кандидатов использует функцию itertools.compress; «магия» находится в последовательности MASK; MASK имеет 15 элементов (в каждых 30 числах по 15 нечетных чисел, выбранных функцией itertools.islice) с 1 для каждого возможного кандидата, начиная с 7. Цикл повторяется, как указано itertools.cycle функция.
Введение фильтрации кандидатов требует другой модификации: проверка or (x%30) not in MODULOS. Алгоритм erat2 обрабатывает все нечетные числа; теперь, когда алгоритм erat3 обрабатывает только r30 кандидатов, нам нужно убедиться, что все D.keys() могут быть только такими «ложными» кандидатами.
Тесты
Результаты
На сервере Atom 330 Ubuntu 9.10 версии 2.6.4 и 3.1.1 +:
$ testit
up to 8192
==== python2 erat2 ====
100 loops, best of 3: 18.6 msec per loop
==== python2 erat2a ====
100 loops, best of 3: 14.5 msec per loop
==== python2 erat3 ====
Traceback (most recent call last):
…
AttributeError: 'module' object has no attribute 'compress'
==== python3 erat2 ====
100 loops, best of 3: 19.2 msec per loop
==== python3 erat2a ====
100 loops, best of 3: 14.1 msec per loop
==== python3 erat3 ====
100 loops, best of 3: 11.7 msec per loop
На домашнем сервере AMD Geode LX Gentoo, Python 2.6.5 и 3.1.2:
$ testit
up to 8192
==== python2 erat2 ====
10 loops, best of 3: 104 msec per loop
==== python2 erat2a ====
10 loops, best of 3: 81 msec per loop
==== python2 erat3 ====
Traceback (most recent call last):
…
AttributeError: 'module' object has no attribute 'compress'
==== python3 erat2 ====
10 loops, best of 3: 116 msec per loop
==== python3 erat2a ====
10 loops, best of 3: 82 msec per loop
==== python3 erat3 ====
10 loops, best of 3: 66 msec per loop
Код теста
Модуль
A primegen.py содержит функции erat2, erat2a и erat3. Ниже приведен сценарий тестирования:
#!/bin/sh
max_num=${1:-8192}
echo up to $max_num
for python_version in python2 python3
do
for function in erat2 erat2a erat3
do
echo "==== $python_version $function ===="
$python_version -O -m timeit -c \
-s "import itertools as it, functools as ft, operator as op, primegen; cmp= ft.partial(op.ge, $max_num)" \
"next(it.dropwhile(cmp, primegen.$function()))"
done
done