循環次數問題的效率（解釋與編譯語言？）

Question

假設你必須使用2甚至3個循環進行計算。直觀地說，有人可能會認爲用單循環來做這件事情會更有效率。我想一個簡單的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進行了簡化）。也就是說，如果我把所有東西都摺疊成一個單一的循環，我將不得不從另一個數組的大小介於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 

如此看來3個嵌套循環更有效，因爲我花一段時間在case1創建陣列b。所以我不確定我是以最有效的方式創建這個數組，但是把它放在一邊，它是否真的爲摺疊循環付出了代價？我在這裏使用Python，但編譯語言如C++呢？在這種情況下編譯器是否做了一些優化單循環？或者另一方面，當你有多個嵌套循環時，編譯器是否做了一些優化？

Answer 1

這就是爲什麼單迴路功能需要據說長於應該

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 

Answer 2

你的情況很簡單，各種優化可能會做很多。對於更高效的數組，可以使用numpy，也可以使用pypy以獲得更好的JIT優化程序或其他各種各樣的功能。

通過dis模塊查看字節碼可以幫助您瞭解底層模式下發生的情況並進行一些微觀優化，但是一般來說，如果您執行一個循環或嵌套循環（如果您的內存訪問模式對於CPU來說有點可預測。如果不是，它可能會有很大的不同。

Python有一些便宜的字節碼和其他比較昂貴的字節碼。函數調用比簡單的添加要昂貴得多。與創建新對象和其他各種東西一樣。所以通常的優化是將循環移到C，這有時是itertools的好處之一。

一旦處於C級別，它通常歸結爲：避免在緊密循環中使用syscalls/mallocs（），具有可預測的內存訪問模式並確保您的算法對緩存友好。

因此，如果由於大量的內存分配和緩存訪問而導致N的值較大，那麼上述算法在性能上可能會出現大幅變化。

但是，對於上述特定問題，最快的方法是找到函數的封閉形式，因爲必須有一個更簡單的公式來計算'c'的最終值，所以對於該函數進行迭代似乎是浪費。像往常一樣，先進行最佳算法，然後再進行微型優化。

例如Wolfram Alpha的告訴你，你可以代替兩個循環使用，有可能是所有三個一個封閉的形式，但阿爾法沒有告訴我...

def case3(n): 
    c = 0 
    for j in range(n): 
     c += (j* n^2 *(n+1)^2))/4 
    return c