为什么itertools.chain比扁平化列表推导更快？

Question

为什么itertools.chain比扁平化列表推导更快？

pythonlist-comprehensionpython-itertoolsflatten

16

在这个问题的评论讨论中提到，虽然将一系列字符串连接起来只需使用''.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 10 x64上测试了Python 3.6.3，如果有关联。

编辑：

看来最快的方法毕竟是对每个列表调用空列表的.extend方法，就像@zwer提出的那样，这可能是因为它按“块”而不是按单个元素处理数据。

- jdehesa

list(x for y in lsts for x in y) 表达的意思是什么？ - Peter Wood

2

我的猜测是列表推导式在Python空间中执行某些表达式评估，而itertools变体没有执行任何表达式评估(它只是完全在C空间中生成东西)。 - mgilson

1

@jdehesa 与直接委托给C的函数相比，由LCs生成的字节码产生了巨大的差异。（https://ideone.com/zYcKZw） - Ashwini Chaudhary

1

如果有C语言经验的人能深入研究一下这个差异，那将非常有用。可能与内存分配有关，但只是猜测。 - jpp

1

顺便提一下，相关问题仍未得到回答：https://dev59.com/zlcO5IYBdhLWcg3w1Eym - Right leg

显示剩余12条评论

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- FHTMitchell · Accepted Answer

这里是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解包生成器（而不是C中的LIST_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