Python列表推导是否会在每次迭代时附加？

Question

我试图理解Python中列表推导的性能,以及使用它们与循环创建列表的权衡.使用for循环将元素附加到列表的已知性能成本之一是在每次迭代时它是O(k)(其中k是列表的长度),因为append需要到达列表的末尾添加一个额外的元素.

这对列表推导有什么用？在每次迭代时,它是否需要到达新列表的末尾以附加新元素？

# For loop:
# O(n*k) (k=number of elements currently in list) time complexity:
new_list = []
for i in range(n): # O(n)
  new_list.append(i) # O(k) 

# List comprehension:
new_list = [i for i in range(n)] # Is this O(n)? 

我搜索过Python文档,Stack Overflow和其他网站,但无法找到有关此内容的任何信息.关于列表推导的更多更高级别的信息有很多资源,但没有类似的具体内容.

如果您无法提供答案,请指导我,或者告诉我如何查看实际的基础Python列表理解代码,以便我可以自己做这个？

Answer 1

附加到列表是否摊销 O(1)而不是O(k); 列表实现为可变长度数组,而不是链接列表.复杂性适用于for具有my_list.append调用和列表推导的循环(其中,扰乱警报,也附加).

所以在这两种情况下.复杂性是O(N).

列表推导通常表现更好,因为它们专门做一件事: 创建列表.为它们生成的字节码是特定的.(参见LIST_APPEND字节码)

另请注意,列表推导(如for循环)不一定会在每次迭代时附加.if通常使用使用子句来过滤掉循环的迭代元素.

如果您想了解如何在CPython中实现list-comprehensions,您可以查看为它们生成的字节码,并浏览ceval.c为每个执行的操作.

dis在编译list-comprehension表达式之后可以看到字节码:

dis(compile('[i for i in range(10)]', '', 'exec').co_consts[0])
  1           0 BUILD_LIST               0
              2 LOAD_FAST                0 (.0)
        >>    4 FOR_ITER                 8 (to 14)
              6 STORE_FAST               1 (i)
              8 LOAD_FAST                1 (i)
             10 LIST_APPEND              2
             12 JUMP_ABSOLUTE            4
        >>   14 RETURN_VALUE

然后,扫描案例ceval.c或查看dis模块中的文档.