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 个元素和新的元素）。ETC。

这意味着该算法突然变得O(n^2), 虽然它O(n)使用 python lists，因为它们不会为每个 复制整个列表append。它们足够聪明，可以分配更多内存来容纳更多元素。

此外，作为一般规则，对于单元素访问numpy并不适用。在这种情况下，它实际上比纯 python慢，因为它必须始终在机器数据类型和 python 对象之间进行转换。尝试将操作矢量化，您会看到速度大幅提升。