在Python中列表的大小调整系数是多少

问题描述

例如，Java中的ArrayList的大小调整系数为2。当ArrayList所环绕的数组空间不足时，该数组的所有元素都将转移到一个新数组中，该数组的大小是原始数组的2倍。

既然Python列表/数组自然是动态的，那么它们的大小调整因素是什么？或者，他们是否使用其他一些扩展方法？如果是的话，那是什么方法呢？它的渐近运行时(大O)是多少？

---

解决方案

特别是objects/listobject.c中实现了调整时的超配。它被描述为

温和，但..。足以在性能不佳的系统realloc()存在的情况下，在较长的append()序列上提供线性时间摊销行为。

当列表需要增长时，它将增长到大约所需大小的112.5。特别是，实际大小为new_size + new_size >> 3 + (newsize < 9 ? 3 : 6)。