python-2.7 - 为什么 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 允许通过改变现有 s 列表来执行操作，而s = s + arr 必须构造一个新列表，复制旧列表的缓冲区。

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

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

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