为什么 python 的内置 sum 函数在用于展平列表列表时速度很慢？

Question

当尝试使用 python 2.7 的内置sum函数展平列表列表时，我遇到了一些性能问题 - 不仅计算速度慢，而且迭代方法产生了更快的结果。

下面的简短代码似乎说明了这种性能差距：

import timeit

def sum1(arrs):
    return sum(arrs, [])

def sum2(arrs):
    s = []
    for arr in arrs:
        s += arr
    return s

def main():
    array_of_arrays = [[0] for _ in range(1000)]
    print timeit.timeit(lambda: sum1(array_of_arrays), number=100)
    print timeit.timeit(lambda: sum2(array_of_arrays), number=100)

if __name__=='__main__':
    main()

在我的笔记本电脑上，我得到输出：

>> 0.247241020203
>> 0.0043830871582

谁能向我解释一下为什么会这样？

Answer 1

您的sum2用途+=：

    for arr in arrs:
        s += arr

sum不使用+=。sum被定义为使用+. 不同之处在于，允许通过改变现有列表s += arr来执行操作，而必须构造一个新列表，复制旧列表的缓冲区。ss = s + arr

通过+=，Python 可以使用有效的列表调整策略，该策略需要与最终列表的大小成比例的复制量。对于每个N长度的列表K，这需要与 成正比的时间N*K。

对于+，Python 无法做到这一点。对于每个s = s + arr，Python 必须复制整个s和arr列表来构造新的s。对于每个N大小的列表K，复制所花费的总时间与 成正比N**2 * K，更糟糕。

因此，您几乎不应该使用sum连接序列。