0

私はPython 2.7を使用しています

私が書いたエラトステネスのふるいerat()とerat2()の2つの実装のうち、erat2()には、erat2()の2回目の実行で比較的短い時間で結果が得られるという利点があります。

def erat2(num, isprime = [2]):
    if num > len(isprime) + 2:

        last_original = len(isprime) + 2
        isprime += [num for num in xrange(last_original ,num + 1)]

        for i in xrange(2,num + 1):
            if isprime[i-2]:
                if i <= last_original:
                    j = last_original//i + 1
                else:
                    j = 2
                temp = j * i
                while temp <= num:
                    isprime[temp-2] = 0
                    j += 1
                    temp = j * i

    return filter(lambda x: x != 0, isprime[:num - 1])

def erat(num):
    isprime = [num for num in xrange(2,num + 1)]
    for i in xrange(2,num + 1):
        if isprime[i-2]:
            j = 2
            temp = j * i
            while temp <= num:
                isprime[temp-2] = 0
                j += 1
                temp = j * i

    return filter(lambda x: x != 0, isprime)

import time
def t():
    num = 100000000
    i = 10
    while i < num:
        s = time.time()
        erat2(i)
        x = time.time() - s

        print "%10d %10f" %(i,x),

        s = time.time()
        erat(i)
        y = time.time() - s

        print " %10f" %(y)

        i *= 10

コードの 2 回目の実行で結果がはるかに高速になるという事実をサポートするために、いくつかのタイミング分析をここに示します。最初の列はテスト入力です。2列目はerat2()のタイミング、3列目はerat()のタイミングです。明らかなように、時間は 2 回目の実行で 7 分の 1 に短縮されます。

>>> t()
        10   0.000000    0.000000
       100   0.000000    0.000000
      1000   0.000000    0.000000
     10000   0.010000    0.010000
    100000   0.100000    0.110000
   1000000   1.231000    1.410000
  10000000  13.605000   15.081000
>>> t()
        10   0.000000    0.000000
       100   0.000000    0.000000
      1000   0.000000    0.000000
     10000   0.000000    0.020000
    100000   0.020000    0.140000
   1000000   0.170000    1.550000
  10000000   1.770000   15.752000

私が直面している問題は、このテスト入力の後にメモリ使用量が急増することです。

  • メモリ消費を減らすためにできる最適化はありますか?
  • このようなメモリの増加は、良い実装方法ですか?

編集：

関数erat()とerat2()の両方を少し最適化して、速度を上げました。ラムダ関数を

lambda x: x != 0

に

lambda x: x

同じ結果ですが、わずかに高速です。num = 10000000 で 1 秒速くなります。

EDIT2：

vartec と btilly の提案を使用しました。erat() を erat3() に改善しました。ここでは、タイミング チェックとともに改善された実装を示します。また、xrange 関数に式を配置すると、パフォーマンスが低下することもわかりました。パフォーマンスを向上させるために変数を追加しました。

def erat3(num):
    ''' Improves Sieve of eratosthenes '''
    #REQUIRES MATH MODULE
    if num < 2:
        return []

    isprime = [num for num in xrange(3,num + 1,2)]
    #temp2's expression placed in xrange function => performance-loss
    temp2 = int(math.sqrt(num)) + 1
    for i in xrange(3, temp2 ,2):
        if isprime[(i-3)/2]:
            j = 3
            temp = j * i
            while temp <= num:
                isprime[(temp-3)/2] = 0
                j += 2
                temp = j * i

    return [2] + filter(lambda x: x, isprime)

erat() と erat3() のタイミング

>>> t()
        10   0.000000    0.000000
       100   0.000000    0.000000
      1000   0.000000    0.000000
     10000   0.010000    0.010000
    100000   0.110000    0.040000
   1000000   1.241000    0.530000
  10000000  14.131000    6.111000
4

2 に答える 2

2

メモリとパフォーマンスの間にトレードオフがあるのは一般的です。どちらが重要かは、アプリケーションによって異なります。

この場合、作成するデータ構造がよりコンパクトになるように、BitVector (詳細についてはhttps://pypi.python.org/pypi/BitVectorを参照) を使用して軽減することをお勧めします。

また、この場合、特別なケース 2 と奇数ビットのみを格納すると、パフォーマンスが 2 倍になり、メモリが半分になりますが、コードが少し複雑になります。それはおそらく価値があります。

于 2013-06-03T19:48:20.893 に答える
0

isprime 配列には単一ビットを使用できます。Python は、ビットを操作するための非常に高速な方法を提供しませんが、1 つの簡単な方法は long を使用することです。

is_prime = (1 << num) - 1

これを使用して、数値がふるいにかけられたかどうかを確認します

is_prime & (1 << x)

2番目の関数に最小限の変更を加えて適用する方法は次のとおりです

def erat(num):
    isprime = (1 << num) - 1
    for i in xrange(2,num + 1):
        if isprime & (1 << i):
            j = 2
            temp = j * i
            while temp <= num:
                isprime &= (1 << num) - 1 - (1 << temp)
                j += 1
                temp = j * i
    return [i for i in range(num) if isprime&(1 << i)]

(1 << num)ローカル変数に保存して、何度もビルドすることを節約することはおそらく価値があります。@btilly が指摘しているように、少し余分な作業を行うことで、奇数のみを追跡することで半分のスペースを節約できます。

于 2013-06-03T19:48:57.283 に答える