3

私は次のプログラムを持っています：

def main():
    print "Running"
    primes = sieve(100000)
    print "Sieve is done"

def sieve(n):
    print "starting sieve"
    primes = []
    times = 0

    numbers = range(2, n):
    print "sieve array filled"

    while len(numbers) > 0:
        current = numbers[0]
        primes.append(current)
        numbers.remove(current)

        times = times + 1
        if (times % 10 == 0):
            print str(times) + "th prime is " + str(current)

        # Remove every multiple
        for i in numbers:
            if (i % current == 0):
                numbers.remove(i)

多数（たとえば1万）までのすべての素数を見つけるとき、出力を見て、プログラムがどれだけ進んでいるかを確認できるようにしたかったのです。そこで、10プライムごとに印刷することにしました。ただし、印刷する場合は、プログラムの最後まで待機して印刷します。印刷ステートメントの直後に追加しましたsys.stdout.flush()が、違いはありませんでした。次に、スクリプトを実行してみましたpython -u <file name>が、まったく違いはありませんでした。

これは私が出力として得るものです：

Running
starting sieve
sieve array filled

次に、約1分後、残りの出力が一度に表示されます。

バッファをオフにできないのはなぜですか？コードをできるだけ変更しないようにしています。

4

3 に答える 3

3

いくつかのことをテストしましたが、問題が実際に出力バッファリングであるかどうかはわかりません。それはアルゴリズムの動作にすぎません。currentループの上部近くで印刷してみてくださいwhile。初期の数値が処理されるまでに非常に長い時間がかかることがわかります。その後、numbersが短くなるにつれて、の新しい値のcurrent処理がはるかに速くなり、素数が表示され始めます。現れる。

試す：

while len(numbers) > 0:
    current = numbers[0]
    print current
    primes.append(current)
    numbers.remove(current)
于 2012-11-29T00:23:30.630 に答える
2

これが非常に遅い理由は、数値から要素を削除するループです。

    # Remove every multiple
    for i in numbers:
        if (i % current == 0):
            numbers.remove(i)

数値を削除するたびに、Pythonは、削除した数値の後にあるすべての要素を1か所元に戻す必要があります。すべての削除はO（n）*であり、O（n）の削除を行うため、このステップの各反復にはO（n ^ 2）の時間がかかります。

これをリスト内包表記に置き換えると、Pythonは古いリストから新しいリストを作成します（移動は必要ありません）。これはO（n）操作です。これが私がそのステップを行う方法です：

    # Remove every multiple
    numbers = [i for i in numbers if (i % current) != 0]

この変更により、コードの実行速度が大幅に向上します。5秒以内に完了し、出力バッファリングの問題はありません。

*ここにPythonリスト操作の時間計算量の素晴らしい表があります。

于 2012-11-29T00:38:28.493 に答える
0

sys.stdout.writeの代わりに使用してみてくださいprint。これは、でうまく機能するはずsys.stdout.flushです。

于 2012-11-29T00:10:17.840 に答える