4

2 つまたは 3 つのループを使用して計算を実行する必要があるとします。直感的には、これを 1 つのループで行う方が効率的であると思うかもしれません。簡単なPythonの例を試しました：

import itertools
import timeit

def case1(n):
    c = 0
    for i in range(n):
        c += 1
    return c

def case2(n):
    c = 0
    for i in range(n):
        for j in range(n):
            for k in range(n):
                c += 1
    return c

print(case1(1000))
print(case2(10))

if __name__ == '__main__':
    import timeit

    print(timeit.timeit("case1(1000)", setup="from __main__ import case1", number=10000))

    print(timeit.timeit("case2(10)", setup="from __main__ import case2", number=10000))

このコードの実行:

$ python3 code.py 
1000
1000
0.8281264099932741
1.04944919400441

したがって、実質的に 1 ループの方が効率がよいようです。ただし、配列内の値を使用する必要があるため、問題には少し異なるシナリオがあります (次の例では、range簡略化のために関数を使用しています)。つまり、すべてを 1 つのループにまとめると、サイズが 2 ～ 10 要素の別の配列の値から拡張配列を作成する必要があります。

import itertools
import timeit

def case1(n):

    b = [i * j * k for i, j, k in itertools.product(range(n), repeat=3)]
    c = 0
    for i in range(len(b)):
        c += b[i]
    return c

def case2(n):

    c = 0
    for i in range(n):
        for j in range(n):
            for k in range(n):
                c += i*j*k
    return c

print(case1(10))
print(case2(10))

if __name__ == '__main__':
    import timeit

    print(timeit.timeit("case1(10)", setup="from __main__ import case1", number=10000))

    print(timeit.timeit("case2(10)", setup="from __main__ import case2", number=10000))

私のコンピューターでは、このコードは次の場所で実行されます。

$ python3 code.py 
91125
91125
2.435348572995281
1.6435037050105166

bで配列を作成するのに時間がかかるため、3つのネストされたループの方が効率的であるようcase1です。したがって、この配列を最も効率的な方法で作成しているかどうかはわかりませんが、それはさておき、ループを単一のものに折りたたむことは本当に報われますか? ここでは Python を使用していますが、C++ などのコンパイル済み言語はどうでしょうか。この場合、コンパイラは単一のループを最適化するために何かをしますか? あるいは、ネストされたループが複数ある場合、コンパイラは何らかの最適化を行いますか?

4

2 に答える 2

2

これが、単一のループ関数が必要以上に長くかかる理由です

b = [i * j * k for i, j, k in itertools.product(range(n), repeat=3)]

関数全体を次のように変更するだけで

def case1(n, b):
    c = 0
    for i in range(len(b)):
        c += b[i]
    return c

timeit を返します:

case1 : 0.965343249744
case2 : 2.28501694207
于 2015-06-07T18:07:41.573 に答える
2

あなたのケースは、さまざまな最適化がおそらく多くのことを行うほど単純です。numpyより効率的な配列、おそらくよりpypy優れた JIT オプティマイザー、またはその他のさまざまなもののためです。

モジュールを介してバイトコードを見ると、内部でdis何が起こっているかを理解し、いくつかのマイクロ最適化を行うのに役立ちますが、一般に、メモリアクセスパターンがある程度予測可能である場合、1 つのループを実行するかネストされたループを実行するかは問題ではありません。 CPU。そうでない場合は、大きく異なる可能性があります。

Python には、安価なバイトコードと高価なバイトコードがあります。たとえば、関数呼び出しは単純な追加よりもはるかに高価です。新しいオブジェクトやその他のさまざまなものを作成する場合と同じです。したがって、通常の最適化はループを C に移動することです。これはitertools時々の利点の 1 つです。

C レベルになると、通常は次のようになります。タイトなループで syscalls/mallocs() を回避し、予測可能なメモリ アクセス パターンを持ち、アルゴリズムがキャッシュ フレンドリーであることを確認します。

したがって、N の値を大きくすると、メモリ割り当てとキャッシュ アクセスの量が原因で、上記のアルゴリズムのパフォーマンスが大幅に変化する可能性があります。

しかし、上記の特定の問題に対する最速の方法は、関数の閉じた形式を見つけることです。「c」の最終値を計算するためのはるかに単純な式が必要なため、それを繰り返すのは無駄に思えます。いつものように、マイクロ最適化を行う前に、まず最適なアルゴリズムを取得します。

たとえば、Wolfram Alpha は、2 つのループを次のように置き換えることができると言っています。おそらく 3 つすべてに閉じた形式がありますが、Alpha は教えてくれませんでした...

def case3(n):
    c = 0
    for j in range(n):
        c += (j* n^2 *(n+1)^2))/4
    return c
于 2015-06-07T18:40:14.337 に答える