Pythonの高速素数篩

Question

私は、エラトステネスのふるいを使用してPythonで素数生成を行っています。そして、人々が比較的高速なオプションとして指摘する解決策は、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] 

の下に与えられているのpython料理から最速のものとして上記のリンクの質問への答えに記載された方法が

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.sieve_for_primes_to(1000000)" 
10 loops, best of 3: 19.5 msec per loop 

を返します。

実行時

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のみを使用してください。

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

は、コードの実行を示しているように、製造する他方、664579及び1270607素数のrun at対応する図面と

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

として、コードtest run MLN 10まで及び20の上限とを比較します"only" 3.1x ... 3.3x倍速。 :) 36x倍速く、タイミングが何らかの理由で表示されます。

「理想的な」プライムジェネレータであると主張した人はいないと思いますが、それは概念的にきれいでクリアなものです。これらの主要な生成関数はすべて実際にはおもちゃであり、実際のものは非常に大きな数値で動作しており、まったく別のアルゴリズムを使用しています。

ここでは、アルゴリズムの時間の複雑さが問題になります。アルゴリズムの時間の複雑さは約~ n^(1+a)、a < 0.1...0.2empirical orders of growthのようになります。どちらも実際にはそうであるようです。 ~ n^1.5、または~ n^2の成長の玩具発電機を持つことは、遊ぶのが楽しいことではありません。

Answer 2

私は次のようにFastest way to list all primes below N で@unutbuのプライムふるい比較スクリプトにフィットするようにコードを変換：

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では、スクリプトが速い< 1000000すべての素数を計算するが、実際には1.5倍遅くされI7 rwh_primes1（1.2）、rwh_primes（1.19）、primeSieveSeq（1.12）（ページ終了時に@andreasbriese）よりも大きい。