7

私はエラトステネスのふるいを使用してpythonで素数生成を行ってきました.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 -m timeit -n10 -s "import euler" "euler.sieve_for_primes_to(1000000)"
10 loops, best of 3: 19.5 msec per loop

上記のリンクされた質問への回答で、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.get_primes_erat(1000000)"
10 loops, best of 3: 697 msec per loop

私の質問は、理想的な素数ジェネレーターとして比較的複雑なクックブックから上記を宣伝するのはなぜですか?

4

2 に答える 2

10

次のように、コードを @unutbu at Fastest way to list 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 を高速に計算しますが、実際には rwh_primes2、rwh_primes1 (1.2)、rwh_primes (1.19)、および primeSieveSeq (1.12) よりも 1.5​​ 倍遅くなります (ページ末尾の @andreasbriese)。

于 2013-09-25T06:18:24.993 に答える
3

そのアルゴリズムの「延期された」バリアントのみを使用する必要があります。コードテストの実行を最大 10 万と 20 万の上限まで比較すると、次のようになります。

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

もう 1 つは、664579 と 1270607 の素数の対応する数字で実行して、次のように生成します。

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

「のみ」3.1x...3.3x倍高速に実行されているコードを示します。:)何らかの理由でタイミングが表示されるように、36倍高速ではありません。

これが「理想的な」素数生成器であると主張した人は誰もいなかったと思いますが、概念的にクリーンで明確なものであるというだけです。これらの素数生成関数はすべて実際にはおもちゃです。実際のものは非常に大きな数で動作し、とにかくまったく異なるアルゴリズムを使用しています.

ここで低い範囲で問題になるのは、アルゴリズムの時間の複雑さです。これは約~ n^(1+a)、a < 0.1...0.2 経験的な成長の順序であり、どちらも実際にそうであるように見えます。おもちゃのジェネレーターに成長の順序を付け~ n^1.5たり、さらに~ n^2は成長させたりすることは、遊んでいて楽しいものではありません。

于 2013-04-16T00:37:13.073 に答える