4

1回の反復と多数の反復のパフォーマンスへの影響について疑問に思っています。私はPythonで働いています-それが答えに影響するかどうかはわかりません。

リスト内のすべての項目に対して一連のデータ変換を実行することを検討してください。

def one_pass(my_list):
    for i in xrange(0, len(my_list)):
        my_list[i] = first_transformation(my_list[i])
        my_list[i] = second_transformation(my_list[i])
        my_list[i] = third_transformation(my_list[i])
    return my_list

def multi_pass(my_list):
    range_end = len(my_list)
    for i in xrange(0, range_end):
       my_list[i] = first_transformation(my_list[i])

    for i in xrange(0, range_end):
       my_list[i] = second_transformation(my_list[i])

    for i in xrange(0, range_end):
       my_list[i] = third_transformation(my_list[i])

    return my_list

さて、読みやすさの問題は別として、厳密にはパフォーマンスの観点から、multi_pass よりも one_pass に本当の利点はありますか? ほとんどの作業が変換関数自体で行われると仮定すると、multi_pass の各反復にかかる時間は約 1/3 だけではないでしょうか?

4

4 に答える 4

5

違いは、読み取っている値とコードがCPUのキャッシュにある頻度です。

の要素my_listが大きいが、CPUキャッシュに収まる場合は、最初のバージョンが有益な場合があります。一方、変換の（バイト）コードが大きい場合は、データをキャッシュするよりも操作をキャッシュする方が適切な場合があります。

どちらのバージョンも、読みやすい方法よりもおそらく低速です。

def simple(my_list):
    return [third_transformation(second_transformation(first_transformation(e)))
            for e in my_list]

それがもたらすタイミング：

one_pass: 0.839533090591
multi_pass: 0.840938806534
simple: 0.569097995758
于 2012-11-15T22:11:41.673 に答える
2

複数の操作を含む 1 つのループ、またはそれぞれ 1 つの操作を実行する複数のループを簡単に作成できるプログラムを検討していると仮定すると、計算の複雑さは変わりません (たとえば、O(n) アルゴリズムはいずれにしても O(n) のままです)。

シングルパス アプローチの利点の 1 つは、ループの「簿記」を節約できることです。反復メカニズムがインクリメントしてカウンターを比較するか、「次の」ポインターを取得して null をチェックするか、または何でも、すべてを 1 回のパスで実行すると、実行量が少なくなります。操作がかなりの量の作業を行うと仮定すると (そして、ループ メカニズムがシンプルで直接的で、高価なジェネレーターなどをループすることはありません)、この「簿記」作業は、実際の作業よりも小さくなります。これは間違いなくマイクロ最適化であり、プログラムが遅すぎることがわかっていて、より重要な利用可能な最適化をすべて使い果たした場合を除き、実行すべきではありません。

もう 1 つの利点は、次の要素に移る前にすべての操作を繰り返しの各要素に適用すると、CPU キャッシュの恩恵を受ける傾向があることです。これは、同じアイテムに対する後続の操作で各アイテムがまだキャッシュ内にある可能性があるためです。複数のパスを使用すると、それはほとんど不可能になります (コレクション全体がキャッシュに収まらない限り)。Python では辞書による間接処理が非常に多いため、メモリ空間全体に散在するハッシュ バケットを読み取ることで、個々の操作ごとにキャッシュをオーバーフローさせることはおそらく難しくありません。したがって、これはまだマイクロ最適化ですが、この分析により、(まだ確実ではありませんが) 大きな違いを生む可能性が高くなります。

マルチパスの利点の 1 つは、ループの反復間で状態を維持する必要がある場合、シングルパス アプローチではすべての操作の状態を維持する必要があることです。これにより、CPU キャッシュが損なわれる可能性があります (各操作の状態が個別にパス全体のキャッシュに収まる可能性がありますが、すべての操作をまとめた状態ではありません)。極端な場合、この効果は、理論的にはプログラムがメモリに適合するかどうかの違いを生む可能性があります (私は、非常に大量のデータを噛んでいるプログラムで一度これに遭遇しました)。しかし、極端なケースでは、物事を分割する必要があることがわかっています。極端でないケースは、事前に行う価値のないマイクロ最適化です。

そのため、パフォーマンスは通常、シングルパスをわずかに優先しますが、場合によっては、シングルパスまたはマルチパスを大幅に優先する場合があります。ここから導き出せる結論は、すべてのプログラミングに適用される一般的なアドバイスと同じです。まず、最も明確で保守しやすく、プログラムに適切に対応できる方法でコードを記述します。ほぼ完成したプログラムを手に入れて、「十分に速くない」ことが判明した場合にのみ、コードのさまざまな部分のパフォーマンスへの影響を測定して、時間を費やす価値がある場所を見つけます。

パフォーマンス上の理由からシングルパスとマルチパスのどちらのアルゴリズムを作成するかを考えるのに費やされた時間は、ほとんどの場合無駄になります。したがって、無制限の開発時間を利用できる場合を除き、このことを前もって気にせず、必要に応じて対処することで、開発作業全体 (パフォーマンスを含む場合) から "最良の" 結果を得ることができます。

于 2012-11-15T23:30:51.687 に答える
1

個人的には、one_passオプションを好むことは間違いありません。それは間違いなくより良いパフォーマンスを発揮します。違いはそれほど大きくないというのは正しいかもしれません。Pythonはxrangeイテレータを非常にうまく最適化しましたが、それでも必要な3倍の反復を行っています。

于 2012-11-15T22:06:37.923 に答える
1

他のバージョンと比較して、どちらのバージョンでもキャッシュ ミスが減少する可能性があります。それらの変換関数が実際に何をするかによって異なります。

これらの関数に多くのコードがあり、(入力と出力以外に) 異なるデータ セットを操作する場合は、マルチパスの方が適している可能性があります。それ以外の場合は、現在のリスト要素がキャッシュされたままになる可能性が高く、ループ操作が 3 回ではなく 1 回だけ実行されるため、シングル パスの方が適している可能性があります。

これは、実際の実行時間を比較することが非常に役立つ場合です。

于 2012-11-15T22:05:31.137 に答える