python - 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 lists，因为它们不会为每个 复制整个列表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 秒。