Sito szybkich liczb pierwszych w Pythonie

Question

Przeszukałem generację liczb pierwszych w pythonie za pomocą sita Eratostenesa, a rozwiązania, które ludzie reklamują jako stosunkowo szybka opcja, takie jak te w kilku z the answers to a question on optimising prime number generation in python, nie są proste i proste. Wdrożenie, które mam tutaj, konkuruje z wydajnością. Moja implementacja jest podana poniżej

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] 

odmierzanie wykonanie zwraca

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

Chociaż metoda opisana w odpowiedzi na wyżej połączonego pytanie, będąc najszybszym z książki kucharskiej Pythona znajduje się poniżej

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

Po uruchomieniu daje

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

Moje pytanie brzmi: dlaczego ludzie mówią o powyższym z książki kucharskiej, która jest stosunkowo złożona jako idealny generator główny?

Answer 1

Powinieneś używać tylko "postponed" variant of that algorithm. Porównywanie kodu test run do 10 i 20 milionów górna granica, jako

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

z drugą, run at odpowiednie Figury 664579 i 1270607 liczb pierwszych w produkcji, jak

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

wykazuje swoją wykonujących kod "only" 3.1x ... 3.3x razy szybszy. :) Nie36x razy szybciej, ponieważ czasy pokazują się z jakiegoś powodu.

Nie sądzę, aby ktokolwiek twierdził, że to "idealny" generator główny, tylko że jest koncepcyjnie czysty i przejrzysty. Wszystkie te funkcje pierwszej generacji są naprawdę zabawkami, prawdziwe rzeczy pracują z bardzo dużymi liczbami, i tak za pomocą zupełnie innych algorytmów.

Tutaj, w dolnym zakresie, liczy się złożoność czasowa algorytmu, która powinna wynosić około ~ n^(1+a), a < 0.1...0.2empirical orders of growth, którą oba wydają się być rzeczywiście. Posiadanie generatora zabawek z rzędami wzrostu ~ n^1.5 lub nawet ~ n^2 nie jest po prostu zabawą.

Answer 2

przerabiałem swój kod, aby pasowały do ​​głównego porównania sito scenariusza @unutbu na Fastest way to list all primes below N następująco:

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] 

Na moim MBPro i7 skrypt jest szybkie obliczenie wszystkie liczby pierwsze < 1000000, ale faktycznie 1,5 razy wolniej niż rwh_primes2, rwh_primes1 (1.2), rwh_primes (1.19) i primeSieveSeq (1.12) (@andreasbriese na końcu strony).