"Si j'ai vu plus loin..."
L' erat2 fonction à partir du livre de cuisine peut être encore accéléré (environ 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
L' not (x&1) check vérifie que x est impair. Cependant, depuis les deux q et p sont impairs, par l'ajout d' 2*p de la moitié des mesures sont évités avec le test de curiosité.
erat3
Si on n'a pas l'esprit un peu plus fanciness, erat2 peut être accéléré par 35 à 40% avec les changements suivants (NB: les besoins de Python 2.7+ ou Python 3+ en raison de l' itertools.compress de la fonction):
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
L' erat3 fonction prend avantage du fait que tous les nombres premiers (à l'exception de 2, 3, 5) modulo 30 résultat, à seulement huit chiffres: ceux inclus dans l' MODULOS frozenset. Ainsi, après ce qui donne les trois premiers nombres premiers, nous commençons à partir de 7 et de travailler uniquement avec les candidats.
Le candidat de filtrage utilise l' itertools.compress de la fonction; la "magie" est dans l' MASK de la séquence; MASK a 15 éléments (il y a 15 nombres impairs dans tous les 30 numéros choisis par l' itertools.islice de la fonction) avec un 1 pour chaque candidat possible, à partir de 7. Le cycle se répète, comme spécifié par l' itertools.cycle fonction.
L'introduction du candidat du filtrage a besoin d'une autre modification: la or (x%30) not in MODULOS vérifier. L' erat2 algorithme traité tous les nombres impairs; maintenant que l' erat3 algorithme ne traite que r30 candidats, nous devons nous assurer que tous D.keys() ne peut être tel -faux candidats.
Repères
Résultats
Sur un Atom 330 Ubuntu 9.10 server, versions 2.6.4 et 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
Sur un AMD Geode LX Gentoo home server, Python 2.6.5 et 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
Référence code
Un primegen.py module contient l' erat2, erat2a et erat3 fonctions. Voici le script de test:
#!/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
