一句话定义
数组按下标组织元素;CPython 的 list 使用可扩容的对象指针数组。下标访问快,尾部追加为摊还常数时间,头部插入则需移动元素。
为什么重要
- 数组是栈、二叉堆和哈希表等结构的一种常用实现基础。
- 理解“连续内存”就能解释:为什么尾部追加快、头部插入慢;为什么 NumPy 比 list 快(见 k1.lib.numpy)。
使用边界
list 连续存放的是引用槽位,不是各个 Python 对象本体。sys.getsizeof 不递归统计元素;张量也可能是带步长的非连续视图,不能把连续存储推广到所有数组对象。
原理 / 图解
CPython list 由指针数组实现,按比例**超额分配(over-allocation)**以使追加的摊还成本为常数:源码 https://github.com/python/cpython/blob/main/Objects/listobject.c ;官方时间复杂度表:https://wiki.python.org/moin/TimeComplexity 。
地址计算公式(这正是 随机访问的来源):
| 操作 | 复杂度 | 原因 |
|---|---|---|
a[i] 读写 |
地址直接计算 | |
append / 尾部 pop |
摊还 | 有空槽直接放,偶尔扩容 |
insert(0, x) / pop(0) |
后面所有元素要挪一位 | |
x in a |
逐个比较 |
可运行示例
观察扩容过程、各操作的实际耗时、array 模块的紧凑存储,以及二维列表的经典陷阱(Python 3.15.0 一稿运行记录):
# 文件:examples/08_array.py
# 数组:连续内存 + 下标 O(1) 访问;Python 的 list 是"动态数组"
import sys, time, array
from timeit import timeit
lst = []
sizes = []
for i in range(20):
lst.append(i)
sizes.append(sys.getsizeof(lst))
print("append 过程中 list 占用字节变化(容量成倍预留):", sorted(set(sizes)))
big = list(range(1_000_000))
t_idx = timeit(lambda: big[500_000], number=100_000)
t_end = timeit(lambda: big.append(0) or big.pop(), number=100_000)
t_head = timeit(lambda: big.insert(0, 0) or big.pop(0), number=1_000)
print(f"随机访问 {t_idx/100_000*1e9:.0f} ns | 尾部增删 {t_end/100_000*1e9:.0f} ns | 头部增删 {t_head/1_000*1e6:.0f} µs")
# 紧凑数组:array 模块按 C 类型存储,比 list 省内存
a = array.array("d", range(1000))
print("list 1000 个浮点约", sys.getsizeof(list(map(float, range(1000)))) + 1000 * sys.getsizeof(1.0), "字节",
"| array('d') 约", sys.getsizeof(a), "字节")
# 二维数组的坑:[[0]*3]*3 复制的是同一行的引用
bad = [[0] * 3] * 3; bad[0][0] = 1
good = [[0] * 3 for _ in range(3)]; good[0][0] = 1
print("bad :", bad); print("good:", good)
一稿留存输出:
append 过程中 list 占用字节变化(容量成倍预留): [88, 120, 184, 248]
随机访问 20 ns | 尾部增删 42 ns | 头部增删 546 µs
list 1000 个浮点约 32856 字节 | array('d') 约 8320 字节
bad : [[1, 0, 0], [1, 0, 0], [1, 0, 0]]
good: [[1, 0, 0], [0, 0, 0], [0, 0, 0]]
sys.getsizeof是阶梯式增长的(88 → 120 → 184 → 248 字节),说明不是每次 append 都扩容。- 本轮计时展示头部与尾部操作差异,具体倍数与规模和环境有关:这就是 与 的差别。
list存的是指向对象的指针,array('d')直接存 8 字节浮点数,实际内存比例取决于列表元素是否共享、平台与统计口径。
常见误区
[[0]*3]*3建二维表:三行是同一个列表对象,改一行三行一起变(见 k1.py.object-reference)。用[[0]*3 for _ in range(3)]。- 把 list 当队列用
pop(0):,改用collections.deque(见 k2.ds.queue)。 - 以为 Python list 存的是“值”:它存引用,元素可以是不同类型。
- 大量数值计算用 list 循环:改用 NumPy 向量化。
与 AI 开发的关系
- 张量在程序中常通过多维数组及其存储布局表示:PyTorch/NumPy 张量的“形状 + 步长(stride)”就是在连续内存上做下标换算,
view/reshape/contiguous的区别都源于此。 - 批处理与预分配:知道长度时预分配数组比反复 append 更省内存碎片。
- Token 序列、嵌入表本质上都是按下标访问的数组。
延伸阅读
- Python 官方:列表的更多用法 https://docs.python.org/zh-cn/3/tutorial/datastructures.html
array模块:https://docs.python.org/3/library/array.html- Python Wiki 时间复杂度:https://wiki.python.org/moin/TimeComplexity
理解检查
list 的 append 摊还 O(1),为什么某一次追加仍可能很慢?
参考答案:容量不足时需要分配并迁移槽位;摊还复杂度描述一系列操作的总成本。
核验与复现
核验日期:2026-10-14。示例状态:运行通过。本轮日志:08_array.py。
配套代码与核验资料