python - 为什么列表求和(有时)比 itertools.chain 快？

Question

我在这里通过使用它来“展平”列表列表来回答几个问题:

>>> l = [[1,2,3],[4,5,6],[7,8,9]]
>>> sum(l,[])

它工作正常并产生:

[1, 2, 3, 4, 5, 6, 7, 8, 9]

尽管有人告诉我 sum 运算符执行 a = a + b ，但性能不如 itertools.chain

我计划的问题是“为什么它可以在列表上被阻止在字符串上”，但我在我的机器上做了一个快速基准比较 sum 和 itertools.chain.from_iterable 在相同的数据上:

import itertools,timeit

print(timeit.timeit("sum(l,[])",setup='l = [[1,2,3],[4,5,6],[7,8,9]]'))
print(timeit.timeit("list(itertools.chain.from_iterable(l))",setup='l = [[1,2,3],[4,5,6],[7,8,9]]'))

我做了好几次，我总是得到与下面相同的数字:

0.7155522836070246
0.9883352857722025

令我惊讶的是，chain - 在对我的答案的多条评论中，每个人都推荐超过 sum 的列表 - 速度要慢得多。

在 for 循环中迭代时仍然很有趣，因为它实际上并没有创建列表，但是在创建列表时，sum 获胜。

那么当预期结果是 list 时，我们是否应该放弃 itertools.chain 并使用 sum ？

编辑:感谢一些评论，我通过增加列表数量进行了另一次测试

s = 'l = [[4,5,6] for _ in range(20)]'
print(timeit.timeit("sum(l,[])",setup=s))
print(timeit.timeit("list(itertools.chain.from_iterable(l))",setup=s))

现在我得到相反的结果:

6.479897810702537
3.793455760814343

Answer 1

您的测试输入很小。在这些规模下，sum 版本可怕的 O(n^2) 渐近运行时间是不可见的。时间由常数因子决定，sum 有一个更好的常数因子，因为它不必通过迭代器工作。

有了更大的列表，很明显 sum 根本不是为这种事情设计的:

>>> timeit.timeit('list(itertools.chain.from_iterable(l))',
...               'l = [[i] for i in xrange(5000)]; import itertools',
...               number=1000)
0.20425895931668947
>>> timeit.timeit('sum(l, [])', 'l = [[i] for i in xrange(5000)]', number=1000)
49.55303902059097