数组：连续内存的力量与代价

第二章：数组 — 连续内存的力量与代价

在所有数据结构中，数组是最简单的，也是最被低估的。它没有花哨的指针操作，没有复杂的平衡条件，只有一块连续的内存和一个偏移量计算公式。但正是这种极致的简单，让它在现代 CPU 架构上拥有无与伦比的性能优势。

理解数组，不是理解"一排格子"，而是理解计算机硬件如何与软件协作——连续内存让 CPU 的缓存预取机制满负荷运转，让每一次内存访问都有极高的命中率。这一章，我们从最基础的定义出发，深入到 CPython 源码、CPU 缓存架构、均摊分析，最终在面试高频题中将这些知识融会贯通。

Level 1 · 你需要知道的

1.1 数组的本质：连续内存 + 随机访问

数组的核心思想极其简单：在内存中分配一块连续的空间，每个元素占据相同大小的位置，通过起始地址 + 偏移量直接定位任意元素。

地址计算公式：
element_address = base_address + index × element_size

这个公式意味着什么？意味着无论数组有 10 个元素还是 10 亿个元素，访问第 i 个元素的时间都是恒定的——O(1)。你不需要从头遍历，不需要跟随指针跳转，一次乘法加一次加法，CPU 一个时钟周期就能算出目标地址。

这就是随机访问（Random Access）——数组得名的原因。RAM（Random Access Memory）这个词中的 Random Access，说的就是这件事。

1.2 Python list 不是传统数组

如果你的第一门语言是 Python，你可能认为数组就是 list。但 Python 的 list 和 C 语言的数组有本质区别：

Python list 的底层是一个指针数组：连续内存中存储的不是数据本身，而是指向各个 Python 对象的指针（在 64 位系统上，每个指针 8 字节）。

# 这不是 [1, 2, 3] 紧密排列在一起
# 而是 [ptr_to_1, ptr_to_2, ptr_to_3] 紧密排列
# 每个 ptr 指向堆上的一个 int 对象
my_list = [1, 2, 3]

这意味着：

1. 类型灵活：[1, "hello", 3.14, None] 完全合法，因为指针不关心指向什么类型
2. 额外开销：每个元素至少多消耗 8 字节（指针）+ 对象头部（28 字节 for int）
3. 缓存不友好：遍历 list 时，CPU 需要先读指针，再跟着指针跳到对象位置，内存访问模式不连续

1.3 常见操作的时间复杂度

每个 Python 开发者都应该把这张表刻在脑子里：

关键洞察：append 是均摊 O(1) 而不是严格 O(1)。大多数时候，列表末尾有预留空间，直接写入即可。但当预留空间用完时，Python 必须分配一块更大的内存，把所有元素搬过去。这个扩容操作是 O(n) 的，但因为发生频率很低，分摊到每次 append 上仍然是 O(1)。我们会在 Level 2 详细分析这个过程。

1.4 二维数组：行优先存储

当我们需要表示矩阵或网格时，就需要二维数组。在 Python 中，二维数组通常用嵌套列表表示：

# 3×4 的矩阵
matrix = [
    [1,  2,  3,  4],
    [5,  6,  7,  8],
    [9, 10, 11, 12]
]

# 访问第 i 行第 j 列
element = matrix[i][j]

在底层内存中，这些数据是如何排列的？绝大多数语言（C、C++、Java、Python）使用行优先存储（Row-Major Order）：先存第一行的所有元素，再存第二行，依此类推。

内存中的实际排列（行优先）：
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]
 ←—第0行—→  ←—第1行—→  ←——第2行——→

这意味着：按行遍历比按列遍历快得多。按行遍历时，连续访问的元素在内存中也是连续的，CPU 缓存可以一次性加载一整行；按列遍历时，相邻访问的元素在内存中相隔一整行的距离，缓存命中率大幅下降。

import time

n = 5000
matrix = [[0] * n for _ in range(n)]

# 按行遍历 — 快
start = time.time()
for i in range(n):
    for j in range(n):
        matrix[i][j] = 1
row_time = time.time() - start

# 按列遍历 — 慢
start = time.time()
for j in range(n):
    for i in range(n):
        matrix[i][j] = 2
col_time = time.time() - start

print(f"按行遍历: {row_time:.3f}s")
print(f"按列遍历: {col_time:.3f}s")
print(f"列遍历/行遍历 = {col_time/row_time:.1f}x")
# 典型输出：列遍历比行遍历慢 2-5 倍

1.5 常见错误：浅拷贝陷阱

这是 Python 中最经典的数组陷阱，几乎每个初学者都会踩：

# ❌ 错误的二维数组初始化
matrix = [[0] * 3] * 3
matrix[0][0] = 1
print(matrix)
# [[1, 0, 0], [1, 0, 0], [1, 0, 0]]  ← 三行全变了！

# 为什么？因为 * 3 创建的是三个指向同一列表的引用
# matrix[0], matrix[1], matrix[2] 指向同一个 [0, 0, 0]

# ✅ 正确的二维数组初始化
matrix = [[0] * 3 for _ in range(3)]
matrix[0][0] = 1
print(matrix)
# [[1, 0, 0], [0, 0, 0], [0, 0, 0]]  ← 只有第一行变了

为什么 [0] * 3 没问题但 [[0]*3] * 3 有问题？

[0] * 3 创建的是 [0, 0, 0]，里面的 0 是不可变对象（int），即使三个位置"共享"同一个 0 对象，你也无法修改 0 本身——赋值 lst[0] = 1 只是让 lst[0] 指向新的对象 1。

但 [[0]*3] * 3 里面的元素是列表（可变对象），三行共享同一个列表对象。当你修改 matrix[0][0] 时，你修改的是那个共享的列表对象，所以三行都变了。

记住这个规则：* 运算符复制的是引用，不是对象。对于不可变类型（int、str、tuple），这无所谓；对于可变类型（list、dict），这就是灾难。

1.6 越界访问

不同语言对越界访问的处理方式天差地别：

# Python — 抛出 IndexError，安全但有性能开销
lst = [1, 2, 3]
lst[5]  # IndexError: list index out of range

# Python 支持负索引
lst[-1]  # 3 （最后一个元素）
lst[-2]  # 2 （倒数第二个）

// C — 未定义行为，不检查边界
int arr[3] = {1, 2, 3};
int x = arr[5];  // 未定义行为！可能读到垃圾值，可能段错误
                 // 更可怕的是：可能看起来"正常工作"

Python 的负索引是一个优雅的设计。lst[-k] 等价于 lst[len(lst) - k]。这让从末尾开始的操作非常方便：

lst = [10, 20, 30, 40, 50]
lst[-1]    # 50  — 最后一个
lst[-2:]   # [40, 50]  — 最后两个
lst[:-1]   # [10, 20, 30, 40]  — 除了最后一个

Level 2 · 它是怎么运行的

2.1 动态数组的扩容策略

Python list 是一个动态数组（Dynamic Array）：当你不断 append 元素时，它会自动增长。但"自动增长"不是免费的——每次扩容都意味着分配新内存、复制所有元素、释放旧内存。

CPython（Python 的官方实现）的扩容逻辑位于 Objects/listobject.c 中的 list_resize 函数。其核心公式是：

/* CPython 3.12 Objects/listobject.c */
static int
list_resize(PyListObject *self, Py_ssize_t newsize)
{
    /* ... */
    new_allocated = ((size_t)newsize + (newsize >> 3) + 6) & ~(size_t)3;
    /* ... */
}

翻译成数学公式：

new_allocated = (newsize + newsize // 8 + 6) & ~3
             ≈ newsize × 1.125 + 6（然后向上对齐到 4 的倍数）

让我们用 Python 来观察这个增长过程：

import sys

lst = []
prev_size = sys.getsizeof(lst)
print(f"{'元素数':>6} {'字节数':>8} {'实际容量':>8} {'触发扩容':>8}")

for i in range(100):
    lst.append(i)
    curr_size = sys.getsizeof(lst)
    # 每个指针 8 字节，空 list 的基础大小是 56 字节（64位系统）
    capacity = (curr_size - 56) // 8
    if curr_size != prev_size:
        print(f"{i+1:>6} {curr_size:>8} {capacity:>8} {'←':>8}")
        prev_size = curr_size

典型输出（CPython 3.12，64 位系统）：

元素数     字节数   实际容量   触发扩容
     1       88        4        ←
     5      120        8        ←
     9      184       16        ←
    17      248       24        ←
    25      312       32        ←
    33      408       44        ←
    45      504       56        ←
    57      632       72        ←
    73      792       92        ←
    93      984      116        ←

观察规律：容量从 4 → 8 → 16 → 24 → 32 → 44 → 56 → 72 → 92 → 116...

增长因子大约是 1.125（即 9/8），而不是常见教科书上说的 2。这是 CPython 团队精心选择的结果。

2.2 为什么扩容因子是 ~1.125 而不是 2

扩容因子的选择是一个经典的工程权衡问题。让我们分析不同因子的利弊：

因子 = 2（Java ArrayList、C++ std::vector 的一种实现）

优点：均摊分析最简单，每次扩容后有 50% 的剩余空间 缺点：

• 空间浪费大：平均有 33% 的内存被浪费（已分配但未使用）
• 无法复用旧内存：假设初始大小为 1，扩容序列为 1, 2, 4, 8, 16...。当需要分配大小为 16 的块时，之前释放的所有块总和为 1+2+4+8=15 < 16，内存分配器永远无法用旧块拼凑出新块

因子 = 1.5（C++ MSVC std::vector、Java ArrayList）

优点：

• 空间浪费降低到平均 25%
• 从第 5 次扩容开始，之前释放的内存总和 > 新需求大小，分配器有机会复用旧内存

缺点：均摊常数稍大

因子 ≈ 1.125（CPython list）

优点：

• 空间浪费极低：平均仅约 6% 的内存浪费
• 对于大列表（百万级元素），节省大量内存
• 更快地复用旧内存块

缺点：

• 扩容更频繁，均摊常数更大
• 但 Python 已经很慢了（解释器开销），扩容的额外开销相对于解释器开销可以忽略

CPython 团队的设计哲学：Python 是内存密集型语言（每个对象都有引用计数、类型指针等开销），所以在可以省内存的地方就省。动态数组的扩容成本本身就被解释器的循环开销掩盖了，选择小因子几乎不影响整体性能，但能显著减少内存占用。

这个设计决策由 Raymond Hettinger 和 Tim Peters 等 CPython 核心开发者在 2004 年前后确定，后续微调了常数项。Tim Peters 在 Python 邮件列表中解释道：对于 Python 这种每个整数都是堆上的对象的语言，list 本身的内存开销相对于其元素的开销来说很小，所以用更保守的增长策略不会造成显著的性能下降。

2.3 Cache 局部性：为什么数组遍历比链表快 10 倍

理论上，遍历一个包含 n 个元素的数组和遍历一个包含 n 个节点的链表，时间复杂度都是 O(n)。但在实际硬件上，数组遍历可以比链表快 10-100 倍。这个差距完全来自 CPU 缓存。

CPU 缓存的工作原理：

现代 CPU 不直接从主内存读数据。在 CPU 和主内存之间，有多级缓存：

CPU 寄存器 → L1 Cache (32KB, ~1ns) → L2 Cache (256KB, ~4ns) 
          → L3 Cache (8-32MB, ~12ns) → 主内存 (GB级, ~100ns)

当 CPU 需要读取地址 X 处的数据时，它不只读 X 这一个字节，而是把 X 所在的整个 Cache Line（通常 64 字节）一次性加载到缓存中。这是基于空间局部性（Spatial Locality）原则的硬件优化：如果你访问了地址 X，你很可能马上会访问 X+1、X+2...

数组的情况：

Cache Line (64字节):
[elem0][elem1][elem2][elem3][elem4][elem5][elem6][elem7]
← 一次加载，连续8个int(8字节)全部就位 →

遍历过程：
读 elem0 → Cache Miss（去主存取，100ns）
读 elem1 → Cache Hit（已在缓存中，1ns）
读 elem2 → Cache Hit
...
读 elem7 → Cache Hit
读 elem8 → Cache Miss（新的 Cache Line）

每 8 个元素只有 1 次 Cache Miss，命中率 7/8 = 87.5%。加上硬件预取器（Prefetcher）会检测到顺序访问模式，提前加载下一个 Cache Line，实际命中率接近 100%。

链表的情况：

节点随机散布在堆内存中：
[node_A @0x1000] → [node_B @0x5830] → [node_C @0x2F10] → ...

遍历过程：
读 node_A → Cache Miss（100ns）
读 node_B → Cache Miss（地址跳跃，不在同一 Cache Line）
读 node_C → Cache Miss
... 几乎每次都 Miss

每个节点都可能在不同的 Cache Line 中（甚至不同的内存页中），几乎每次访问都是 Cache Miss。

实验验证：

import time
import array

# 方法1：数组顺序遍历
n = 10_000_000
arr = array.array('l', range(n))  # 紧凑整数数组

start = time.perf_counter()
total = 0
for x in arr:
    total += x
array_time = time.perf_counter() - start

# 方法2：模拟链表的随机访问模式
import random
indices = list(range(n))
random.shuffle(indices)

start = time.perf_counter()
total = 0
for idx in indices:
    total += arr[idx]
random_time = time.perf_counter() - start

print(f"顺序遍历: {array_time:.3f}s")
print(f"随机遍历: {random_time:.3f}s")
print(f"随机/顺序 = {random_time/array_time:.1f}x")
# 典型输出：随机遍历慢 5-15 倍

为什么差距这么大？ 主内存延迟约 100ns，而 L1 缓存延迟约 1ns，差了 100 倍。即使考虑到 L2/L3 的中间层，随机访问的平均延迟也比顺序访问高一个数量级。这就是为什么在实际工程中，数据结构的选择不能只看大 O，还要看常数因子和缓存友好性。

2.4 array 模块 vs numpy vs list

Python 提供了三种"数组"，它们的设计目标和性能特征完全不同：

list — 通用动态数组

lst = [1, 2, 3, 4, 5]
# 底层：[ptr, ptr, ptr, ptr, ptr] → 每个 ptr 指向堆上的 int 对象
# 每个元素开销：8(指针) + 28(int对象) = 36 字节
# 5个int的实际内存：56(list头) + 40(指针数组) + 140(int对象) ≈ 236 字节

array.array — 紧凑类型数组（标准库）

import array
arr = array.array('l', [1, 2, 3, 4, 5])  # 'l' = signed long (8字节)
# 底层：[1, 2, 3, 4, 5] 直接存值，无指针间接层
# 每个元素开销：8 字节（仅数值本身）
# 5个long的实际内存：64(array头) + 40(数据) ≈ 104 字节

array.array 和 C 数组一样，直接在连续内存中存储原始值。但它的 Python 层循环仍然很慢——每次访问元素时，Python 需要把原始字节装箱（boxing）成 Python int 对象。

numpy.ndarray — 高性能数值计算数组

import numpy as np
arr = np.array([1, 2, 3, 4, 5], dtype=np.int64)
# 底层：和 array.array 一样紧凑存储
# 优势：向量化操作在 C 层循环，避免 Python 循环和装箱开销

import numpy as np
import time

n = 10_000_000

# Python list 求和
lst = list(range(n))
start = time.perf_counter()
s1 = sum(lst)
list_time = time.perf_counter() - start

# numpy 求和
arr = np.arange(n, dtype=np.int64)
start = time.perf_counter()
s2 = arr.sum()
numpy_time = time.perf_counter() - start

print(f"list sum:  {list_time:.4f}s")
print(f"numpy sum: {numpy_time:.4f}s")
print(f"numpy 快 {list_time/numpy_time:.0f} 倍")
# 典型输出：numpy 快 50-100 倍

numpy 快的原因是三重加持：

1. 无装箱开销：直接操作原始字节
2. C 层循环：避免 Python 字节码解释器的循环开销
3. SIMD 指令：利用 CPU 的向量指令一次处理多个数据

2.5 内存对齐与 struct 模块

当我们需要和 C 代码交互，或者处理二进制文件格式时，必须理解内存对齐（Memory Alignment）。

CPU 访问内存时有对齐要求：一个 4 字节的 int 最好放在 4 的倍数地址上，一个 8 字节的 double 最好放在 8 的倍数地址上。不对齐的访问在某些 CPU 上会导致性能下降（x86），在另一些上会直接崩溃（ARM）。

import struct

# 假设我们要表示一个 C 结构体：
# struct Point {
#     char  label;    // 1 字节
#     int   x;       // 4 字节
#     int   y;       // 4 字节
# };

# 不考虑对齐，紧凑排列
packed = struct.pack('=bii', ord('A'), 100, 200)
print(f"紧凑大小: {len(packed)} 字节")  # 9 字节

# 考虑 C 的默认对齐规则
aligned = struct.pack('bii', ord('A'), 100, 200)
print(f"对齐大小: {len(aligned)} 字节")  # 12 字节（label 后有 3 字节填充）

# 内存布局：
# [label][pad][pad][pad][  x (4字节)  ][  y (4字节)  ]
#  0      1    2    3    4   5   6   7   8   9  10  11

struct 模块的格式字符串前缀控制字节序和对齐：

这在处理网络协议、文件格式、硬件寄存器映射时至关重要。numpy 的 dtype 也遵循类似的对齐规则，这直接影响了数组的内存布局和 SIMD 操作的效率。

Level 3 · 规范怎么定义的

3.1 动态数组的均摊分析

在第一章中，我们介绍了 Tarjan（1985）提出的均摊分析框架。现在我们用势能法（Potential Method）来严格证明动态数组 append 操作的均摊复杂度为 O(1)。

定义势能函数：

设当前数组有 n 个元素，容量为 c。定义势能函数：

Φ(n, c) = 2n - c

当数组刚扩容完毕时（n ≈ c/α，其中 α 是扩容因子），势能较低。随着元素不断添加，势能逐渐升高，直到触发下一次扩容。

情况一：append 不触发扩容

实际代价 cᵢ = 1（直接写入一个元素） 势能变化 ΔΦ = 2(n+1) - c - (2n - c) = 2 均摊代价 ĉᵢ = cᵢ + ΔΦ = 1 + 2 = 3

情况二：append 触发扩容（以因子 2 为例）

设扩容前 n = c（数组已满），新容量 c' = 2c。 实际代价 cᵢ = n + 1（复制 n 个元素 + 写入新元素） 势能变化 ΔΦ = [2(n+1) - 2n] - [2n - n] = 2 - n + 2 = 4 - n 均摊代价 ĉᵢ = (n + 1) + (4 - n) = 5

结论：无论是否触发扩容，均摊代价都是 O(1) 常数。势能法的精妙之处在于：非扩容操作的"多付"的势能，恰好覆盖了扩容操作的"欠付"。

对于 CPython 的 1.125 因子，分析过程类似，只是常数不同。设 α = 9/8：

扩容后：n ≈ (8/9)c，Φ = 2n - c ≈ (16/9 - 1)c = (7/9)c
扩容前：n = c，Φ = 2c - c = c

均摊代价仍然是 O(1)，但常数比因子 2 的情况稍大（约 18 vs 5），这就是更保守增长策略的代价。

3.2 数组在不同语言中的实现

理解同一个概念在不同语言中的实现差异，能帮助你深入理解设计权衡。

C 语言：栈数组 vs 堆数组

// 栈上数组：编译期确定大小，函数返回即销毁
int arr[100];  // 不初始化，内容未定义

// 堆上数组：运行时确定大小，需要手动释放
int *arr = malloc(n * sizeof(int));
// ... 使用 arr ...
free(arr);  // 忘记 free = 内存泄漏

// C99 VLA (Variable Length Array)：栈上变长数组
int n = get_size();
int arr[n];  // 大小运行时确定，但在栈上分配
             // 危险：如果 n 很大会栈溢出

C 数组的特点：无越界检查、无长度信息（只有指针）、不可动态增长。这既是性能优势（零开销抽象），也是安全隐患（缓冲区溢出漏洞的根源）。

Java：ArrayList

// Java 的 ArrayList 类似 Python list，但有类型约束
ArrayList<Integer> list = new ArrayList<>();
// 默认初始容量：10
// 扩容因子：1.5（newCapacity = oldCapacity + (oldCapacity >> 1)）
// JDK 源码 java.util.ArrayList#grow:
//   int newCapacity = oldCapacity + (oldCapacity >> 1);

Java 选择 1.5 的原因：介于 CPython 的 1.125（太保守）和 2（太浪费）之间，是一个平衡点。Java 的 ArrayList 不需要像 Python 那样极端地省内存，因为 Java 的 int 可以是栈上的原始类型（无装箱开销），内存效率本身就比 Python 高得多。

Rust：Vec

let mut v: Vec<i32> = Vec::new();
// 初始容量：0（不分配内存，直到第一次 push）
// 扩容因子：2
// Rust 的 Vec 选择因子 2 的理由：
// 1. 使用 jemalloc/system allocator，善于处理 2 的幂大小的分配
// 2. Rust 强调零成本抽象，2 倍扩容的均摊常数最小
// 3. 有 shrink_to_fit() 可以手动回收多余内存

3.3 CPU Cache 架构详解

（此节与《计算机是怎样工作的》第 11 章互为补充。第 11 章从硬件设计者的角度讲述 Cache 的电路实现，本节从程序员的角度讲如何利用 Cache。）

Cache 层次结构

现代 CPU（以 Apple M2 为例）的缓存层次：

以 Intel i7-12700K 为例：

Cache Line 是传输的最小单位

Cache 不是一字节一字节地搬运数据，而是以 Cache Line 为单位（绝大多数现代处理器为 64 字节）。这意味着：

# 假设 int 为 8 字节，一个 Cache Line 容纳 8 个 int
# 访问 arr[0] 时，arr[0] ~ arr[7] 全部被加载到缓存

arr = [0] * 1000  # 假设紧凑存储
# 访问 arr[0] → Cache Miss，加载 64 字节 = 8 个 int
# 访问 arr[1] ~ arr[7] → 全部 Cache Hit
# 访问 arr[8] → Cache Miss，加载下一个 Cache Line

硬件预取器（Hardware Prefetcher）

现代 CPU 内置了硬件预取器，可以检测内存访问模式：

• 流式预取：如果检测到连续地址访问（stride = 1），提前加载后续 Cache Line
• 步幅预取：如果检测到固定步幅访问（如每隔 8 个元素），也能预取
• 预取距离：通常提前 2-4 个 Cache Line

这就是为什么数组遍历在现代 CPU 上几乎达到内存带宽的理论极限——硬件预取器让几乎所有 Cache Miss 都变成了"隐藏延迟"（数据在你需要之前就已经到了）。

3.4 行优先 vs 列优先存储

行优先（Row-Major Order）— C、C++、Java、Python

二维数组 A[M][N] 在内存中按行展开：

A[0][0], A[0][1], ..., A[0][N-1], A[1][0], A[1][1], ..., A[M-1][N-1]

地址计算：A[i][j] = base + (i × N + j) × element_size

列优先（Column-Major Order）— Fortran、MATLAB、R、Julia

同一个数组按列展开：

A[0][0], A[1][0], ..., A[M-1][0], A[0][1], A[1][1], ..., A[M-1][N-1]

地址计算：A[i][j] = base + (j × M + i) × element_size

为什么有两种标准？

这要追溯到 1957 年 Fortran 语言的诞生。Fortran 的设计者 John Backus 选择列优先存储，因为在数学和物理中，矩阵运算（如线性代数的列向量操作）更常按列访问。后来 C 语言选择了行优先，因为它更符合"先写行索引后写列索引"的思维习惯。两种标准各有优势，但关键是你必须知道当前使用的是哪种，否则会导致严重的性能问题。

numpy 的选择：两者都支持

import numpy as np

# C 顺序（行优先，默认）
a = np.array([[1, 2, 3], [4, 5, 6]], order='C')
print(a.strides)  # (24, 8) — 跳一行需要 24 字节，跳一列需要 8 字节

# Fortran 顺序（列优先）
b = np.array([[1, 2, 3], [4, 5, 6]], order='F')
print(b.strides)  # (8, 16) — 跳一行需要 8 字节，跳一列需要 16 字节

性能影响：

import numpy as np
import time

n = 3000
# 行优先矩阵
A_c = np.random.rand(n, n).astype(np.float64)  # order='C'

# 列优先矩阵
A_f = np.asfortranarray(A_c)  # order='F'

# 按行求和（行优先更快）
start = time.perf_counter()
for _ in range(100):
    A_c.sum(axis=1)
c_row_time = time.perf_counter() - start

start = time.perf_counter()
for _ in range(100):
    A_f.sum(axis=1)
f_row_time = time.perf_counter() - start

# 按列求和（列优先更快）
start = time.perf_counter()
for _ in range(100):
    A_c.sum(axis=0)
c_col_time = time.perf_counter() - start

start = time.perf_counter()
for _ in range(100):
    A_f.sum(axis=0)
f_col_time = time.perf_counter() - start

print(f"按行求和: C-order {c_row_time:.3f}s, F-order {f_row_time:.3f}s")
print(f"按列求和: C-order {c_col_time:.3f}s, F-order {f_col_time:.3f}s")

实际工程中的影响：

• 图像处理（OpenCV）：行优先，因为图像按行扫描
• 科学计算（BLAS/LAPACK）：列优先（Fortran 遗产），numpy 调用时需要注意转换
• 深度学习（PyTorch）：行优先，但有 channels_first vs channels_last 的选择
• 数据库（列式存储 vs 行式存储）：列式存储（如 Parquet、ClickHouse）更适合分析查询

Level 4 · 边界与陷阱

4.1 Python list 的隐藏性能陷阱

陷阱一：list.insert(0, x) — O(n) 的头部插入

import time
from collections import deque

n = 100_000

# ❌ 用 list 做头部插入
lst = []
start = time.perf_counter()
for i in range(n):
    lst.insert(0, i)
list_time = time.perf_counter() - start

# ✅ 用 deque 做头部插入
dq = deque()
start = time.perf_counter()
for i in range(n):
    dq.appendleft(i)
deque_time = time.perf_counter() - start

print(f"list.insert(0): {list_time:.3f}s")
print(f"deque.appendleft: {deque_time:.3f}s")
print(f"list 慢 {list_time/deque_time:.0f} 倍")
# 典型输出：list 慢 100-500 倍

为什么 list.insert(0, x) 这么慢？ 每次插入都需要把所有现有元素右移一位。对于 n 次操作，总移动次数是 0+1+2+...+(n-1) = O(n²)。

collections.deque 底层是一个双端队列（由固定大小的块组成的双向链表），头部和尾部的插入/删除都是 O(1)。规则：如果你需要频繁在头部操作，用 deque 代替 list。

陷阱二：list + list — 创建新列表的隐藏拷贝

# ❌ 在循环中用 + 拼接列表
result = []
for chunk in data_chunks:
    result = result + chunk  # 每次都创建新列表并复制所有元素！
# 总时间复杂度：O(n × k)，其中 n 是 chunk 数，k 是平均 chunk 大小
# 如果所有 chunk 总共 N 个元素，实际是 O(N²)

# ✅ 用 extend 或 +=
result = []
for chunk in data_chunks:
    result.extend(chunk)  # 原地扩展，O(总元素数)
# 或者更简洁
result = []
for chunk in data_chunks:
    result += chunk  # += 对 list 等价于 extend，是原地操作！

注意：result = result + chunk 和 result += chunk 的语义完全不同！前者调用 __add__（创建新列表），后者调用 __iadd__（原地扩展）。这是 Python 中一个容易被忽视的坑。

陷阱三：list * n 的引用共享

# 表面无害的初始化
board = [[None] * 8] * 8  # 8×8 棋盘

# 实际上 8 行都是同一个列表
board[0][0] = "King"
print(board[3][0])  # "King" — 所有行都被影响了

# 正确写法
board = [[None] * 8 for _ in range(8)]

这个陷阱我们在 Level 1 已经提过，但这里要强调的是：即使是经验丰富的程序员，在更复杂的场景中也会犯这个错误：

# 更隐蔽的变体
cache = [{}] * 100  # 100 个"独立"的字典？不，是同一个！
cache[0]["key"] = "value"
print(cache[99]["key"])  # "value" — 100 个位置共享一个字典

# 正确
cache = [{} for _ in range(100)]

陷阱四：in 操作符的线性搜索

# ❌ 对 list 使用 in（O(n)）
blacklist = [...]  # 10万个元素
if user_id in blacklist:  # 每次检查遍历整个列表
    block()

# ✅ 转成 set（O(1) 查找）
blacklist_set = set(blacklist)  # 一次性 O(n) 转换
if user_id in blacklist_set:  # O(1) 哈希查找
    block()

4.2 大数组的内存估算

在生产环境中，你需要准确估算数据结构的内存占用。Python 的 sys.getsizeof 有一个重大限制：它只计算对象本身的大小，不递归计算引用对象。

import sys

# sys.getsizeof 的误导性
lst = [1, 2, 3]
print(sys.getsizeof(lst))  # 88 字节 — 只有 list 对象本身！
# 不包含 1, 2, 3 这三个 int 对象的大小

# 单个 int 的大小
print(sys.getsizeof(1))    # 28 字节
print(sys.getsizeof(0))    # 28 字节
print(sys.getsizeof(2**30))  # 32 字节（大整数需要更多空间）

# 真实总内存：88 + 3 × 28 = 172 字节（存3个小整数）
# 但 CPython 对小整数 (-5 ~ 256) 有缓存池，所以不会重复分配

递归计算真实内存占用：

import sys
from collections import deque

def deep_getsizeof(obj, seen=None):
    """递归计算对象及其所有引用对象的总内存"""
    if seen is None:
        seen = set()
    obj_id = id(obj)
    if obj_id in seen:
        return 0
    seen.add(obj_id)
    
    size = sys.getsizeof(obj)
    
    if isinstance(obj, dict):
        size += sum(deep_getsizeof(k, seen) + deep_getsizeof(v, seen) 
                   for k, v in obj.items())
    elif isinstance(obj, (list, tuple, set, frozenset, deque)):
        size += sum(deep_getsizeof(item, seen) for item in obj)
    
    return size

# 示例
lst = list(range(1000))
print(f"sys.getsizeof: {sys.getsizeof(lst):,} 字节")
print(f"deep_getsizeof: {deep_getsizeof(lst):,} 字节")
# sys.getsizeof: ~8,056 字节（只有指针数组）
# deep_getsizeof: ~36,056 字节（包含所有 int 对象）

大规模数据的内存估算公式：

# 实际工程估算示例
# 100万个浮点数
n = 1_000_000

# Python list
# 指针数组：56 + 8×n ≈ 8 MB
# float 对象：24×n ≈ 24 MB
# 总计：约 32 MB

# numpy array
# 8×n = 8 MB
# 节省 75% 内存！

import numpy as np
lst = [float(i) for i in range(n)]
arr = np.arange(n, dtype=np.float64)

print(f"list 实际内存: ~{sys.getsizeof(lst)/1024/1024:.1f} MB (不含float对象)")
print(f"numpy 实际内存: {arr.nbytes/1024/1024:.1f} MB")

4.3 面试高频题精讲

数组是面试中最高频的考点之一。以下是四道经典题目的深度解析。

题目一：旋转数组 — LeetCode #189

给定一个整数数组 nums，将数组中的元素向右轮转 k 个位置。

# 方法1：切片（简洁但创建新数组，空间 O(n)）
def rotate_v1(nums, k):
    n = len(nums)
    k = k % n  # 处理 k > n 的情况
    nums[:] = nums[-k:] + nums[:-k]
    # 注意：nums[:] = ... 是原地修改，nums = ... 是重新绑定变量

# 方法2：三次翻转（原地，空间 O(1)）
def rotate_v2(nums, k):
    n = len(nums)
    k = k % n
    
    def reverse(arr, left, right):
        while left < right:
            arr[left], arr[right] = arr[right], arr[left]
            left += 1
            right -= 1
    
    # 整体翻转 → 前 k 个翻转 → 后 n-k 个翻转
    # 原理：[1,2,3,4,5,6,7], k=3
    # 整体翻转：[7,6,5,4,3,2,1]
    # 前3翻转：[5,6,7,4,3,2,1]
    # 后4翻转：[5,6,7,1,2,3,4] ✓
    reverse(nums, 0, n - 1)
    reverse(nums, 0, k - 1)
    reverse(nums, k, n - 1)

# 方法3：环形替换（原地，空间 O(1)，更难理解）
def rotate_v3(nums, k):
    n = len(nums)
    k = k % n
    if k == 0:
        return
    
    count = 0  # 已放置的元素数
    start = 0
    while count < n:
        current = start
        prev = nums[start]
        while True:
            next_idx = (current + k) % n
            nums[next_idx], prev = prev, nums[next_idx]
            current = next_idx
            count += 1
            if current == start:
                break
        start += 1

三次翻转法的数学证明：

设原数组为 a₀, a₁, ..., aₙ₋₁，右旋 k 位后应为 aₙ₋ₖ, ..., aₙ₋₁, a₀, ..., aₙ₋ₖ₋₁。

设 rev(A) 表示翻转序列 A。设 A = a₀...aₙ₋ₖ₋₁，B = aₙ₋ₖ...aₙ₋₁。

原序列为 AB，目标为 BA。

rev(rev(A)·rev(B)) = rev(rev(B))·rev(rev(A)) = BA

所以：先翻转整体 rev(AB)，再分别翻转前后两段，等价于将 AB 变为 BA。

题目二：合并两个有序数组 — LeetCode #88

给你两个有序整数数组 nums1 和 nums2，将 nums2 合并到 nums1 中。nums1 后面有足够的空间。

def merge(nums1, m, nums2, n):
    """
    关键技巧：从后往前填充，避免覆盖未处理的元素
    
    为什么从后往前？如果从前往前，nums1 前面的元素会被覆盖，
    需要额外空间保存。从后往前填充，利用 nums1 尾部的空位。
    """
    p1, p2, p = m - 1, n - 1, m + n - 1
    
    while p1 >= 0 and p2 >= 0:
        if nums1[p1] >= nums2[p2]:
            nums1[p] = nums1[p1]
            p1 -= 1
        else:
            nums1[p] = nums2[p2]
            p2 -= 1
        p -= 1
    
    # 如果 nums2 还有剩余，复制过去
    # 如果 nums1 还有剩余，不需要动（已经在正确位置）
    nums1[:p2 + 1] = nums2[:p2 + 1]

时间复杂度：O(m + n)，每个元素恰好被处理一次。 空间复杂度：O(1)，原地操作。

题目三：移除元素 — LeetCode #27

原地移除数组中等于 val 的所有元素，返回新长度。

def removeElement(nums, val):
    """
    双指针法：slow 指向下一个要写入的位置，fast 扫描整个数组
    """
    slow = 0
    for fast in range(len(nums)):
        if nums[fast] != val:
            nums[slow] = nums[fast]
            slow += 1
    return slow

# 优化版本：当要删除的元素很少时
def removeElement_v2(nums, val):
    """
    与末尾元素交换，避免不必要的移动
    适用于要删除的元素很少的情况
    """
    n = len(nums)
    i = 0
    while i < n:
        if nums[i] == val:
            nums[i] = nums[n - 1]
            n -= 1
            # 不增加 i，因为交换来的元素还需要检查
        else:
            i += 1
    return n

两种方法的对比：

• 方法一：总是 O(n) 次赋值，但保持相对顺序
• 方法二：最多 O(k) 次赋值（k 是 val 的出现次数），但不保持顺序

题目四：螺旋矩阵 — LeetCode #54

给你一个 m×n 矩阵，按照顺时针螺旋顺序返回所有元素。

def spiralOrder(matrix):
    """
    模拟法：维护四个边界，每遍历完一条边就收缩对应边界
    
    top →→→→→→→→→ right
      ↑              ↓
      ↑              ↓
      ↑              ↓
    left ←←←←←←←← bottom
    """
    if not matrix or not matrix[0]:
        return []
    
    result = []
    top, bottom = 0, len(matrix) - 1
    left, right = 0, len(matrix[0]) - 1
    
    while top <= bottom and left <= right:
        # 从左到右遍历顶行
        for col in range(left, right + 1):
            result.append(matrix[top][col])
        top += 1
        
        # 从上到下遍历右列
        for row in range(top, bottom + 1):
            result.append(matrix[row][right])
        right -= 1
        
        # 从右到左遍历底行（需要检查是否还有底行）
        if top <= bottom:
            for col in range(right, left - 1, -1):
                result.append(matrix[bottom][col])
            bottom -= 1
        
        # 从下到上遍历左列（需要检查是否还有左列）
        if left <= right:
            for row in range(bottom, top - 1, -1):
                result.append(matrix[row][left])
            left += 1
    
    return result

为什么需要 if top <= bottom 和 if left <= right 的检查？

考虑一个 1×4 的矩阵 [[1,2,3,4]]。在第一轮循环中：

1. 从左到右遍历顶行 → [1,2,3,4]，top 变为 1
2. 从上到下遍历右列 → 无元素（top > bottom），right 变为 2
3. 如果不检查 top <= bottom，会从右到左遍历"底行"（其实就是已经遍历过的第一行），导致重复

螺旋矩阵的变体思路：

# 巧妙的递归方法：每次取第一行，然后逆时针旋转矩阵
def spiralOrder_recursive(matrix):
    if not matrix:
        return []
    # zip(*matrix[1:]) 转置剩余部分
    # [::-1] 翻转行 = 逆时针旋转90°
    return list(matrix[0]) + spiralOrder_recursive(
        [list(row) for row in zip(*matrix[1:])][::-1]
    )

4.4 什么时候不该用数组

数组不是万能的。以下场景中，其他数据结构是更好的选择：

场景一：频繁头部插入/删除 → deque

from collections import deque

# 滑动窗口、BFS 队列、撤销/重做栈
dq = deque(maxlen=1000)  # 固定大小的环形缓冲区
dq.appendleft(item)  # O(1)
dq.popleft()         # O(1)

deque 底层是一个由固定大小块（每块 64 个元素）组成的双向链表。头部和尾部操作是 O(1)，但随机访问是 O(n)（需要定位到正确的块）。在 CPython 实现中，deque 的块大小为 64（BLOCKLEN = 64，定义在 Modules/_collectionsmodule.c 中），每个块是一个紧凑数组，兼顾了缓存友好性和双端操作效率。

场景二：频繁查找/判重 → set 或 dict

# 查找 O(1) vs O(n)
seen = set()
for item in stream:
    if item in seen:  # O(1) 平均
        handle_duplicate(item)
    seen.add(item)

场景三：需要有序且频繁插入/删除 → 平衡二叉树或跳表

Python 标准库没有内置平衡树，但 sortedcontainers.SortedList 提供了类似功能：

from sortedcontainers import SortedList

sl = SortedList()
sl.add(5)       # O(log n)
sl.add(3)
sl.add(7)
sl.remove(5)    # O(log n)
print(sl[0])    # O(log n) — 支持索引访问

场景四：稀疏数据 → 字典或稀疏矩阵

# ❌ 用数组存储稀疏数据
# 99% 的位置是 0，浪费大量内存
grid = [[0] * 10000 for _ in range(10000)]  # 800 MB 内存！
grid[5][3] = 1
grid[9999][9999] = 2

# ✅ 用字典
sparse = {}
sparse[(5, 3)] = 1
sparse[(9999, 9999)] = 2
# 只占用非零元素的内存

# 科学计算用 scipy 稀疏矩阵
from scipy import sparse
mat = sparse.csr_matrix((10000, 10000))
mat[5, 3] = 1

决策树：

需要什么操作？
├── 随机访问为主 → 数组 (list / numpy)
├── 头/尾插入删除为主 → deque
├── 查找/判重为主 → set / dict
├── 有序 + 插入删除 → SortedList / 堆
├── 稀疏数据 → dict / sparse matrix
└── 数值计算（批量操作） → numpy / pandas

4.5 数组的工程实践总结

在实际工程中，数组相关的性能问题比任何其他数据结构都多，因为它太常用了，以至于人们忘了思考。以下是几条铁律：

铁律一：预分配比动态增长快

# ❌ 动态增长（多次扩容）
result = []
for i in range(1_000_000):
    result.append(compute(i))

# ✅ 列表推导（CPython 对推导有内部优化，能预估大小）
result = [compute(i) for i in range(1_000_000)]

# ✅ 如果知道确切大小，用 numpy 预分配
result = np.empty(1_000_000, dtype=np.float64)
for i in range(1_000_000):
    result[i] = compute(i)

列表推导不仅语法更简洁，在 CPython 实现中还有专门的字节码优化（LIST_APPEND 指令），比等价的 for 循环 + append 快约 30%。

铁律二：避免在循环中构建字符串

# ❌ O(n²) — 每次 += 创建新字符串（字符串不可变）
s = ""
for word in words:
    s += word + " "

# ✅ O(n) — join 一次性分配
s = " ".join(words)

虽然这是字符串的例子，但本质和数组扩容一样：不可变序列的拼接 = 每次都完整复制。

铁律三：用 numpy 替代 Python 循环做数值计算

# ❌ Python 循环 — 慢
def normalize_python(data):
    mean = sum(data) / len(data)
    std = (sum((x - mean) ** 2 for x in data) / len(data)) ** 0.5
    return [(x - mean) / std for x in data]

# ✅ numpy 向量化 — 快 100 倍
def normalize_numpy(data):
    arr = np.array(data)
    return (arr - arr.mean()) / arr.std()

铁律四：理解你的访问模式，选择正确的内存布局

# 如果你的操作是逐行处理（如图像滤波）
# → 使用 C-order (行优先)
image = np.zeros((height, width, 3), dtype=np.uint8, order='C')

# 如果你的操作是逐列处理（如时间序列的特征列）
# → 使用 F-order (列优先) 或 pandas DataFrame
features = np.zeros((n_samples, n_features), order='F')

本章小结

数组是最简单的数据结构，但"简单"不意味着"简陋"。这一章我们看到了：

1. 连续内存是数组的灵魂：它赋予了 O(1) 随机访问的能力，更重要的是让 CPU 缓存和预取机制充分发挥作用。

2. 动态数组是精巧的工程权衡：CPython 选择 1.125 的扩容因子，Java 选择 1.5，C++ 选择 2——每个选择背后都有充分的理由，反映了语言的设计哲学。

3. 理解硬件才能写出快代码：Cache Line、预取器、内存对齐——这些硬件特性决定了同为 O(n) 的两段代码，实际性能可以差 100 倍。

4. 知道什么时候不用数组：频繁头部操作用 deque，查找用 set，稀疏数据用字典。选择正确的数据结构，比优化错误的数据结构重要一万倍。

下一章，我们将学习链表——数组的"对立面"。链表牺牲了随机访问和缓存友好性，换来了 O(1) 的任意位置插入删除。理解了数组的优势和局限，你才能真正理解为什么链表是必要的。

参考资料

• Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to Algorithms (3rd ed.), Chapter 17: Amortized Analysis. MIT Press.
• Tarjan, R. E. (1985). "Amortized Computational Complexity". SIAM Journal on Algebraic and Discrete Methods, 6(2), 306-318.
• CPython source code: Objects/listobject.c — list_resize function. https://github.com/python/cpython
• Drepper, U. (2007). "What Every Programmer Should Know About Memory". Red Hat, Inc.
• Bryant, R. E., & O'Hallaron, D. R. (2015). Computer Systems: A Programmer's Perspective (3rd ed.), Chapter 6: The Memory Hierarchy. Pearson.
• Tim Peters, Python-Dev mailing list discussions on list growth strategy (2004).
• Hettinger, R. "Modern Python: Big Ideas and Little Code". PyCon 2017 keynote.