为什么列表上的总和(有时)比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获胜.

那么当预期结果是什么时我们应该放弃itertools.chain并使用？sumlist

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

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

您的测试输入很小.在那些尺度上,版本的可怕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

Answer 2

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

• 对于小输入,时序由函数调用开销控制.呼叫两者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/