Python代碼迴路速度比較

Question

爲什麼這條線的Python

yy = [sum(y[i:i+5])/5. for i in range(len(y)-4)] 

跑得比以下（等效）代碼快20倍？

for i in xrange(0,len(y)-4):  
    yy = np.append(yy, sum(y[i:i+5])/5.) 

其中y是大量的實數。 這裏真正發生了什麼？ 非常感謝。

Answer 1

這兩個代碼是而不是等效。正確的對應版本是：

yy = [] 
for i in range(0,len(y)-4):  
    yy.append(sum(y[i:i+5])/5.) 

這需要大約在同一時間：

In [10]: y = [1.0] * 100000 

In [11]: %timeit [sum(y[i:i+5])/5. for i in range(len(y)-4)] 
10 loops, best of 3: 49.6 ms per loop 

In [12]: %%timeit yy = [] 
    ...: for i in range(0,len(y)-4):  
    ...:  yy.append(sum(y[i:i+5])/5.) 
    ...: 
10 loops, best of 3: 55.1 ms per loop 

的問題是調用numpy.append比list.append慢得多。 這可能是由於numpy.append正在創建副本並將其返回，因爲每個插入。 第一次插入成本2（爲1個元素分配空間並將其複製到那裏）。秒的成本爲3（爲2個元素分配空間，複製孤立元素和新元素）。第三個成本4（分配3，複製2個元素和新的元素）。等

這意味着算法突然變得O(n^2)，而這是O(n)使用python list小號，因爲他們做的不複製爲每append整個列表。它們足夠聰明，可以分配更多內存來容納更多元素。

此外，作爲一般規則，numpy確實不是閃耀爲單元素訪問。在這種情況下，它實際上是比純python慢​​，因爲它必須始終在機器數據類型和python對象之間進行轉換。嘗試對操作進行矢量化，您將看到大幅加速。

Answer 2

numpy旨在執行向量化操作：如果您必須保持呼叫numpy.append，每次調用的開銷將使其不值得。

在numpy中執行此操作（滾動方式）的正確方法是對其進行矢量化，例如使用convolve函數（感謝@askewchan提供的建議）。在這種情況下，它比列表理解更快遠：

import timeit 
import numpy as np 

y = np.random.normal(0, 1, 10000) 

print timeit.timeit("np.convolve(y, np.ones(5)/5, mode='valid')", 
        setup = "from __main__ import y; import numpy as np", 
        number=100) 

print timeit.timeit("[sum(y[i:i+5])/5. for i in range(len(y)-4)]", 
        setup = "from __main__ import y", 
        number=100) 

在我的機器中，numpy的量化方案的100次迭代需要0.03秒，而列表理解需要6.56秒。