Un Rapide Premier Numéro de Tamis en Python
J'ai été en passant par le premier numéro de génération en python en utilisant le crible d'Eratosthène et les solutions que de gens tout comme relativement rapide en option, tels que ceux dans quelques-uns de les réponses à une question sur l'optimisation premier numéro de génération en python ne sont pas simples et la mise en œuvre simple que j'ai ici rivaux dans l'efficacité. Mon application est donnée ci-dessous
def sieve_for_primes_to(n):
size = n//2
sieve = [1]*size
limit = int(n**0.5)
for i in range(1,limit):
if sieve[i]:
val = 2*i+1
tmp = ((size-1) - i)//val
sieve[i+val::val] = [0]*tmp
return sieve
print [2] + [i*2+1 for i, v in enumerate(sieve_for_primes_to(10000000)) if v and i>0]
Timing de l'exécution retourne
python -m timeit -n10 -s "import euler" "euler.sieve_for_primes_to(1000000)"
10 loops, best of 3: 19.5 msec per loop
Bien que la méthode décrite dans la réponse à la ci-dessus liés question comme étant le plus rapide de l'python cookbook est donnée ci-dessous
import itertools
def erat2( ):
D = { }
yield 2
for q in itertools.islice(itertools.count(3), 0, None, 2):
p = D.pop(q, None)
if p is None:
D[q*q] = q
yield q
else:
x = p + q
while x in D or not (x&1):
x += p
D[x] = p
def get_primes_erat(n):
return list(itertools.takewhile(lambda p: p<n, erat2()))
Lorsqu'il est exécuté, il donne
python -m timeit -n10 -s "import euler" "euler.get_primes_erat(1000000)"
10 loops, best of 3: 697 msec per loop
Ma question est de savoir pourquoi les gens tout les ci-dessus à partir du livre de cuisine qui est relativement complexe comme l'idéal le premier générateur?
- Qui et où est vantant
erat2
"comme idéal premier générateur"? Veuillez fournir des références qui nous permettent de mieux comprendre le contexte qui a donné lieu à votre question. - Avez-vous comparer les vôtres contre le
rwh_primes2
algorithme? erat2
était que par rapport à l'OP du code sur cette page, et Alex Martelli a seulement dit que le livre de cuisine de la solution est plus de deux fois plus rapide par rapport à l'OP de la solution. Et votre solution est deux fois plus lent par rapport àrwh_primes2
.- Cela ressemble à une variation mineure sur
rwh_primes1
.
Vous devez vous connecter pour publier un commentaire.
J'ai transformé votre code pour l'adapter dans le premier tamis comparaison script de @unutbu à Le plus rapide moyen de la liste de tous les nombres premiers en dessous de N
comme suit:
Sur mon MBPro i7 le script est rapide à calculer tous les nombres premiers < 1000000 mais en fait 1,5 fois plus lent que rwh_primes2, rwh_primes1 (1.2), rwh_primes (1.19) et primeSieveSeq (1.12) (@andreasbriese à la fin de cette page).
Vous ne devez utiliser les "reporté" variante de cet algorithme. En comparant votre code essai jusqu'à 10 et 20 millions de limite supérieure, comme
avec l'autre, exécuter à les chiffres correspondants de 664579 et 1270607 premiers à produire, comme
montre ton code en cours d'exécution "seulement" 3.1 x...3.3 x fois plus rapide. 🙂 Pas 36x fois plus vite, que votre timings de spectacle pour une raison quelconque.
Je ne pense pas que quiconque n'a jamais prétendu que c'est un "idéal", le premier générateur, c'est juste que c'est un conceptuellement propre et clair. Tous ces premier des fonctions de génération sont des jouets vraiment, le vrai truc est de travailler avec les grands nombres, en utilisant complètement différents algorithmes de toute façon.
Ici, dans le bas de gamme, ce qui compte c'est la complexité temporelle de l'algorithme, qui devrait être autour de
~ n^(1+a)
,a < 0.1...0.2
empiriques commandes de croissance, dont deux d'entre eux semblent être en effet. Avoir un jouet générateur avec~ n^1.5
ou même~ n^2
les commandes de la croissance est juste pas de plaisir à jouer avec.