7

私は次のようにEratosthanesの簡単なふるいを実装しています：

# Generate all primes less than k
def sieve(k):
    s = [True] * k
    s[0] = s[1] = False
    for i in range(4, k, 2):
        s[i] = False

    for i in range(3, int(sqrt(k)) + 2, 2):
        if s[i]:            
            for j in range(i ** 2, k, i * 2):
                s[j] = False

    return [2] + [ i for i in range(3, k, 2) if s[i] ]

私は10M未満の素数を繰り返し生成することにより、このコードのベンチマークを行っています。

st = time()
for x in range(1000):
    rt = time()
    sieve(10000000)
    print "%3d %.2f %.2f" % (x, time() - rt, (time() - st) / (x + 1))

テストの実行ごとにかかる時間が著しく増加するため、私は混乱しています。

run   t  avg
  0 1.49 1.49
  1 1.79 1.66
  2 2.23 1.85
  3 2.72 2.07
  4 2.67 2.20
  5 2.87 2.31
  6 3.05 2.42
  7 3.57 2.56
  8 3.38 2.65
  9 3.48 2.74
 10 3.81 2.84
 11 3.75 2.92
 12 3.85 2.99
 13 4.14 3.07
 14 4.02 3.14
 15 4.05 3.20
 16 4.48 3.28
 17 4.41 3.34
 18 4.19 3.39
 19 4.22 3.43
 20 4.65 3.49

ただし、のすべてのインスタンスを変更すると、問題rangeがxrange解消されます。

run   t  avg
  0 1.26 1.26
  1 1.23 1.28
  2 1.24 1.27
  3 1.25 1.26
  4 1.23 1.26
  5 1.23 1.25
  6 1.25 1.25
  7 1.25 1.25
  8 1.23 1.25
  9 1.25 1.25
 10 1.24 1.25

なぜそうなのですか？それは本当にすべてのGCオーバーヘッドですか？20回の実行後に3倍遅くなるのは大変なようです...

4

1 に答える 1

1

これは（まだ）答えではありませんが、組織化された実験のコレクションにすぎません。

これは本当に魅力的です。Python のメモリ アロケータで非常に疑わしいことが起こっているようです。

テストケースを減らすための私の試みは次のとおりです。

def sieve(k):
    s = [True] * k

    for i in xrange(3, int(sqrt(k)) + 2, 2):
        for j in range(i ** 2, k, i * 2):
            s[j] = False

    return [ i for i in range(3, k, 2) if s[i] ]

st = time()
for x in range(1000):
    rt = time()
    sieve(10000000)
    print "%3d %.2f %.2f" % (x, time() - rt, (time() - st) / (x + 1))

を削除するかif s[i]、内側rangeをxrangeにするか、戻り値をジェネレーターにするか、またはpass内側のforループで (または にするs[j] = True) と、動作が消えて時間がフラットになることに注意してください。

Python のメモリ使用量は、関数が実行されるにつれて着実に増加し、最終的には横ばいになります (この時点で、実行時間も横ばいになり始め、初期値の約 250% になります)。

私の仮説は、(サイズが減少する) 多数の内部ranges と最終的な配列によって、何らかの最悪の場合のヒープの断片化が発生し、オブジェクトの割り当てを続行することが非常に困難になるというものです。

私が推奨するのは、縮小したテスト ケースを作成し、それをバグとして Python 開発者 (bugs.python.org) に報告することです。

于 2012-09-16T19:12:54.143 に答える