Project Euler 10 - 最初のPythonコードが2番目のPythonコードよりもはるかに高速に動作するのはなぜですか？

Question

プロジェクトオイラーで10問題：

10以下の素数の和である2 + 3 + 5 + 7 = 17

が200万下に全ての素数の和を探します。

私はこのスニペットを見つけました：

sieve = [True] * 2000000 # Sieve is faster for 2M primes 
def mark(sieve, x): 
    for i in xrange(x+x, len(sieve), x): 
     sieve[i] = False 

for x in xrange(2, int(len(sieve) ** 0.5) + 1): 
    if sieve[x]: mark(sieve, x) 

print sum(i for i in xrange(2, len(sieve)) if sieve[i]) 

は3秒間に実行here を発表しました。

私はこのコードを書いた：私のコード（1秒）がはるかに遅い理由

def isprime(n): 
    for x in xrange(3, int(n**0.5)+1): 
     if n % x == 0: 
      return False 
    return True 

sum=0; 
for i in xrange(1,int(2e6),2): 
    if isprime(i): 
     sum += i 

を私は理解していませんか？

Answer 1

あなたのアルゴリズムは、素数性のために2からN（N = 2000000）のすべての数を個別にチェックしています。

スニペット1は、約2200年前に発見されたsieve of Eratosthenesアルゴリズムを使用します。これは、すべての番号をチェックしませんが ：

• は2から2000000
• へのすべての数字の「ふるい」は、その後のすべての倍数を削除し、最初の数は（2）、プライムとしてマーク検索しますふるい。
• 次に、削除されていない番号（3）を見つけ、それをプライムとしてマークし、すべての倍数をシーブから削除します。
• 次に、削除されていない番号（5）を見つけ、それをプライムとしてマークし、すべての倍数をシーブから削除します。
• ...
• 素数1409が見つかるまで、すべての倍数をふるいから削除します。
• 1414〜= sqrt（2000000）までのすべての素数が見つかり、停止する
• 1415から2000000までの数字はチェックする必要はありません。削除されていないものはすべて素数です。

だからアルゴリズムはN.までのすべての素数を生成

お知らせそれはどの部門、追加のみ（いなくても、乗算、およびないそれはとても小さな数字で重要しかし、それは大きなとの可能性があることをしないこともの）。時間複雑度はO(n loglogn)で、アルゴリズムにはO(n^(3/2))（または@Daniel FischerがコメントしたようにO(n^(3/2)/logn)）というものがありますが、部門は乗算と同じであると仮定します。ウィキペディアから

（上記のリンク）の記事：

時間複雑ランダム・アクセス・マシン・モデルでは、O（n個のnをログログ）操作、prime harmonic seriesは漸近的log log nに近づいているという事実の直接的な結果です。

感謝を@machineyearning

Answer 2

最初のバージョンでは、範囲内のすべての素数が事前に計算され、sieve配列に格納されているため、解を見つけることは配列内の素数を追加する単純な問題です。それはmemoizationの形で見ることができます。

2番目のバージョンでは、範囲内の各数値をテストして、それが素数であるかどうかを確認します。前回の計算で既に多くの作業が繰り返されています。

結論として、最初のバージョンは値の再計算を避け、2番目のバージョンは何度も同じ操作を実行します。その数があることについて試験するとき、あなたのソリューションで

、数2は、各番号について試験する：

Answer 3

が簡単に違いを理解するために、それぞれの数は分圧器として使用される回数を考えてみてくださいプライム。道に沿って渡った番号は、次の番号ごとに分けられる可能性があります。

最初の解決策では、あなたが戻ってくることのない数字を踏んだら、あなたはいつもあなたが到達した場所から前に進みます。ところで、可能と共通の最適化は、あなたが2をマークした後にのみ、奇数のために行くことです。

mark(sieve, 2) 
for x in xrange(3, int(len(sieve) ** 0.5) + 1, 2): 
    if sieve[x]: mark(sieve, x) 

あなたは一度だけ、各番号を見て、むしろ経由するよりも、前方にその乗算のすべてをクリアこの方法すべての可能な仕切りは、すべての前任者と各番号を何度も何度もチェックしており、ifというステートメントは、以前に遭遇した番号の繰り返し作業を防ぎます。

Answer 4

Óscarの回答によれば、アルゴリズムは多くの作業を繰り返します。

calls, count = 0, 0 
def mark(sieve, x): 
    global calls, count 
    calls += 1 
    for i in xrange(x+x, len(sieve), x): 
     count += 1 
     sieve[i] = False 

：他のアルゴリズムが節約どれだけの処理を確認するには、関数が呼び出された回数のトラックとループの反復のための総数を保つ mark()と isprime()機能、次の修正版を考えます

この新しい関数を使って最初のコードを実行すると、mark()が223回呼び出され、forループの合計で4,489,006（〜4.5百万）回の反復が行われることがわかります。私たちはあなたのコードに似た変更を加えた場合

calls, count = 0 
def isprime(n): 
    global calls, count 
    calls += 1 
    for x in xrange(3, int(n**0.5)+1): 
     count += 1 
     if n % x == 0: 
      return False 
    return True 

は、我々はisprime()は、forループの177492735（〜1.775億）の反復で1,000,000（100万）回呼び出されていることがわかります。

関数の呼び出しとループの繰り返しを計算することは、アルゴリズムがなぜ高速であるかを判断する決定的な方法ではありませんが、一般的にステップが少なくて済むため時間が大幅に短縮されます。