为什么列表推导比生成器表达式更快？

Question

为什么列表推导比生成器表达式更快？

16

不确定标题是否使用了正确的术语。

如果你需要比较两个字符串（A，B）中的字符，并计算B中与A匹配的字符数：

sum([ch in A for ch in B])

在 %timeit 方面更快

sum(ch in A for ch in B)

我理解第一个会创建一个布尔值列表，然后将1的值相加。

第二个是一个生成器。我不清楚它内部在做什么，以及为什么速度较慢？

谢谢。

使用%timeit测试结果进行编辑:

10个字符

生成器表达式

列表

10000次循环，3次中最好的:每次112微秒

10000次循环，3次中最好的:每次94.6微秒

1000个字符

生成器表达式

列表

100次循环，3次中最好的:每次8.5毫秒

100次循环，3次中最好的:每次6.9毫秒

10,000个字符

生成器表达式

列表

10次循环，3次中最好的:每次87.5毫秒

10次循环，3次中最好的:每次76.1毫秒

100,000个字符

生成器表达式

列表

1次循环，3次中最好的:每次908毫秒

1次循环，3次中最好的:每次840毫秒

- Chris94549

1

这些字符串有多长？生成器是数据惰性的，这可能会增加一些开销，对于短字符串来说，这个开销可能比不复制数据所节省的更大。 - millimoose

因为Python非常擅长创建列表。 - juanpa.arrivillaga

哼，即使使用长度为10000000的字符串，列表版本也比生成器版本更快... 我也很好奇它们之间的速度差异。 - jkr

从渐近的角度来看，它们似乎正在收敛。最终，必须进行两次遍历和构建列表的成本可能会超过更昂贵的生成器遍历。 - chepner

2个回答

1

生成器通常比列表推导式慢，生成器的整个意义在于其内存效率，因为它们通过以惰性方式创建每个项目来产生它们（仅在实际需要时）。它们优先考虑内存效率而不是速度。

- Andreas

我正在尝试理解在这个上下文中它的含义。sum（列表推导式）首先生成一个布尔列表，然后对1进行求和。生成器表达式有什么不同？ - Chris94549

1

在我对生成器的理解中，它们需要多次调用 next 方法，这可能会使它们变慢（但并非总是如此），请参见此处：生成器使用 next 方法，如下所示： https://www.python.org/dev/peps/pep-0289/#the-details 因此，像字符串这样更长的可迭代对象会导致更多的 next 调用，从而降低速度。 - Andreas

1

我在 Stack Overflow 上找到了一个更详细的解释：https://dev59.com/WWct5IYBdhLWcg3wmOng - Andreas

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

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

- Mario Ishac · Accepted Answer

我查看了每个构造的反汇编代码（使用dis）。我通过声明这两个函数来完成：

def list_comprehension():
    return sum([ch in A for ch in B])

def generation_expression():
    return sum(ch in A for ch in B)

然后对每个函数调用 dis.dis。

对于列表推导式：

 0 BUILD_LIST               0
 2 LOAD_FAST                0 (.0)
 4 FOR_ITER                12 (to 18)
 6 STORE_FAST               1 (ch)
 8 LOAD_FAST                1 (ch)
10 LOAD_GLOBAL              0 (A)
12 COMPARE_OP               6 (in)
14 LIST_APPEND              2
16 JUMP_ABSOLUTE            4
18 RETURN_VALUE

对于生成器表达式：

 0 LOAD_FAST                0 (.0)
 2 FOR_ITER                14 (to 18)
 4 STORE_FAST               1 (ch)
 6 LOAD_FAST                1 (ch)
 8 LOAD_GLOBAL              0 (A)
10 COMPARE_OP               6 (in)
12 YIELD_VALUE
14 POP_TOP
16 JUMP_ABSOLUTE            2
18 LOAD_CONST               0 (None)
20 RETURN_VALUE

实际求和的反汇编代码如下:

 0 LOAD_GLOBAL              0 (sum)
 2 LOAD_CONST               1 (<code object <genexpr> at 0x7f49dc395240, file "/home/mishac/dev/python/kintsugi/KintsugiModels/automated_tests/a.py", line 12>)
 4 LOAD_CONST               2 ('generation_expression.<locals>.<genexpr>')
 6 MAKE_FUNCTION            0
 8 LOAD_GLOBAL              1 (B)
10 GET_ITER
12 CALL_FUNCTION            1
14 CALL_FUNCTION            1
16 RETURN_VALUE

但这个 sum 反汇编在两个示例之间是常量，唯一的区别是加载 generation_expression.<locals>.<genexpr> vs list_comprehension.<locals>.<listcomp>（因此只是加载了不同的本地变量）。

前两个反汇编之间的不同字节码指令是列表推导式的 LIST_APPEND vs. 生成器表达式的 YIELD_VALUE 和 POP_TOP 的连接。

我不会假装我知道 Python 字节码的内在机制，但我从中得出的结论是生成器表达式被实现为一个队列，在生成值后弹出。这种弹出不必发生在列表推导中，这使我相信使用生成器将会有一些开销。

现在这并不意味着生成器总是会更慢。生成器擅长于节省内存，因此会有阈值 N，使得在此阈值之前列表推导性能略优（因为内存使用不成问题），但在此阈值之后，生成器将显著表现更好。