为什么itertools.chain比扁平化列表理解更快?

Question

在这个问题的评论中的讨论中提到，虽然连接字符串序列只需要''.join([str1, str2, ...])，但连接列表序列就像list(itertools.chain(lst1, lst2, ...))，尽管您也可以使用像[x for y in [lst1, lst2, ...] for x in y]这样的列表推导。令我惊讶的是，第一种方法始终比第二种方法快：

import random
import itertools
random.seed(100)
lsts = [[1] * random.randint(100, 1000) for i in range(1000)]
%timeit [x for y in lsts for x in y]
# 39.3 ms ± 436 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)
%timeit list(itertools.chain.from_iterable(lsts))
# 30.6 ms ± 866 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)
%timeit list(x for y in lsts for x in y)  # Proposed in comments
# 62.5 ms ± 504 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)
# Loop-based methods proposed in the comments
%%timeit
a = []
for lst in lsts: a += lst
# 26.4 ms ± 634 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)
%%timeit
a = []
for lst in lsts: a.extend(lst)
# 26.7 ms ± 728 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)

这不是数量级的差异，但也不能忽略不计。我想知道情况如何，因为列表理解通常是解决给定问题的最快方法之一。起初我认为也许itertools.chain对象会有一个len，list构造函数可以使用该来预分配必要的内存，但事实并非如此(不能在itertools.chain对象上调用len)。是以某种方式发生了一些自定义itertools.chain到list的转换，还是itertools.chain利用了其他机制？

在Windows 3.6.3 x10 x64上的Python 10中进行了测试，如果相关的话。

编辑：

正如@zwer所建议的那样，似乎最快的方法是对每个列表调用.extend一个空列表，可能是因为它适用于数据"块"而不是基于每个元素。

Answer 1

这是itertools.chain.from_iterable。即使你不懂 C，也不难阅读，你可以说出一切都在 c 级别发生(在用于在代码中生成列表之前)。

列表推导的字节码如下所示：

def f(lsts):
return [x for y in lsts for x in y]
dis.dis(f.__code__.co_consts[1])
2           0 BUILD_LIST               0
2 LOAD_FAST                0 (.0)
>>    4 FOR_ITER                18 (to 24)
6 STORE_FAST               1 (y)
8 LOAD_FAST                1 (y)
10 GET_ITER
>>   12 FOR_ITER                 8 (to 22)
14 STORE_FAST               2 (x)
16 LOAD_FAST                2 (x)
18 LIST_APPEND              3
20 JUMP_ABSOLUTE           12
>>   22 JUMP_ABSOLUTE            4
>>   24 RETURN_VALUE

这些是创建列表理解所涉及的所有 python 解释器操作。只需在 C 级别(chain年)进行所有操作，而不是让解释器跨过每个字节码步骤(在理解中)，就可以提高性能。

尽管如此，这种提升是如此之小，我不会担心它。这是python，可读性超过速度。

---

编辑：

对于列表包装生成器理解

def g(lists):
return list(x for y in lsts for x in y)
# the comprehension
dis.dis(g.__code__.co_consts[1])
2           0 LOAD_FAST                0 (.0)
>>    2 FOR_ITER                20 (to 24)
4 STORE_FAST               1 (y)
6 LOAD_FAST                1 (y)
8 GET_ITER
>>   10 FOR_ITER                10 (to 22)
12 STORE_FAST               2 (x)
14 LOAD_FAST                2 (x)
16 YIELD_VALUE
18 POP_TOP
20 JUMP_ABSOLUTE           10
>>   22 JUMP_ABSOLUTE            2
>>   24 LOAD_CONST               0 (None)
26 RETURN_VALUE

因此，解释器在运行按列表解压缩的生成器表达式时有类似数量的步骤要做，但正如您所期望的那样，让list解压缩生成器(而不是 CLIST_APPEND指令)的 python 级开销是减慢它的速度的原因。

dis.dis(f)
2           0 LOAD_CONST               1 (<code object <listcomp> at 0x000000000FB58B70, file "<ipython-input-33-1d46ced34d66>", line 2>)
2 LOAD_CONST               2 ('f.<locals>.<listcomp>')
4 MAKE_FUNCTION            0
6 LOAD_FAST                0 (lsts)
8 GET_ITER
10 CALL_FUNCTION            1
12 RETURN_VALUE
dis.dis(g)
2           0 LOAD_GLOBAL              0 (list)
2 LOAD_CONST               1 (<code object <genexpr> at 0x000000000FF6F420, file "<ipython-input-40-0334a7cdeb8f>", line 2>)
4 LOAD_CONST               2 ('g.<locals>.<genexpr>')
6 MAKE_FUNCTION            0
8 LOAD_GLOBAL              1 (lsts)
10 GET_ITER
12 CALL_FUNCTION            1
14 CALL_FUNCTION            1
16 RETURN_VALUE