数组(Array)与 Python 列表

数组按下标组织元素;CPython 的 list 使用可扩容的对象指针数组。下标访问快,尾部追加为摊还常数时间,头部插入则需移动元素。

一句话定义

数组按下标组织元素;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 。

图 1

地址计算公式(这正是 O(1)O(1) 随机访问的来源):

addr(i)=base+i×slot_size \text{addr}(i) = \text{base} + i \times \text{slot\_size}
操作 复杂度 原因
a[i] 读写 O(1)O(1) 地址直接计算
append / 尾部 pop 摊还 O(1)O(1) 有空槽直接放,偶尔扩容
insert(0, x) / pop(0) O(n)O(n) 后面所有元素要挪一位
x in a O(n)O(n) 逐个比较

可运行示例

观察扩容过程、各操作的实际耗时、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 都扩容。
  • 本轮计时展示头部与尾部操作差异,具体倍数与规模和环境有关:这就是 O(n)O(n) 与 O(1)O(1) 的差别。
  • list 存的是指向对象的指针,array('d') 直接存 8 字节浮点数,实际内存比例取决于列表元素是否共享、平台与统计口径。

常见误区

  • [[0]*3]*3 建二维表:三行是同一个列表对象,改一行三行一起变(见 k1.py.object-reference)。用 [[0]*3 for _ in range(3)]。
  • 把 list 当队列用 pop(0):O(n)O(n),改用 collections.deque(见 k2.ds.queue)。
  • 以为 Python list 存的是“值”:它存引用,元素可以是不同类型。
  • 大量数值计算用 list 循环:改用 NumPy 向量化。

与 AI 开发的关系

  • 张量在程序中常通过多维数组及其存储布局表示:PyTorch/NumPy 张量的“形状 + 步长(stride)”就是在连续内存上做下标换算,view/reshape/contiguous 的区别都源于此。
  • 批处理与预分配:知道长度时预分配数组比反复 append 更省内存碎片。
  • Token 序列、嵌入表本质上都是按下标访问的数组。

延伸阅读

理解检查

list 的 append 摊还 O(1),为什么某一次追加仍可能很慢?

参考答案:容量不足时需要分配并迁移槽位;摊还复杂度描述一系列操作的总成本。

核验与复现

核验日期:2026-10-14。示例状态:运行通过。本轮日志:08_array.py。

配套代码与核验资料

继续浏览基础 返回知识 →返回顶部 ↑
本篇目录
教程图解100%
教程图解