0

長いリストを繰り返し処理する for ループ。リストを変更する反復を加速しようとしました(成功しませんでした)。コード：

from math import sqrt
def holeofStrainer():
    isPrime = [False, False] + [True]*999999
    for num in range(3, len(isPrime)):
        if isPrime[num] == False:
            continue
        else:
            for x in range(2, int(sqrt(num)) + 1):
                if num % x == 0:
                    isPrime[num] = False        
                    break
            else:          
                isPrime[num] = True       
                for item in range (2, int(1000001/num) + 2):
                    ple = item * num
                    if ple < len(isPrime):
                        isPrime[ple] = False  
    return(isPrime) 
print(holeofStrainer())

5 行目の目的は、不要な計算を省くことです。

14 ～ 17 行目で変更を加えます(エラトステネスのふるいに従い、素数の倍数の値を False に変更します)。これにより、5 行目の計算が増えることを回避します。

まとめ：

  1. ループ自体からループ反復リストを変更することは可能ですか?
  2. 答えが「はい」の場合、なぜ私のコードではうまくいかないのですか?
4

1 に答える 1

1

時期尚早の最適化、つまり、最初にコードを動作させずに高速なコードを構築しようとするケースに遭遇したことは間違いありません。

外側の for ループ

for num in isPrime:

数値やインデックス位置ではなく、 のTrueとのFalse値を反復します。isPrime

            for item in range (2, int(1000001/num) + 2):
                ple = item * num
                if ple < len(isPrime):
                    isPrime[ple] = False

Padraic Cunningham のコメントにもあるように、コードのこの部分が何を達成するのかわかりません。DRY 違反 (制限数の重複) もあります。

これをすべてきれいにすると、次のようになります

def holeofStrainer(nprimes):
    isPrime = [False, False] + [True] * (nprimes - 1)
    for num in (num for num, numIsPrime in enumerate(isPrime) if numIsPrime):                                            
        for x in xrange(2, int(sqrt(num)) + 1):                                                                           
            if num % x == 0:                 
                isPrime[num] = False
                break                      
     return isPrime

xrange()の代わりに を使用していることに注意してくださいrange()。これが python 2 のrange()場合、呼び出されたときに完全なリストが作成されます。これは、より大きな数の場合、非常に大きな問題になります。

holeofStrainer(1000000)ここを一周するのに約14秒かかります。これはおそらくより高速に実行できますが (たとえば、最初に奇数のみをチェックして格納することにより)、より高速な SO の動作バージョンが既に存在します。

于 2015-05-09T21:53:51.080 に答える