在每次迭代中附加python列表综合

Question

我正在尝试了解python列表综合的性能，以及使用它们与循环创建列表的权衡。使用for循环将元素附加到列表的已知性能成本之一是，在每次迭代中，它是o（k）（k是列表的长度），因为附加需要到达列表的末尾添加一个附加元素。

这对列表综合有效？在每次迭代中

# 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

附加到列表的 amortized O(1)而不是 O(k);列表被实现为可变长度数组，而不是链接列表。该复杂性既适用于具有my_list.append调用和列表 - 经验的for循环（扰流板警报，附加）。

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

列表 - 经验的表现通常更好，因为它们是专门做一件事的：创建列表。为它们生产的字节代码是特定的。（请参阅LIST_APPEND字节）

还要注意，列表的理解，例如for-loops，不一定会在每次迭代中附加。通常使用if子句来过滤您所浏览的峰值的元素。

---

如果您想查看如何在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

然后，扫描ceval.c中的案例或在dis模块中查看其文档。