1

私は Python を学ぼうとしていますが、自分のプライム シーブを開発することは、午後の興味深い問題になると思いました。これまでのところ、必要に応じて、オンラインで見つけたバージョンのエラトステネスのふるいをインポートするだけでした。これをベンチマークとして使用しました。

いくつかの異なる最適化を試した後、私はかなりまともなふるいを書いたと思いました:

def sieve3(n):
top = n+1
sieved = dict.fromkeys(xrange(3,top,2), True)
for si in sieved:
    if si * si > top:
        break
    if sieved[si]:
        for j in xrange((si*2) + si, top, si*2):       [****]
            sieved[j] = False
return [2] + [pr for pr in sieved if sieved[pr]]

最初の 1,000,000 個の整数を範囲として使用すると、このコードは正しい数の素数を生成し、ベンチマークよりも約 3 倍から 5 倍遅くなりました。諦めて背中を撫でようと思ってレンジを広げてみたらダメだった！

n = 1,000 -- Benchmark = 168 in 0.00010 seconds
n = 1,000 -- Sieve3 = 168 in 0.00022 seconds

n = 4,194,304 -- Benchmark = 295,947 in 0.288 seconds
n = 4,194,304 -- Sieve3 = 295,947 in 1.443 seconds

n = 4,194,305 -- Benchmark = 295,947 in 3.154 seconds
n = 4,194,305 -- Sieve3 = 2,097,153 in 0.8465 seconds

問題は の行にあると思いますが、[****]なぜそんなに壊れているのかわかりません。「j」の各奇数倍数を False としてマークすることになっており、ほとんどの場合は機能しますが、4,194,304 を超えるとふるいが破られます。（公平を期すために、たとえば10,000など、他のランダムな数字でも壊れます）。

変更を加えたところ、コードの速度が大幅に低下しましたが、実際にはすべての値で機能します。このバージョンにはすべての数字 (オッズだけでなく) が含まれていますが、それ以外は同一です。

def sieve2(n):
top = n+1
sieved = dict.fromkeys(xrange(2,top), True)
for si in sieved:
    if si * si > top:
        break
    if sieved[si]:
        for j in xrange((si*2), top, si):
            sieved[j] = False
return [pr for pr in sieved if sieved[pr]]

元の関数 (sieve3) が一貫して機能しない理由を理解してくれる人はいますか?

編集：Sieve3が「壊れる」と、sieve3（n）がn / 2を返すことを忘れていました。

4

3 に答える 3

2

ふるいでは、素数候補のループを順序付けする必要があります。問題のコードは、順序付けが保証されていない辞書のキーを列挙しています。代わりに、次のようにxrange、メインの sieve ループと戻り結果ループの辞書を初期化するために使用した を使用します。

def sieve3(n):
    top = n+1
    sieved = dict.fromkeys(xrange(3,top,2), True)
    for si in xrange(3,top,2):
        if si * si > top:
            break
        if sieved[si]:
            for j in xrange(3*si, top, si*2):     
                sieved[j] = False
    return [2] + [pr for pr in xrange(3,top,2) if sieved[pr]]
于 2013-04-20T00:10:20.160 に答える
1

これは、辞書のキーが順序付けられていないためです。偶然にfor si in sieved:も、昇順でキーをループすることがあります。最後の例では、 si が取得する最初の値は、ループをすぐに中断するのに十分な大きさです。

単純に使用できます: for si in sorted(sieved):

于 2013-04-20T00:04:16.073 に答える
0

さて、ランタイムを見てください。最後に示したケースのランタイムは、ベンチマークよりもほぼ 5 倍高速でしたが、通常は 5 倍遅かったことがわかります。これは危険信号です。すべての反復を実行していない可能性がありますか? (素数の数はほぼ 10 倍ですが、5 倍高速です...)

今はコードを詳しく調べる時間がありませんが、これがお役に立てば幸いです。

于 2013-04-19T23:01:01.570 に答える