为什么列表上的总和(有时)比itertools.chain更快？

您的测试输入很小.在那些尺度上,版本的可怕O(n ^ 2)渐近运行时sum是不可见的.时间由常数因素支配,并且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

对于第一个问题,"令我惊讶的是,链条 - 在我的答案的几条评论中推荐所有人列出的总和 - 要慢得多",你观察到的时间有两个原因:

对于小输入,时序由函数调用开销控制.呼叫两者list并且chain.from_iterable比仅仅呼叫更昂贵sum.连接小输入的实际工作比进行函数和方法调用的工作要快.

对于较大的输入,a = a + b逻辑的预期二次行为将占主导地位.

对于你的另一个问题,"为什么它可以在字符串上被阻止的列表",答案是我们无法检测和报告所有二次情况,所以我们只报告一个用户最有可能偶然发现的情况偶然.

此外,''.join(list_of_strings)如果您还不了解它,那么解决方法更难以弄清楚.相比之下,列表的高性能解决方法更容易找到t=[]; for s in list_of_lists: t+=s.

使用非itertools替代方案,您应该能够通过简单的就地列表扩展来获得合理的性能:

result = []
for seq in list_of_lists:
    result += seq

循环以"python-speed"而不是"C-speed"运行,但是没有函数调用开销,没有额外的迭代层,更重要的是,列表连接可以利用已知的输入长度,所以它可以预先分配结果所需的空间(这称为__length_hint__).

另外一个想法,你永远不应该相信那些涉及逐渐增加列表的时间.内部逻辑使用realloc()在列表增长时调整列表大小.在时序套件中,环境是有利的,并且realloc通常可以就地扩展,因为没有其他数据在路上.但是,实际代码中使用的相同逻辑可能会执行得更糟,因为更多碎片的内存会导致realloc必须将所有数据复制到更大的空白区域.换句话说,时间可能根本不表示您关心的实际代码中的实际性能.

无论如何,sum()的主要原因是因为Guido van Rossum和Alex Martelli认为这对语言来说是最好的:

https://mail.python.org/pipermail/python-dev/2003-April/034853.html

http://code.activestate.com/lists/python-dev/51956/