Un setaccio numero primo rapido in Python

Question

Ho passato attraverso la generazione di numeri primi in python usando il setaccio di Eratostene e le soluzioni che le persone propongono come un'opzione relativamente veloce come quelle in alcuni di the answers to a question on optimising prime number generation in python non sono semplici e il semplice l'implementazione che ho qui rivaleggia in efficienza. La mia applicazione è riportata qui sotto

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 l'esecuzione ritorna

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

Mentre il metodo descritto nella risposta alla domanda di cui sopra legati ad essere il più veloce dal ricettario pitone è indicato di seguito

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

Quando eseguito dà

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

La mia domanda è: perché la gente dice quanto sopra dal libro di cucina che è relativamente complesso come il primo generatore ideale?

Answer 1

Utilizzare solo lo "postponed" variant of that algorithm. Il confronto del codice test run fino a 10 e 20 milioni di limite superiore, come

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

con l'altro, run at corrispondenti figure 664.579 e 1270607 numeri primi per produrre, come

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

mostra l'esecuzione del codice "solo" 3.1x ... 3.3x volte più veloce. :) Non36x più veloce, come mostrano i tempi per qualche motivo.

Non credo che nessuno abbia mai affermato che si tratta di un generatore principale "ideale", solo che è concettualmente pulito e chiaro. Tutte queste funzioni di prima generazione sono davvero giocattoli, le cose reali stanno lavorando con numeri molto grandi, usando comunque algoritmi completamente diversi.

Qui nella gamma bassa, ciò che conta è la complessità temporale dell'algoritmo, che dovrebbe essere intorno a ~ n^(1+a), a < 0.1...0.2empirical orders of growth, che entrambi sembrano essere effettivamente. Avere un generatore di giocattoli con ~ n^1.5 o anche gli ordini di crescita ~ n^2 non è affatto divertente da giocare.

Answer 2

ho trasformato il codice per inserire nello script confronto vaglio primario di @unutbu a Fastest way to list all primes below N come segue:

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] 

Sul mio MBPRO I7 lo script sta rapidamente calcolando tutti i primi < 1000000 ma in realtà 1,5 volte più lento di rwh_primes2, rwh_primes1 (1.2), rwh_primes (1.19) e primeSieveSeq (1.12) (@andreasbriese alla fine della pagina).