Быстрое числовое сито в Python

Question

Я проходил генерацию простых чисел в python, используя сито Eratosthenes, и решения, которые люди рекламируют как относительно быстрый вариант, например, в нескольких из the answers to a question on optimising prime number generation in python, не просты и простые реализация, которую я имею здесь, соперничает с ними в эффективности. Моя реализация приводится ниже

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 выполнение возвращает

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

В то время как метод, описанный в ответ на вышеупомянутую связанный вопрос как самый быстрый из питона поваренной книги приведен ниже

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

При запуске дает

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

Мой вопрос: почему люди рекламируют вышеуказанное из книги повара, которая относительно сложна как идеальный первичный генератор?

Answer 1

Вы должны использовать только "postponed" variant of that algorithm. Сравнение кода test run до 10 и 20 млн верхнего предела, а

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

с другой, run at соответствующие показатели 664579 и 1270607 простых чисел, чтобы произвести как

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

показывает ваш код работает "только" 3.1x ... 3.3x раз быстрее. :) Не36x раз быстрее, так как ваши показания по каким-либо причинам.

Я не думаю, что кто-либо когда-либо утверждал, что это «идеальный» генератор, просто он концептуально чист и ясен. Все эти основные функции поколений - игрушки действительно, реальный материал работает с очень большими числами, используя всевозможные алгоритмы.

Здесь, в низком диапазоне, важна временная сложность алгоритма, который должен быть примерно ~ n^(1+a), a < 0.1...0.2empirical orders of growth, который, по-видимому, и есть. Наличие генератора игрушек с ~ n^1.5 или даже ~ n^2 порядков роста просто не забавно играть.

Answer 2

я трансформировал свой код, чтобы вписаться в прайм сценарий сравнения сито @unutbu в Fastest way to list all primes below N следующим образом:

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] 

На мой MBPro i7 сценарий быстро вычисления всех простых чисел < +1000000, но на самом деле в 1,5 раза медленнее чем rwh_primes2, rwh_primes1 (1.2), rwh_primes (1.19) и primeSieveSeq (1.12) (@ andreasbriese на конце страницы).