Ein schnelles Primzahl-Sieb in Python

Question

Ich habe durch Primzahlen-Generation in Python mit dem Sieb von Eratosthenes und die Lösungen, die Menschen als eine relativ schnelle Option wie die in ein paar von the answers to a question on optimising prime number generation in python sind nicht einfach und einfach Umsetzung, die ich hier habe, konkurriert sie in der Effizienz. Meine Implementierung wird unter

gegeben

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] 

den Ausführungszeitpunkt zurück

python -m timeit -n10 -s "import euler" "euler.sieve_for_primes_to(1000000)" 
10 loops, best of 3: 19.5 msec per loop 

Während das Verfahren in der Antwort auf die oben verlinkten Frage beschrieben, wie die schnellsten aus dem Python-Kochbuch zu sein, ist unter

gegeben

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())) 

Wenn es läuft, gibt es

python -m timeit -n10 -s "import euler" "euler.get_primes_erat(1000000)" 
10 loops, best of 3: 697 msec per loop 

Meine Frage ist, warum Leute die oben genannten aus dem Kochbuch tout, das relativ komplex ist, als der ideale Hauptgenerator?

Answer 1

Sie sollten nur die "postponed" variant of that algorithm verwenden. Beim Vergleich des Code test run bis zu 10 und 20 mln oberen Grenzwerte als

... 
print(len([2] + [i*2+1 for i, v in 
    enumerate(sieve_for_primes_to(10000000)) if v and i>0])) 

mit der anderen, run at den entsprechenden Zahlen von 664.579 und 1.270.607 Primzahlen zu erzeugen, wie

... 
print(list(islice((p for p in postponed_sieve()), n-1, n+1))) 

zeigt Code Lauf "nur" 3.1x ... 3.3x mal schneller. :) Nicht36x mal schneller, wie Ihre Timings aus irgendeinem Grund zeigen.

Ich glaube nicht, dass jemals jemand behauptet hat, es sei ein "idealer" Prime-Generator, nur dass es konzeptionell sauber und klar ist. Alle diese Funktionen der Prime Generation sind Spielzeuge, das echte Zeug arbeitet mit den sehr großen Zahlen und benutzt sowieso völlig andere Algorithmen.

hier im unteren Bereich, was zählt, ist die Zeitkomplexität des Algorithmus, die ~ n^(1+a) um sein sollte, a < 0.1...0.2empirical orders of growth, die beide von ihnen in der Tat zu sein scheinen. Einen Spielzeuggenerator mit ~ n^1.5 oder sogar ~ n^2 Ordnungen des Wachstums zu haben ist einfach kein Spaß, mit zu spielen.

Answer 2

transformiert ich Ihren Code in das prime Sieb Vergleich Skript von @unutbu bei Fastest way to list all primes below N passen wie folgt:

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 [2] + [i*2+1 for i, v in enumerate(sieve) if v and i>0] 

Auf meinem MBPro das Skript i7 schnell alle Primzahlen < 1000000 Berechnung aber tatsächlich 1,5-mal langsamer als rwh_primes2, rwh_primes1 (1.2), rwh_primes (1.19) und primarySieveSeq (1.12) (@andreasbriese am Seitenende).