Python中列表的调整因子是什么？

Question

例如，Java 中的 ArrayList 的调整大小因子为2。当 ArrayList 包装的数组空间不足时，该数组的所有元素都会转移到一个新数组中，该新数组的大小是原始数组的两倍。

由于 Python 的列表/数组是天然动态的，它们的调整大小因子是多少？还是它们使用了其他的缩放方法？如果是这样，那么这种方法是什么？其渐进运行时间复杂度（大 O）是多少？

- TomLisankie

---

我已经在Python列表存储其值的位置在哪里？中描述了CPython的12.5％列表重新分配。 - wim

Java的ArrayList的调整大小因子是1.5而不是2：https://dev59.com/D2855IYBdhLWcg3wQx5L#52014409 - maplemaple

Answer 1

对于CPython，特别是在调整大小期间的过度分配是在objects/listobject.c中实现的。它被描述为“温和，但足以在系统realloc()性能不佳的情况下，在一长串appends()中提供线性时间摊销行为。”当需要增加列表大小时，它会增长到大约所需大小的112.5%。具体来说，实际大小为new_size + new_size >> 3 + (newsize < 9 ? 3 : 6)。

- nanofarad

---

注意：这严格来说只是当前版本的CPython（即参考解释器）的一个实现细节。过度分配的规则随着时间的推移已经发生了变化，未来仍可能会发生变化，并且在每个非CPython解释器上可能会有所不同（例如Jython可能合理地在幕后使用ArrayList并继承其行为）。没有任何记录的语言特性需要任何特定的实现。依赖特定的调整大小算法是一个糟糕的想法。 - ShadowRanger

不过，即便如此，这个答案对于概念理解和复杂性分析来说仍然非常有用。 - flow2k

@ShadowRanger 在哪里可以找到当前安装的Python版本中这种行为的文档？我怎么知道我具体有哪个版本？ - Gulzar

@Gulzar：你不需要这样做。它在源代码中已经提到了，也许是设置它的错误跟踪器条目。这不是语言本身的重要内容，只是一个实现细节，记录它会束缚他们的手脚，而没有提供任何有用的好处。CPython是参考解释器，所以除非你特意安装了其他解释器，否则它就是你所拥有的。 - ShadowRanger

Answer 2

回答你的另一个问题：向ArrayList或类似对象的末尾添加元素只需要平摊O(1)时间，只要存在任何因子k > 1，使得重新分配总是生成比之前大k倍的数组。

实际使用的因子并不重要，只要它比一大即可。其他重新分配方案可能具有不同的复杂度。例如，如果重新分配添加了固定数量，则添加元素需要平摊O(N)时间。

这就是为什么所有专业编写的动态增长数组都会按照某个因子增长。该因子提供了浪费空间比例（(k-1)/k）的固定上限，同时也换取了在一系列添加操作中每个元素平均复制次数的固定上限。

假设您使用因子k，并且刚刚执行了第N次重新分配。这意味着您已经添加了约k^N个元素。您复制了多少个元素？让它等于C。然后： C = k^(N-1) + k(N-2) + ... + 1 kC - C = k^N + k^(N-1) - k^(N-1) + k^(N-2) - k^(N-2) ... - 1 kC - C = k^N - 1 C = (k^N-1) / (k-1) 然后每个添加的元素的复制次数为C/K^N，几乎等于1/(k-1)。

因此，Java的因子k=2意味着每个添加操作大约有一次复制，最多有50％未使用的插槽，而CPython的因子k=1.125意味着每个添加操作大约有8次复制，最多有11％未使用的插槽。

- Matt Timmermans