你能否通过剖析源码解释为什么Python的列表扩容不是翻倍而是增加约12.5%

访客源码剖析 2026-06-05 10:42:13 1

本文目录导读：

核心结论（先剧透）
第一层：源码入口（listobject.c）
第二层：拆解扩容公式
第三层：为什么选择“12.5%”而不是“100%（翻倍）”？
第四层：一个重要的例外（list.clear() 与缩容）
总结与延伸

这是一个很深入且常见的问题,首先需要纠正一个细微但重要的表述：CPython（标准Python解释器）的列表扩容机制并非固定增加“12.5%”，而是遵循一个特定的线性增长模式，其背后的核心逻辑与“内存分配效率”和“避免浪费”有关。

下面,我将从CPython的源码（以3.11+版本为例）角度，剖析为什么Python的列表扩容策略不是简单的翻倍，而是目前这种看似“约12.5%”的增长模式。

核心结论（先剧透）

Python列表的扩容策略被设计为：new_allocated = (size // 8) + (3 if size < 9 else 6) + size。

这个公式导致的结果是：对于大列表，扩容增量大约是当前大小的 1/8（即12.5%），它故意选择不翻倍，主要目的是为了在保证分摊O(1)时间复杂度的同时，极大地减少内存浪费。

第一层：源码入口（`listobject.c`）

关键的扩容函数是 list_resize，你需要查找 CPython 源码中的 Objects/listobject.c 文件。

// 来自 CPython 3.12 源码 (Objects/listobject.c)
static int
list_resize(PyListObject *self, Py_ssize_t newsize)
{
    PyObject **items;
    size_t new_allocated, num_allocated_bytes;
    Py_ssize_t allocated = self->allocated;
    // 如果新大小小于等于当前已分配容量，则不需要扩容
    if (allocated >= newsize && newsize >= (allocated >> 1)) {
        // ... 一些边界检查
        return 0;
    }
    // ---------- 这里是核心扩容逻辑 ----------
    // 计算新容量
    new_allocated = (size_t)newsize + (newsize >> 3) + (newsize < 9 ? 3 : 6);
    if (new_allocated > (size_t)PY_SSIZE_T_MAX / sizeof(PyObject *)) {
        PyErr_NoMemory();
        return -1;
    }
    // ... 执行内存重新分配 (realloc) ...
}

关键行： new_allocated = (size_t)newsize + (newsize >> 3) + (newsize < 9 ? 3 : 6);

我们来拆解这个公式。

第二层：拆解扩容公式

公式：new_allocated = newsize + (newsize >> 3) + (newsize < 9 ? 3 : 6)

newsize：这是扩容后列表想要达到的“逻辑大小”（即元素个数），当你在列表末尾执行 append 时，如果当前列表容量不够，newsize 原长度 + 1。
newsize >> 3：这是整数除法，相当于 newsize // 8，这是产生“12.5%”增量的直接来源。
(newsize < 9 ? 3 : 6)：这是一个小列表的额外补贴，当列表很小（长度小于9）时，额外分配3个槽位；当列表较大时，额外分配6个槽位。

为什么需要这个额外的 +3 或 +6？ 这是为了平滑小列表的扩容行为，如果没有这个常数项，一个从0开始的空列表，每次append都会触发一次昂贵的内存重新分配，加上常数项后，可以确保前几次append能快速分配足够空间，减少扩容次数。

举例计算（非常直观）

假设当前列表长度为 n，容量为 c，执行 append 时，newsize = n + 1。

当前长度 n	新需求 newsize	新容量计算 (newsize + newsize//8 + 6)	新容量	扩容增量	增量百分比
0	1	1 + 0 + 3 = 4 (小列表+3)	4	+4	N/A (从0开始)
3	4	4 + 0 + 3 = 7	7	+4	133%
7	8	8 + 1 + 6 = 15 (进入+6模式)	15	+8	114%
15	16	16 + 2 + 6 = 24	24	+9	60%
100	101	101 + 12 + 6 = 119	119	+19	19%
1000	1001	1001 + 125 + 6 = 1132	1132	+132	2%
10000	10001	10001 + 1250 + 6 = 11257	11257	+1256	56%
1,000,000	1,000,001	1,000,001 + 125,000 + 6 = 1,125,007	1,125,007	+125,006	5%

你可以清楚地看到：随着列表变大，增量百分比稳定地趋近于1/8（12.5%）。

第三层：为什么选择“12.5%”而不是“100%（翻倍）”？

这是设计上的一个精妙的权衡，翻倍（如C++的std::vector）和Python的1/8增长，代表了两种不同的设计哲学：

翻倍策略（C++ vector）

优点：分摊时间复杂度非常低，每次扩容都会将容量翻倍，所以一个元素一生中被复制的次数大约是log₂(n)次。（例如从1到100万，大约只需要复制20次）。
缺点：内存浪费极大，如果一个列表最终只存储了 2^k + 1个元素，那么实际分配的内存是 2^(k+1)，内存浪费接近 50%。

Python的12.5%策略

优点：内存利用率极高，每次扩容只增加12.5%的额外空间，在最坏情况下（恰好扩容后立即停止），浪费比例大约是 5% / (1+12.5%) ≈ 11.1%。内存浪费比翻倍的50%大幅度降低。
缺点：分摊时间复杂度变差，一个元素一生中被复制的次数大约是 O(n/k) 次（k是增长因子），对于12.5%，大约是 O(log_(1.125)(n)) 次，大约是 8 * log_e(n) 次，即大约比翻倍策略多花8倍的时间在数据拷贝上。

核心权衡：为什么Python选择了“慢一点但省内存”？

Python的设计哲学在其发展和应用场景中逐渐明确：面向对象的动态类型语言 + 开发者通常写的是“脚本”而非“极限性能计算”。

内存更宝贵：在Python中，每个对象（包括列表中的元素）都是一个复杂的PyObject指针（8字节），并且可能涉及引用计数等，让列表本身占用的内存膨胀一倍，其影响远比C++中一个vector<int>大得多。控制内存碎片和浪费是首要目标。
单次操作速度：对于Python开发者，一次append操作的时间大部分花在Python解释器循环、类型检查、对象分配、引用计数等元操作上，而真正用于拷贝指针的内存操作只占很小一部分，增加一些拷贝次数（从log到8*log）对用户体验的影响，远小于内存浪费30%带来的负面影响。
确定性行为：翻倍策略在小列表时行为非常激进（例如从0到4，从4到8），而Python的公式通过 +3 和 +6 做了平滑，让列表从小到大的增长更平稳。

第四层：一个重要的例外（`list.clear()` 与缩容）

虽然扩容是12.5%，但Python并没有对称的“缩容”机制，当你清空列表后，其容量保持不变，这意味着你无法简单通过清空来回收内存，只有当你删除大量元素导致 allocated > 4 * newsize 时，list_resize 才会触发一次“缩容”到 newsize + (newsize >> 3) + 6。

总结与延伸

Python列表的扩容不是固定12.5%，而是 newsize + newsize//8 + (3或6)，这个约1/8的增长因子是有意为之的设计选择，它在维持可接受的时间复杂度（非严格O(1)但分摊O(1)） 和 显著降低内存浪费（从约50%降到约11%） 之间找到了平衡。
这不是一条数学定律，而是一个工程选择，CPython的开发者（特别是Raymond Hettinger等人）经过深思熟虑后选择了这个模式。
对于你的代码意味着什么？
- 无需担心：Python的list.append()性能已经足够好。
- 如果需要极致性能且知道最终大小：使用 list = [None] * expected_size 预分配，可以完全避免扩容开销。
- 如果需要频繁在任意位置插入：考虑使用 collections.deque。