2

次のプログラム (関数 prime 内) の実行時間は 110.726383227 秒です

関数（プライム）でラップせずに同じプログラムを実行すると、実行時間は222.006502634秒です

関数でラップすることで、パフォーマンスが大幅に向上しました。

このプログラムの効率を高める可能性はまだありますか?

# This is a program to find sum of prime numbers till 2 billion

def prime():
import time
start_time = time.clock()

num = 2
j=1
tot_sum = 0

for num in xrange(2,2000000): 
    count = 0
    for j in xrange(1,int(num**0.5)+1): # checking from 1 to sqrt(n)+1
        if(num % j == 0):
            count = count+1

    if(count == 1):
        tot_sum = tot_sum + num

print "total sum is %d" % tot_sum

print time.clock() - start_time, "seconds"
4

2 に答える 2

1

外部ライブラリなしで解決したい場合は、いくつかの明らかな改善を行うことができます:

def prime():
    import time
    start_time = time.clock()

    tot_sum = 2

    for num in xrange( 3, 2000000, 2 ): 
            isPrime = True
            for j in xrange(3, int( num ** 0.5 ) + 1, 2 ):
                if( num % j == 0 ):
                    isPrime = False
                    break

            if isPrime:
                tot_sum = tot_sum + num

    print "total sum is %d" % tot_sum

    print time.clock() - start_time, "seconds"

prime()

2 つを超える偶数をチェックせず、見つかった場合でもすべての除数をチェックしません。あなたの元のコードは私のマシンでは 172.924809 秒で実行され、私のマシンでは 8.492169 秒で実行されます。

外部ライブラリの使用が許可されている場合は、次のことをお勧めしgmpy2ます。

def prime():
    from gmpy2 import is_prime
    import time
    start_time = time.clock()

    print "total sum is %d" % (sum(filter(is_prime, xrange(3,2000000,2)))+2)

    print time.clock() - start_time, "seconds"

prime()

これは 1.691812 秒で実行されます

于 2013-10-13T19:25:07.760 に答える
0

これは、Python が変数を解決する方法に関係している可能性があります。大まかに言えば、関数を入力すると、python は新しい名前空間を作成します。これは基本的に、その関数にローカルなすべての変数にマップされます。次に、Python は名前空間を使用して、プログラマーがアクセスしているすべての変数の値を決定できます。変数名解決の順序は次のとおりです。

  • ローカル名前空間のルックアップ変数名
  • グローバル名前空間で変数名をルックアップ
  • Python のビルトインで名前を検索します。

ルックアップの実行にはコストがかかる可能性があり、Python での一般的なパフォーマンスのヒントは、まさにこの理由でローカル変数を使用することです。少なくとも、1 回ではなく 2 回のルックアップを回避できます。さらに、新しい python コンパイラは、追加の最適化を行って、ローカル名前空間への単一のルックアップさえも削除しているようですが、変数を即時値として扱います。

この最適化が名前空間のルックアップだけで発生するかどうかをテストする良い方法は、(私が知らない他の最適化を除いて) すべてのロジックを関数でラップし、使用しているすべての変数をグローバルにすることです。すべてが遅くなる場合は、名前空間の検索に時間がかかっていると推測できます。

于 2013-10-13T19:15:24.243 に答える