Python列表理解是否会在每次迭代时追加？

Question

我试图了解Python中列表理解的性能，以及使用它们与for循环创建列表的利弊。使用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文档、堆栈溢出和其他网站，但找不到任何相关信息。有很多资源可以获得关于列表理解的更高层次的信息，但是没有像这样具体的信息。在

如果你不能提供答案，你能告诉我，或者告诉我如何看实际的底层Python列表理解代码，这样我就可以自己做了吗？在

Answer 1

附加到列表的是摊销O(1)而不是O(k)；列表是作为可变长度数组而不是链表实现的。复杂度适用于带有my_list.append调用的for循环和列表理解（其中，spoiler alert，也追加）。在

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

列表理解通常表现得更好，因为专门做一件事：创建列表。为它们生成的字节码就是特定的。（请参阅^{}字节码）

还要注意，列表理解，比如for循环，不一定在每次迭代时追加。通常使用if子句筛选出循环遍历的iterable元素。在

---

如果您想了解列表理解是如何在CPython中实现的，那么可以查看为它们生成的字节码，并通过ceval.c扫描为每个字节执行的操作。在

编译列表理解表达式后，dis可以看到字节码：

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

然后，scan through the cases in ^{}或查看^{} module中的文档。在