Python - 将多个列表中的元素 append 在一起的不同技术的相对性能是什么？

Question

关于将多个列表的所有元素 append 在一起的方法，有几个 stackoverflow 问题。我没有看到关于这些不同方法的相对性能的明确答案。此外，有时轻微的性能提升是以牺牲一些可读性为代价的，因此了解几种不同的方法会很有用。

任务:给定一个列表，其中包含任意数量的列表，每个列表包含任意数量的元素，形成一个包含所有元素的列表。首先是第一个列表中的所有元素，然后是第二个列表中的所有元素，等等。这是一个浅表追加:如果列表中有一个元素是列表，则不要提取那些单独的元素。例如

append_all([ [11, 12, 13], [21, 22], [31, [320, 329], 33, 34] ])

=>

[11, 12, 13, 21, 22, 31, [320, 329], 33, 34]

Answer 1

以下是将多个列表 append 在一起的几种方法的时间安排。

它们从最快到最慢显示。

Python 2.7(CPython - 在 Autodesk Maya 2014 中运行)、Windows 7 64 位、Intel Core i7-37770K @ 3.5 GHz。

import timeit
def p_timeit_min(msg, expr_str, number, setup):
    times = timeit.repeat(expr_str, number=number, setup=setup, repeat=3)
    print( '{0:18} => {1:6.3f}'.format( msg, min(times) ))

n = 1000
timeit.repeat('1+1', number=10000)   # "dummy" -- I'm in an environment where the first timeit call is erratic in performance.
setup_0 = ';  import operator;  L1 = list(range(n));  LL = [[10 * x + v for v in L1] for x in range(n)]'
print
p_timeit_min('map+extend 100', 'all = [];   map(all.extend, LL)', number=n, setup='n = 100'+setup_0)
p_timeit_min('for+extend 100', """
all = []
for L in LL:
    all.extend(L)
""", number=n, setup='n = 100'+setup_0)
p_timeit_min('extend 100', 'all = [];   [all.extend(L) for L in LL]', number=n, setup='n = 100'+setup_0)
# reduce with [] initializer, to avoid need to wrap each L in list().
p_timeit_min('reduce+iadd 100 []', 'all = reduce(operator.iadd, LL, [])', number=n, setup='n = 100'+setup_0)
p_timeit_min('filter extend 100', 'all = [];   filter( lambda x: False, iter(all.extend(L) for L in LL) )', number=n, setup='n = 100'+setup_0)
# WARNING: If remove "list()" wrapper around "list_", since this version isn't supplying a [] to accumulate the results, iadd will MODIFY the first element of LL, which may not be desired.
p_timeit_min('reduce+iadd 100 list()', 'all = reduce(operator.iadd, (list(list_) for list_ in LL))', number=n, setup='n = 100'+setup_0)
p_timeit_min('chain 100', 'all = list(itertools.chain(*LL))', number=n, setup='n = 100'+setup_0)
p_timeit_min('comprehension 100', 'all = [x for list_ in LL for x in list_]', number=n, setup='n = 100'+setup_0)
p_timeit_min('nested for append 100',
"""
all = []
for L in LL:
    for x in L:
        all.append(L)
""", number=n, setup='n = 100'+setup_0)
p_timeit_min('sum 100', 'all = sum(LL, [])', number=n, setup='n = 100'+setup_0)
print
p_timeit_min('map+extend 200', 'all = [];   map(all.extend, LL)', number=n, setup='n = 200'+setup_0)
p_timeit_min('for+extend 200', """
all = []
for L in LL:
    all.extend(L)
""", number=n, setup='n = 200'+setup_0)
p_timeit_min('extend 200', 'all = [];   [all.extend(L) for L in LL]', number=n, setup='n = 200'+setup_0)
p_timeit_min('reduce+iadd 200 []', 'all = reduce(operator.iadd, LL, [])', number=n, setup='n = 200'+setup_0)
p_timeit_min('filter extend 200', 'all = [];   filter( lambda x: False, iter(all.extend(L) for L in LL) )', number=n, setup='n = 200'+setup_0)
p_timeit_min('reduce+iadd 200 list()', 'all = reduce(operator.iadd, (list(list_) for list_ in LL))', number=n, setup='n = 200'+setup_0)
p_timeit_min('chain 200', 'all = list(itertools.chain(*LL))', number=n, setup='n = 200'+setup_0)
p_timeit_min('comprehension 200', 'all = [x for list_ in LL for x in list_]', number=n, setup='n = 200'+setup_0)
p_timeit_min('nested for append 200', """
all = []
for L in LL:
    for x in L:
        all.append(L)
""", number=n, setup='n = 200'+setup_0)
p_timeit_min('sum 200', 'all = sum(LL, [])', number=n, setup='n = 200'+setup_0)
print

输出:

map+extend 100     =>  0.062
for+extend 100     =>  0.064  ** within margin of error of first place, but slower on average
extend 100         =>  0.066
reduce+iadd 100 [] =>  0.063  ** see "200" case for reason this isn't placed higher in list.
filter extend 100  =>  0.078
reduce+iadd 100 list=> 0.105  ** ignore this - use the better "reduce" above.
chain 100          =>  0.127
comprehension 100  =>  0.250
nested for append 100=>0.672
sum 100            =>  1.424

对于 O(n) 阶算法，这些时间大约长 4 倍 -

“200”大小写为 200 x 200，因此元素总数是“100”大小写的 4 倍。

观察:前 5 个变体的性能明显优于 O(n) - 对于 4 倍多的元素，大约长 3 倍。这是因为每个列表都更长；子列表数量增加了 2 倍:

map+extend 200     =>  0.187
for+extend 200     =>  0.190
extend 200         =>  0.194
reduce+iadd 200 [] =>  0.204
filter extend 200  =>  0.217
reduce+iadd 200 list=> 0.311  ** ignore this - use the better "reduce" above.
chain 200          =>  0.426
comprehension 200  =>  0.931
nested for append 200=>2.676
sum 200            => 13.432

分析:如果每个列表都有很多元素，前四个解决方案并没有本质上的不同。

嵌套列表理解需要 4 倍的时间(作为最佳解决方案)。另一方面，总 # 个元素仍然是 O(n)。在许多情况下，这是一个足够小的时间值的 4 倍，无关紧要。

结论:如果这是您所处情况的性能关键因素，请将 list.extend 与任何循环方式一起使用，或 reduce(operator.iadd, LL, [])。亚军选择:itertools.chain 成本为 2 倍，或 [ .. for .. for .. ](嵌套列表理解)成本为 4 倍。

注意:这是一个测试，在一台机器上，在一个实现上，Python 2.7。

它假定您有列表并且您需要将结果作为列表；如果您有/需要序列/生成器/迭代器，这可能会改变平衡(可能有利于 itertools.chain)？

TODO:包含许多 SHORT 列表的测试。