为什么从前面填充数组很慢？

Question

在“用Python编写访谈的元素”一书中关于数组的章节中，提到从前面填充数组的速度很慢，所以看看是否可以从后面写值。

可能的原因是什么？

Answer 1

Python列出了标准Python实现CPython (至少在实际上从数据结构的角度实现为数组，而不是列表。中)。

但是，它们是动态分配和调整大小的，因此在Python列表的末尾追加实际上是可能的。这样做需要一些可变的时间:当附加项超出实际需要时，CPython会尝试分配额外的空间，这样就不需要为每个附加操作分配更多的空间。充其量，如果已经分配了空间，则追加是O(1)，而且由于它是数组，索引也是O(1)。

然而，需要很长时间才能在列表的开头添加一些内容，因为这需要移动所有数组值和是O(n)，就像弹出第一个元素一样。

Python语言设计人员决定调用这些数组列表而不是数组，这在一定程度上与标准术语相矛盾，我认为这是因为动态调整大小使得它们不同于标准的、固定大小的列表。

除非我搞错了，collections.deque实现了一个双链接列表，其中任何一方都添加了相应的O(1) /pops，以此类推。