数组与动态数组

前置知识#

建议先阅读以下内容再进入本文：

• 算法分析基础与学习路线

1. 概述与学习目标#

1.1 什么是数组与动态数组#

数组（Array）是计算机科学中最基础的数据结构，它将相同类型的元素存储在一段连续的内存空间中，并通过索引（下标）实现 $O(1)$ 的随机访问。这一简单的连续存储模型正是 Von Neumann 1945 年存储程序架构的物理体现，至今仍是所有现代计算机体系结构的基石。

静态数组（Static Array）在创建时必须指定大小且不可改变；动态数组（Dynamic Array）则在内部维护一个容量可变的底层数组，当空间不足时自动倍增扩容（resize），并通过均摊分析保证 append 操作的均摊 $O(1)$ 复杂度。

flowchart LR
    S[静态数组 size=capacity=5<br/>10 20 30 40 50<br/>内存连续，索引 0-4]
    D[动态数组 size=4 capacity=8<br/>10 20 30 40 空 空 空 空<br/>内存连续，预留空间 索引 0-3 size，可继续追加]

一句话定义：数组 = 连续内存 + 索引寻址，随机访问 $O(1)$，中间插删 $O(n)$，缓存友好；动态数组 = 静态数组 + 倍增扩容，append 均摊 $O(1)$，是工业级动态序列的首选。

1.2 学习目标#

完成本文档学习后，你将能够：

1. 记忆数组作为连续内存线性表的形式化定义 $\text{address}(i) = \text{base} + i \times \text{size}$，复述静态数组、动态数组在随机访问、头部插入、尾部插入、任意位置插入删除上的时间复杂度差异；
2. 理解 Von Neumann 1945 EDVAC 报告《First Draft of a Report on the EDVAC》确立的存储程序架构、Iverson 1962 APL 语言首创数组运算符、Stepanov-Lee 1994 STL 设计 std::vector 的历史脉络，说明连续存储为何成为现代计算机体系结构的基石；
3. 应用顺序数组、动态数组（含倍增扩容与缩容）、二维行优先数组、稀疏数组三元组编写可运行的 Python/C++/Java 代码，解决双指针去重、滑动窗口最短子数组、前缀和区域和、差分数组区间加法等问题；
4. 分析动态数组倍增扩容的均摊时间复杂度 $O(1)$ 论证，掌握聚合分析、势能分析、核算法三种均摊分析技术，证明”扩容代价 $O(n)$ 均摊到 $n$ 次操作上为 $O(1)$“的核心不变式；
5. 评估数组相对于链表、动态数组、平衡树在”随机访问密集”问题维度上的优劣，识别 CPU 缓存行预取、SIMD 向量化、内存对齐中的选型动机；
6. 对比静态数组、动态数组、循环缓冲区、稀疏数组、交错数组在内存开销、缓存友好性、扩容代价、实现复杂度维度的差异；
7. 创造性设计基于数组的开源项目解决方案，如环形缓冲区日志系统、位图索引、Bitmap 布隆过滤器、Redis ziplist 压缩列表、TensorFlow Tensor 张量存储。

1.3 术语表#

1.4 数组 vs 其他线性结构#

1.5 适用场景与不适用场景#

跨模块引用：数组的链式替代方案参见 链表；数组作为栈/队列底层存储参见 栈与队列；数组在哈希表开放寻址中的应用参见 哈希表；二分查找基于有序数组参见 查找算法；动态规划状态表参见 动态规划。

2. 历史动机与演进#

2.1 前数组时代：表与序列的早期抽象#

19 世纪末，数学家已使用”序列”（sequence）这一抽象概念描述有序元素集合。但计算机诞生前，“存储一个序列”的物理实现极其原始：穿孔卡片、纸带、继电器寄存器，每种介质对随机访问的支持都极弱。

1945 年 6 月，John von Neumann 在 Moore School of Electrical Engineering 完成了划时代的 101 页报告《First Draft of a Report on the EDVAC》，首次提出存储程序架构（stored-program architecture）：

• 程序与数据共享同一存储器；
• 存储器是线性编址的字序列，每个字有唯一地址；
• CPU 通过地址总线直接寻址任意存储单元。

这一架构（后称 Von Neumann 架构）天然支持”按地址随机访问”，为数组数据结构的诞生奠定了物理基础。所有现代计算机（x86、ARM、RISC-V）均基于此架构。

2.2 EDVAC 报告 1945：连续存储的物理实现#

Von Neumann 在 EDVAC 报告中将存储器描述为”an array of storage locations”，这是”array”一词首次在计算机科学文献中出现。报告明确指出：

存储器由 $n$ 个字组成，每个字的地址为 $0, 1, 2, \ldots, n-1$，CPU 可在单位时间内访问任意地址 $i$。

这一描述精确刻画了数组的两个核心性质：

1. 连续编址：地址线性递增，相邻元素的地址差固定；
2. 随机访问：任意地址访问时间相同（与位置无关）。

这两个性质至今仍是数组的核心定义。EDVAC 报告因此被视为数组数据结构的诞生地。

2.3 Iverson 1962：APL 与数组运算符#

1962 年，哈佛大学 Kenneth E. Iverson 出版《A Programming Language》（Wiley），首次将数组作为一等数据结构（first-class data structure）系统化定义：

• 引入维度（rank）、形状（shape）、元素（element）概念；
• 设计数组运算符 +、×、/、⍴（shape）、,（ravel）等；
• 提出广播（broadcast）规则，允许标量与数组运算；
• 后于 1968 年在 IBM 实现 APL 解释器。

Iverson 因此获 1979 年 ACM Turing Award，颁奖词明确指出”for his pioneering effort in programming languages and mathematical notation resulting in what has become APL”。

APL 的影响深远：NumPy、MATLAB、Julia、R 等数组编程语言均沿用其设计；现代深度学习框架（TensorFlow、PyTorch）的 Tensor 抽象本质上是 APL 多维数组运算的延伸。

2.4 McCarthy 1960：Lisp 与 list 的分野#

1960 年，MIT 的 John McCarthy 在 Communications of the ACM 3(4): 184-195 发表《Recursive functions of symbolic expressions and their computation by machine, Part I》，定义 Lisp 语言。

Lisp 选择链表而非数组作为主要数据结构，原因有二：

1. 符号计算中元素长度动态变化，数组连续存储不灵活；
2. 1950 年代内存稀缺，链表按需分配更节省空间。

这一分野奠定了数组（适合数值计算）与链表（适合符号计算）的二元对立，至今仍是数据结构选型的核心决策点。

2.5 Stepanov-Lee 1994：STL 与 std::vector#

1985 年，Bjarne Stroustrup 发布 C++ 1.0，但早期 C++ 标准库缺乏通用容器。1985-1994 年间，HP 实验室的 Alexander Stepanov 与 Meng Lee 在泛型编程思想指导下设计 STL（Standard Template Library），核心容器之一就是 std::vector：

• 模板参数化元素类型，类型安全；
• 自动管理内存，析构释放；
• 倍增扩容策略，size() == capacity() 时触发扩容；
• 提供 begin()、end()、operator[]、at() 等接口。

1994 年 STL 被 ANSI C++ 标准委员会采纳，1998 年 C++98 标准正式纳入 STL。std::vector 迅速成为 C++ 最常用的动态数组，影响了 Java ArrayList（1998）、C# List<T>（2002）、Rust Vec<T>（2010）等后续语言的设计。

Stepanov 在《From Mathematics to Generic Programming》（2014）中回忆：std::vector 的扩容策略借鉴了 Sedgewick 1983 年《Algorithms》第 1 版讨论的”倍增-复制”模式，而均摊 $O(1)$ 的论证则来自 Tarjan 1985 年《Amortized Complexity》的势能分析。

2.6 Gosling 1995：Java ArrayList 的诞生#

1995 年 Sun 公司发布 Java 1.0，初始集合框架仅有 Vector（线程安全但性能差）与 Hashtable。1998 年 Java 1.2 引入 Collections Framework，核心是 ArrayList：

• 非线程安全（性能优先），可用 Collections.synchronizedList 包装；
• 倍增策略：newCapacity = oldCapacity + (oldCapacity >> 1)，即 1.5 倍扩容；
• 底层是 Object[]，泛型通过擦除实现。

ArrayList 至今仍是 Java 最常用的动态数组实现。

2.7 Van Rossum 1991：Python list 的过分配策略#

1991 年 Guido van Rossum 发布 Python 0.9，list 是核心内建类型。CPython 的 list 实现采用过分配（over-allocation）策略，使扩容更温和：

// CPython listobject.c - list_resize 函数
// 过分配公式：newsize + (newsize >> 3) + (newsize < 9 ? 3 : 6)
// 对小 list 较激进，对大 list 渐近 ~1.125 倍扩容
new_allocated = newsize + (newsize >> 3) + (newsize < 9 ? 3 : 6);

这种温和扩容策略使 Python list 在内存占用与扩容次数之间取得平衡，每个 append 仍保持均摊 $O(1)$。

2.8 Cox 2009：Go slice 与三层抽象#

2009 年 Google 发布 Go 1.0，其动态数组 slice 设计独特：

// Go slice 底层结构（runtime/slice.go）
type slice struct {
    array unsafe.Pointer  // 底层数组指针
    len   int             // 长度
    cap   int             // 容量
}

slice 是对底层数组的视图（view），多个 slice 可共享同一底层数组。扩容策略（Go 1.18 后）：

• cap < 256：2 倍扩容；
• cap >= 256：newcap = oldcap + (oldcap + 3*256) / 4，渐近 1.25 倍。

这种设计兼顾小 slice 的快速扩容与大 slice 的内存节约，是工业级动态数组设计的典范。

2.9 演进时间线#

timeline
    title 数组与动态数组演进时间线
    1945 : Von Neumann EDVAC 报告 (存储程序架构 + array 概念)
    1957 : Fortran 1.0 (首个支持数组的高级语言)
    1958 : LISP 1.5 (选择链表而非数组)
    1962 : Iverson APL 书 (数组作为一等数据结构)
    1964 : BASIC 数组 (DIM 语句静态数组)
    1972 : C 语言诞生 (int arr[10] 静态数组 + malloc 动态分配)
    1985 : Stroustrup C++ 1.0 (new/delete 动态数组)
    1991 : Van Rossum Python 0.9 (list 过分配策略)
    1994 : Stepanov-Lee STL 设计 (std::vector)
    1995 : Gosling Java 1.0 (Vector 同步容器)
    1998 : Java 1.2 Collections Framework (ArrayList 1.5x 扩容)
    2002 : C# 1.0 List<T> (泛型动态数组)
    2009 : Cox Go 1.0 (slice 三层结构)
    2010 : Rust 1.0 Vec<T> (所有权安全动态数组)
    2024 : NumPy 2.0 ndarray (科学计算数组抽象)

2.10 关键设计决策#

数组演进过程中的 7 个关键设计决策：

1. 连续存储而非链式存储：牺牲插删效率换取 $O(1)$ 随机访问与缓存友好性；
2. 索引从 0 开始：简化地址计算 $\text{base} + i \times \text{size}$，避免减法偏移；
3. 静态大小向动态扩容演进：倍增扩容策略 + 均摊分析保证 $O(1)$ 追加；
4. 倍增而非线性增长：扩容代价摊到 $n$ 次操作后为 $O(1)$；
5. 过分配而非精确分配：CPython 的 ~1.125 倍策略平衡内存与扩容次数；
6. slice 视图而非拷贝：Go slice 多视图共享底层数组，节省内存；
7. 行优先存储：C/C++/Java 选择行优先，Fortran/MATLAB 选择列优先，源于科学计算惯例。

3. 形式化定义#

3.1 数组的数学定义#

数组 $A$ 是从索引集合 $I = \{0, 1, 2, \ldots, n-1\}$ 到数据域 $D$ 的一个全函数：

$A: I \to D, \quad A[i] \in D \quad \forall i \in I$

其核心性质：

1. 有限性：$|I| = n < \infty$；
2. 同质性：$\forall i, j \in I, A[i]$ 与 $A[j]$ 类型相同；
3. 线性序：$I$ 上存在全序关系 $<$，元素按序排列；
4. 连续存储：内存地址 $\text{addr}(A[i]) = \text{base} + i \times \text{size}$，其中 $\text{base}$ 为基地址，$\text{size}$ 为元素字节大小。

3.2 随机访问的形式化#

随机访问（Random Access）指：对于任意 $i \in I$，访问 $A[i]$ 的时间复杂度与 $i$ 无关，即 $T_{\text{access}}(i) = O(1)$。

证明（基于地址公式）：

$\text{addr}(A[i]) = \text{base} + i \times \text{size}$

计算 $\text{addr}(A[i])$ 需要：

• 1 次乘法（$i \times \text{size}$）
• 1 次加法（$+ \text{base}$）

均为常数时间 $O(1)$，与 $i$ 无关。这正是数组随机访问高效的根本原因。

3.3 ADT 定义#

ADT Array {
    数据对象：D = {a_i | a_i ∈ ElemSet, i = 0, 1, ..., n-1, n ≥ 0}
    数据关系：R = {<a_{i-1}, a_i> | a_{i-1}, a_i ∈ D, i = 1, ..., n-1}
                    且 a_i 在内存中连续存储
    基本操作：
        InitArray(&A, n)        : 构造长度为 n 的数组
        DestroyArray(&A)        : 销毁数组
        Length(A)               : 返回长度 n
        Get(A, i)               : 取第 i 个元素 (O(1))
        Set(&A, i, e)           : 修改第 i 个元素 (O(1))
        Insert(&A, i, e)        : 在位置 i 插入元素 (O(n))
        Delete(&A, i)           : 删除位置 i 的元素 (O(n))
        Traverse(A, visit)      : 遍历所有元素
}

ADT DynamicArray extends Array {
    基本操作：
        Append(&A, e)           : 尾部追加元素 (均摊 O(1))
        Resize(&A, newCap)      : 显式调整容量
        Capacity(A)             : 返回当前容量
        Shrink(&A)              : 自动缩容
}

3.4 复杂度表#

4. 静态数组的实现#

4.1 内存模型图解#

flowchart LR
    A[内存地址 base base+4 base+8 base+12 base+16<br/>索引 0 1 2 3 4<br/>元素 10 20 30 40 50<br/>base = 起始地址，size = 4 字节 int]

地址公式：address(A[i]) = base + i × 4

4.2 C++ 静态数组实现#

// C++ 静态数组三种形式
#include <array>
#include <cstddef>

// 形式 1：C 风格静态数组（栈分配，编译期确定大小）
int c_array[5] = {10, 20, 30, 40, 50};

// 形式 2：堆分配动态数组（手动管理内存）
int* heap_array = new int[5]{10, 20, 30, 40, 50};
delete[] heap_array;  // 必须手动释放

// 形式 3：C++11 std::array（栈分配 + STL 接口，推荐）
std::array<int, 5> stl_array = {10, 20, 30, 40, 50};

// 访问元素 O(1)
int val = stl_array[2];      // operator[] 无边界检查
int safe_val = stl_array.at(2);  // at() 有边界检查，越界抛 std::out_of_range

// 修改元素 O(1)
stl_array[3] = 100;

// 获取大小 O(1)
size_t size = stl_array.size();  // 5

// 遍历 O(n) - 缓存友好，CPU 预取
long long sum = 0;
for (size_t i = 0; i < stl_array.size(); ++i) {
    sum += stl_array[i];  // 连续内存访问，缓存命中率极高
}

4.3 Java 静态数组实现#

// Java 静态数组（堆分配，长度不可变）
int[] arr = new int[5];              // 默认值 0
int[] arr2 = {10, 20, 30, 40, 50};   // 直接初始化

// 访问 O(1)
int val = arr2[2];                   // 30

// 修改 O(1)
arr2[3] = 100;

// 长度 O(1)
int length = arr2.length;            // 5

// 遍历 O(n) - 增强型 for 循环
long sum = 0;
for (int x : arr2) {
    sum += x;
}

// 边界检查：Java 数组访问会自动进行，越界抛 ArrayIndexOutOfBoundsException
// int bad = arr2[10];  // 抛异常

4.4 Python 中的”数组”#

Python 没有原生的静态数组，list 本质是动态数组。如果需要真正的静态数组，可用 array 模块或 numpy：

import array
import numpy as np

# array.array: 类型化静态数组（C 类型，内存连续）
arr = array.array('i', [10, 20, 30, 40, 50])  # 'i' = signed int
print(arr[2])  # 30, O(1) 访问

# numpy.ndarray: 科学计算数组（内存连续 + 向量化运算）
np_arr = np.array([10, 20, 30, 40, 50], dtype=np.int32)
print(np_arr[2])  # 30, O(1) 访问
print(np_arr.sum())  # 150, C 层向量化求和，远快于 Python 循环

# Python list 也是动态数组，但元素是 PyObject* 指针，不连续存储数据
py_list = [10, 20, 30, 40, 50]
# 底层：PyObject* 数组 [ptr, ptr, ptr, ptr, ptr]
# 每个 ptr 指向独立的 int 对象，数据本身不连续

4.5 三语言对比表#

5. 动态数组的实现#

5.1 为什么需要动态数组#

静态数组在创建时必须指定大小，运行期无法改变。当元素数量超过容量时无法继续添加；当元素数量远小于容量时浪费内存。动态数组通过”预留空间 + 自动扩容”解决这一矛盾：

• 容量（capacity）：底层数组物理大小；
• 长度（size）：实际元素数；
• size < capacity 时 append 直接写入，$O(1)$；
• size == capacity 时触发扩容，分配新数组 + 复制元素，$O(n)$。

各语言动态数组实现：

5.2 倍增扩容机制#

flowchart LR
    B[扩容前 capacity=4 size=4<br/>10 20 30 40<br/>size=capacity 触发扩容]
    B --> N[扩容中 分配新数组+复制<br/>10 20 30 40 → 10 20 30 40 空 空 空 空<br/>新数组，新 capacity=8，旧数组释放]
    N --> A[扩容后追加 50<br/>10 20 30 40 50 空 空 空<br/>size=5 capacity=8]

5.3 Python 完整实现（含倍增扩容与缩容）#

from typing import Generic, TypeVar, Iterator
import sys

T = TypeVar('T')

class DynamicArray(Generic[T]):
    """动态数组完整实现（Python 3.9+ Generic 语法）

    特性：
    - 倍增扩容策略（2 倍）
    - 1/4 阈值缩容（避免抖动）
    - 索引边界检查
    - 支持 __getitem__ / __setitem__ / __len__ / __iter__
    - 内存友好：缩容后释放多余空间
    """

    def __init__(self, capacity: int = 10) -> None:
        if capacity < 0:
            raise ValueError(f'capacity must be non-negative, got {capacity}')
        self._data: list[T | None] = [None] * capacity
        self._size: int = 0
        self._capacity: int = capacity

    def __len__(self) -> int:
        """返回长度 O(1)"""
        return self._size

    def __getitem__(self, index: int) -> T:
        """索引访问 O(1)，支持负索引"""
        if index < 0:
            index += self._size
        if index < 0 or index >= self._size:
            raise IndexError(f'array index {index} out of range [0, {self._size})')
        return self._data[index]  # type: ignore

    def __setitem__(self, index: int, value: T) -> None:
        """索引修改 O(1)"""
        if index < 0:
            index += self._size
        if index < 0 or index >= self._size:
            raise IndexError(f'array index {index} out of range [0, {self._size})')
        self._data[index] = value

    def __iter__(self) -> Iterator[T]:
        """迭代器 O(n)"""
        for i in range(self._size):
            yield self._data[i]  # type: ignore

    def capacity(self) -> int:
        """返回当前容量 O(1)"""
        return self._capacity

    def is_empty(self) -> bool:
        """判空 O(1)"""
        return self._size == 0

    def append(self, value: T) -> None:
        """尾部追加，均摊 O(1)"""
        if self._size == self._capacity:
            self._resize(self._capacity * 2 if self._capacity > 0 else 1)
        self._data[self._size] = value
        self._size += 1

    def insert(self, index: int, value: T) -> None:
        """在 index 处插入 value O(n)"""
        if index < 0:
            index += self._size
        if index < 0 or index > self._size:
            raise IndexError(f'array index {index} out of range [0, {self._size}]')
        if self._size == self._capacity:
            self._resize(self._capacity * 2 if self._capacity > 0 else 1)
        # 从后向前移动元素，腾出 index 位置
        for i in range(self._size, index, -1):
            self._data[i] = self._data[i - 1]
        self._data[index] = value
        self._size += 1

    def pop(self, index: int | None = None) -> T:
        """删除并返回 index 处元素，默认删除末尾 O(n)"""
        if index is None:
            index = self._size - 1
        if index < 0:
            index += self._size
        if index < 0 or index >= self._size:
            raise IndexError(f'array index {index} out of range [0, {self._size})')
        removed: T = self._data[index]  # type: ignore
        # 从前向后移动元素，填补 index 空位
        for i in range(index, self._size - 1):
            self._data[i] = self._data[i + 1]
        self._data[self._size - 1] = None  # 帮助 GC
        self._size -= 1
        # 缩容：当 size < capacity/4 时缩容为 capacity/2
        # 阈值用 1/4 而非 1/2，避免在 1/2 附近反复扩缩导致抖动
        if 0 < self._size < self._capacity // 4 and self._capacity > 10:
            self._resize(max(self._capacity // 2, 10))
        return removed

    def remove(self, value: T) -> None:
        """删除第一个等于 value 的元素 O(n)"""
        for i in range(self._size):
            if self._data[i] == value:
                self.pop(i)
                return
        raise ValueError(f'{value!r} not in array')

    def _resize(self, new_capacity: int) -> None:
        """扩容/缩容核心：分配新数组 + 复制元素 O(n)"""
        new_data: list[T | None] = [None] * new_capacity
        for i in range(self._size):
            new_data[i] = self._data[i]
        self._data = new_data
        self._capacity = new_capacity

    def __repr__(self) -> str:
        return f'DynamicArray({list(self)!r}, capacity={self._capacity})'

# 使用示例
if __name__ == '__main__':
    arr: DynamicArray[int] = DynamicArray(capacity=2)
    for x in [10, 20, 30, 40, 50]:
        arr.append(x)
        print(f'append {x}: size={len(arr)}, capacity={arr.capacity()}')
    # 输出：
    # append 10: size=1, capacity=2
    # append 20: size=2, capacity=2
    # append 30: size=3, capacity=4   <- 触发扩容
    # append 40: size=4, capacity=4
    # append 50: size=5, capacity=8   <- 再次触发扩容

    print(arr[2])  # 30
    arr[2] = 99
    print(arr[2])  # 99

    arr.insert(1, 15)  # 在索引 1 处插入 15
    print(list(arr))   # [10, 15, 20, 99, 40, 50]

    arr.pop(0)  # 删除头部
    print(list(arr))   # [15, 20, 99, 40, 50]

5.4 C++ 完整实现#

// C++ 动态数组实现（类似 std::vector<T>）
#include <cstddef>
#include <stdexcept>
#include <utility>
#include <type_traits>
#include <initializer_list>

template <typename T>
class DynamicArray {
public:
    // 默认构造
    DynamicArray() : data_(nullptr), size_(0), capacity_(0) {}

    // 带初始容量构造
    explicit DynamicArray(size_t cap) : data_(nullptr), size_(0), capacity_(cap) {
        if (cap > 0) {
            data_ = static_cast<T*>(::operator new(cap * sizeof(T)));
        }
    }

    // 列表初始化
    DynamicArray(std::initializer_list<T> init) : DynamicArray(init.size()) {
        for (const auto& x : init) {
            push_back(x);
        }
    }

    // 拷贝构造
    DynamicArray(const DynamicArray& other) : DynamicArray(other.capacity_) {
        for (size_t i = 0; i < other.size_; ++i) {
            new (&data_[size_]) T(other.data_[i]);  // placement new
            ++size_;
        }
    }

    // 析构
    ~DynamicArray() { destroy(); }

    // 拷贝赋值
    DynamicArray& operator=(const DynamicArray& other) {
        if (this != &other) {
            destroy();
            capacity_ = other.capacity_;
            data_ = capacity_ > 0 ? static_cast<T*>(::operator new(capacity_ * sizeof(T))) : nullptr;
            for (size_t i = 0; i < other.size_; ++i) {
                new (&data_[size_]) T(other.data_[i]);
                ++size_;
            }
        }
        return *this;
    }

    // 元素访问 O(1)
    T& operator[](size_t i) { return data_[i]; }
    const T& operator[](size_t i) const { return data_[i]; }

    // 带边界检查的访问 O(1)
    T& at(size_t i) {
        if (i >= size_) throw std::out_of_range("index out of range");
        return data_[i];
    }

    // 尾部追加，均摊 O(1)
    void push_back(const T& value) {
        if (size_ == capacity_) reserve(capacity_ == 0 ? 1 : capacity_ * 2);
        new (&data_[size_]) T(value);  // placement new
        ++size_;
    }

    // 尾部追加（右值引用，支持移动语义）
    void push_back(T&& value) {
        if (size_ == capacity_) reserve(capacity_ == 0 ? 1 : capacity_ * 2);
        new (&data_[size_]) T(std::move(value));
        ++size_;
    }

    // 尾部删除 O(1)
    void pop_back() {
        if (size_ == 0) throw std::out_of_range("pop from empty array");
        --size_;
        data_[size_].~T();  // 显式析构
        // 缩容：当 size < capacity/4 时缩容为 capacity/2
        if (size_ < capacity_ / 4 && capacity_ > 16) {
            reserve(capacity_ / 2);
        }
    }

    // 在 index 处插入 O(n)
    void insert(size_t index, const T& value) {
        if (index > size_) throw std::out_of_range("insert index out of range");
        if (size_ == capacity_) reserve(capacity_ == 0 ? 1 : capacity_ * 2);
        // 从后向前移动元素（移动构造 + 析构）
        for (size_t i = size_; i > index; --i) {
            new (&data_[i]) T(std::move(data_[i - 1]));
            data_[i - 1].~T();
        }
        new (&data_[index]) T(value);
        ++size_;
    }

    // 删除 index 处元素 O(n)
    void erase(size_t index) {
        if (index >= size_) throw std::out_of_range("erase index out of range");
        data_[index].~T();
        for (size_t i = index; i < size_ - 1; ++i) {
            new (&data_[i]) T(std::move(data_[i + 1]));
            data_[i + 1].~T();
        }
        --size_;
    }

    // 预留容量 O(n)
    void reserve(size_t new_cap) {
        if (new_cap <= capacity_) return;
        T* new_data = static_cast<T*>(::operator new(new_cap * sizeof(T)));
        for (size_t i = 0; i < size_; ++i) {
            new (&new_data[i]) T(std::move(data_[i]));
            data_[i].~T();
        }
        ::operator delete(data_);
        data_ = new_data;
        capacity_ = new_cap;
    }

    // 容量与长度
    size_t size() const { return size_; }
    size_t capacity() const { return capacity_; }
    bool empty() const { return size_ == 0; }

private:
    T* data_;
    size_t size_;
    size_t capacity_;

    void destroy() {
        for (size_t i = 0; i < size_; ++i) {
            data_[i].~T();
        }
        ::operator delete(data_);
        data_ = nullptr;
        size_ = capacity_ = 0;
    }
};

5.5 Java 完整实现#

import java.util.Iterator;
import java.util.NoSuchElementException;

/**
 * 泛型动态数组完整实现（类似 java.util.ArrayList<E>）。
 *
 * <p>特性：
 * <ul>
 *   <li>1.5 倍扩容策略（与 OpenJDK ArrayList 一致）</li>
 *   <li>1/4 阈值缩容</li>
 *   <li>支持泛型、Iterable 接口</li>
 *   <li>fail-fast 迭代器（简化版）</li>
 * </ul>
 */
public class DynamicArray<E> implements Iterable<E> {
    private static final int DEFAULT_CAPACITY = 10;
    private static final Object[] EMPTY_ARRAY = {};

    private Object[] data;
    private int size;

    public DynamicArray() {
        this.data = EMPTY_ARRAY;  // 延迟分配，节省空数组内存
        this.size = 0;
    }

    public DynamicArray(int initialCapacity) {
        if (initialCapacity < 0) {
            throw new IllegalArgumentException("Illegal capacity: " + initialCapacity);
        }
        this.data = new Object[initialCapacity];
        this.size = 0;
    }

    public int size() { return size; }
    public int capacity() { return data.length; }
    public boolean isEmpty() { return size == 0; }

    @SuppressWarnings("unchecked")
    public E get(int index) {
        checkIndex(index);
        return (E) data[index];
    }

    public E set(int index, E element) {
        checkIndex(index);
        @SuppressWarnings("unchecked")
        E old = (E) data[index];
        data[index] = element;
        return old;
    }

    /** 尾部追加，均摊 O(1)。 */
    public boolean add(E element) {
        ensureCapacity(size + 1);
        data[size++] = element;
        return true;
    }

    /** 在 index 处插入 O(n)。 */
    public void add(int index, E element) {
        if (index < 0 || index > size) {
            throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
        }
        ensureCapacity(size + 1);
        // 从后向前移动元素
        System.arraycopy(data, index, data, index + 1, size - index);
        data[index] = element;
        size++;
    }

    /** 删除 index 处元素 O(n)。 */
    @SuppressWarnings("unchecked")
    public E remove(int index) {
        checkIndex(index);
        E removed = (E) data[index];
        int numMoved = size - index - 1;
        if (numMoved > 0) {
            System.arraycopy(data, index + 1, data, index, numMoved);
        }
        data[--size] = null;  // 帮助 GC
        // 缩容：当 size < capacity/4 且容量大于默认值时缩容
        if (size < data.length / 4 && data.length > DEFAULT_CAPACITY) {
            shrink();
        }
        return removed;
    }

    /** 扩容核心：1.5 倍策略。 */
    private void ensureCapacity(int minCapacity) {
        if (minCapacity > data.length) {
            int newCapacity = data.length + (data.length >> 1);  // 1.5 倍
            if (newCapacity < minCapacity) newCapacity = minCapacity;
            Object[] newData = new Object[newCapacity];
            System.arraycopy(data, 0, newData, 0, size);
            data = newData;
        }
    }

    /** 缩容：缩为 capacity/2，但不小于 DEFAULT_CAPACITY。 */
    private void shrink() {
        int newCapacity = Math.max(data.length >> 1, DEFAULT_CAPACITY);
        Object[] newData = new Object[newCapacity];
        System.arraycopy(data, 0, newData, 0, size);
        data = newData;
    }

    private void checkIndex(int index) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
        }
    }

    @Override
    public Iterator<E> iterator() {
        return new ArrayIterator();
    }

    private class ArrayIterator implements Iterator<E> {
        private int cursor = 0;

        @Override public boolean hasNext() { return cursor < size; }

        @Override
        @SuppressWarnings("unchecked")
        public E next() {
            if (!hasNext()) throw new NoSuchElementException();
            return (E) data[cursor++];
        }
    }
}

5.6 三语言实现对比表#

6. 均摊复杂度分析#

6.1 为什么需要均摊分析#

动态数组的 append 操作大多数时候是 $O(1)$（直接写入），偶尔触发扩容时是 $O(n)$（分配新数组 + 复制 $n$ 个元素）。最坏情况分析会得出 $O(n)$，但这过于悲观——因为扩容很少发生。

均摊分析（Amortized Analysis）是评估”一系列操作平均代价”的方法，由 Tarjan 1985 年在《Amortized Complexity》中系统化。CLRS 第 17 章详细讨论了三种均摊分析技术：

1. 聚合分析（Aggregate Analysis）
2. 核算法（Accounting Method）
3. 势能法（Potential Method）

6.2 聚合分析法#

思路：计算 $n$ 次操作的总代价 $T(n)$，再除以 $n$ 得到均摊代价 $\hat{c} = T(n)/n$。

场景：从空数组开始连续 $n$ 次 append，倍增扩容（2 倍策略）。

扩容发生在第 1, 2, 4, 8, 16, …, $2^k$ 次插入时（即 $2^k \leq n < 2^{k+1}$）。

总代价：

$T(n) = \underbrace{n}_{\text{写入代价}} + \underbrace{\sum_{i=0}^{\lfloor \log_2 n \rfloor} 2^i}_{\text{扩容代价}} = n + (2^{\lfloor \log_2 n \rfloor + 1} - 1) \leq n + 2n - 1 = 3n - 1$

均摊代价：

$\hat{c} = \frac{T(n)}{n} \leq \frac{3n - 1}{n} = 3 - \frac{1}{n} = O(1)$

因此 append 的均摊复杂度为 $O(1)$。

6.3 势能分析法#

思路：定义势函数 $\Phi(D_i)$ 表示数据结构 $D_i$ 在第 $i$ 次操作后的”势能”，均摊代价 $\hat{c}_i = c_i + \Phi(D_i) - \Phi(D_{i-1})$。

关键：选择合适的势函数，使均摊代价易于计算且上界可控。

场景：倍增扩容策略下，定义势函数：

$\Phi(D_i) = 2 \times \text{size}_i - \text{capacity}_i$

（其中 $\text{size}_i$ 为长度，$\text{capacity}_i$ 为容量）

初始：$\Phi(D_0) = 0$（空数组）。

情况 1：第 $i$ 次操作不触发扩容（$\text{size}_i < \text{capacity}_i$）

• 实际代价 $c_i = 1$（仅写入）
• 势能变化 $\Phi(D_i) - \Phi(D_{i-1}) = 2(\text{size}_i - \text{size}_{i-1}) = 2$
• 均摊代价 $\hat{c}_i = 1 + 2 = 3 = O(1)$

情况 2：第 $i$ 次操作触发扩容（$\text{size}_i = \text{capacity}_{i-1} + 1$，扩容前 $\text{size}_{i-1} = \text{capacity}_{i-1}$）

• 实际代价 $c_i = \text{size}_{i-1} + 1$（复制 $\text{size}_{i-1}$ 个 + 写入 1 个）
• 扩容后 $\text{capacity}_i = 2 \times \text{capacity}_{i-1}$
• 势能变化 $\Phi(D_i) - \Phi(D_{i-1}) = (2(\text{size}_{i-1} + 1) - 2 \text{capacity}_{i-1}) - (2 \text{size}_{i-1} - \text{capacity}_{i-1})$ $= 2 - \text{capacity}_{i-1} = 2 - \text{size}_{i-1}$
• 均摊代价 $\hat{c}_i = (\text{size}_{i-1} + 1) + (2 - \text{size}_{i-1}) = 3 = O(1)$

两种情况均摊代价均为 3，故 append 的均摊复杂度为 $O(1)$。

6.4 核算法#

思路：为每次操作”预付”代价，部分用于当前操作，部分存入”信用”（credit），用于未来扩容。

场景：倍增扩容策略下，每次 append 预付 3 单位代价：

• 1 单位用于当前写入；
• 1 单位存入信用，用于将来将该元素从旧数组复制到新数组；
• 1 单位存入信用，用于将来将”前一次扩容后第一个元素”从旧数组复制到新数组。

当扩容发生时，需要复制 $n$ 个元素，恰好可由累积的 $n$ 单位信用支付（每个元素已预存 1 单位复制代价）。

结论：每次 append 预付 3 单位，足够支付扩容代价，故均摊代价 $O(1)$。

6.5 缩容的均摊分析#

缩容策略：当 $\text{size} < \text{capacity}/4$ 时缩容为 $\text{capacity}/2$。

为什么用 1/4 而非 1/2？ 假设用 1/2，则在 $\text{size} = \text{capacity}/2$ 附近反复 append/pop 会反复触发扩容缩容，抖动（thrashing）导致均摊复杂度退化为 $O(n)$。

1/4 阈值的均摊正确性：定义势函数

$\Phi(D_i) = \begin{cases} 2 \times \text{size}_i - \text{capacity}_i & \text{if } \text{size}_i \geq \text{capacity}_i / 2 \\ \text{capacity}_i / 2 - \text{size}_i & \text{if } \text{size}_i < \text{capacity}_i / 2 \end{cases}$

可证明 append 与 pop 的均摊代价均为 $O(1)$（详见 CLRS 习题 17.3-6）。

6.6 三种方法对比#

7. 多维数组#

7.1 二维数组的两种存储顺序#

二维数组 $A[m][n]$ 在内存中是一维的，需要选择存储顺序：

行优先（Row-major）——C/C++/Java/Python 等大多数语言：

A[0][0] A[0][1] A[0][2] A[1][0] A[1][1] A[1][2] A[2][0] A[2][1] A[2][2]

地址公式：

$\text{addr}(A[i][j]) = \text{base} + (i \times n + j) \times \text{size}$

列优先（Column-major）——Fortran/MATLAB/Julia 等：

A[0][0] A[1][0] A[2][0] A[0][1] A[1][1] A[2][1] A[0][2] A[1][2] A[2][2]

地址公式：

$\text{addr}(A[i][j]) = \text{base} + (j \times m + i) \times \text{size}$

7.2 缓存友好性差异#

// 缓存友好（行优先遍历）
for (int i = 0; i < m; ++i) {
    for (int j = 0; j < n; ++j) {
        sum += A[i][j];  // 相邻 j 内存相邻，缓存命中率高
    }
}

// 缓存不友好（列优先遍历）
for (int j = 0; j < n; ++j) {
    for (int i = 0; i < m; ++i) {
        sum += A[i][j];  // 相邻 i 内存跨行，缓存命中率低
    }
}

对于 $1024 \times 1024$ 的 int 数组（4 MB），行优先遍历可比列优先快 5-10 倍（取决于缓存大小）。

7.3 用一维数组模拟二维数组#

// C++：用一维数组模拟二维数组（缓存友好 + 节省内存）
class Matrix2D {
public:
    Matrix2D(int rows, int cols) : rows_(rows), cols_(cols), data_(new int[rows * cols]()) {}

    ~Matrix2D() { delete[] data_; }

    // 行优先索引
    int& operator()(int i, int j) {
        return data_[i * cols_ + j];
    }

    const int& operator()(int i, int j) const {
        return data_[i * cols_ + j];
    }

    int rows() const { return rows_; }
    int cols() const { return cols_; }

private:
    int rows_;
    int cols_;
    int* data_;
};

// 使用
Matrix2D mat(3, 4);
mat(1, 2) = 42;  // 等价于 mat.data_[1 * 4 + 2] = 42

7.4 交错数组（Jagged Array）#

交错数组是”数组的数组”，每行长度可不同：

// Java 交错数组
int[][] jagged = {
    {1, 2, 3},
    {4, 5},
    {6, 7, 8, 9}
};

// 访问
int val = jagged[1][1];  // 5
int rowLen = jagged[2].length;  // 4

flowchart LR
    J0[jagged[0] → [1, 2, 3]]
    J1[jagged[1] → [4, 5]]
    J2[jagged[2] → [6, 7, 8, 9]]

交错数组 vs 二维数组：

7.5 三维与高维数组#

三维数组 $A[d_1][d_2][d_3]$（行优先）地址公式：

$\text{addr}(A[i][j][k]) = \text{base} + (i \times d_2 \times d_3 + j \times d_3 + k) \times \text{size}$

一般地，$n$ 维数组 $A[d_1][d_2] \cdots [d_n]$（行优先）地址公式：

$\text{addr}(A[i_1][i_2] \cdots [i_n]) = \text{base} + \left(\sum_{k=1}^{n} i_k \prod_{j=k+1}^{n} d_j\right) \times \text{size}$

8. 稀疏数组#

8.1 什么是稀疏数组#

当数组中绝大多数元素为 0（或同一默认值）时，称为稀疏数组（Sparse Array）。直接存储 $m \times n$ 数组浪费 $O(mn)$ 空间，而稀疏存储仅需 $O(k)$（$k$ 为非零元素数）。

典型应用：

• 五子棋棋盘（19×19，但落子位置仅数十个）
• 地理信息系统栅格（大部分区域无数据）
• 推荐系统用户-物品矩阵（用户只评分少数物品）
• 神经网络权重剪枝（90%+ 权重为 0）

8.2 三元组表（COO 格式）#

最简单的稀疏存储：仅记录非零元素的 (row, col, value) 三元组。

# Python：稀疏数组的三元组表存储
from typing import List, Tuple

class SparseMatrix:
    """COO (Coordinate) 格式稀疏矩阵"""

    def __init__(self, rows: int, cols: int):
        self.rows = rows
        self.cols = cols
        self.triplets: List[Tuple[int, int, float]] = []  # [(row, col, value), ...]

    def set(self, i: int, j: int, value: float) -> None:
        """设置元素"""
        if value != 0:
            self.triplets.append((i, j, value))

    def get(self, i: int, j: int) -> float:
        """获取元素 O(k)"""
        for (r, c, v) in self.triplets:
            if r == i and c == j:
                return v
        return 0.0

    def to_dense(self) -> List[List[float]]:
        """转换为稠密矩阵 O(rows × cols + k)"""
        dense = [[0.0] * self.cols for _ in range(self.rows)]
        for (r, c, v) in self.triplets:
            dense[r][c] = v
        return dense

    def density(self) -> float:
        """稀疏度 = 非零元素 / 总元素"""
        return len(self.triplets) / (self.rows * self.cols)

# 示例：五子棋棋盘
board = SparseMatrix(19, 19)
board.set(10, 10, 1)  # 黑子
board.set(10, 11, 2)  # 白子
board.set(11, 10, 1)  # 黑子
print(f'密度: {board.density():.4f}')  # 0.0083 (3/361)

8.3 CSR 格式（Compressed Sparse Row）#

CSR 是科学计算中常用的稀疏矩阵格式，支持高效行切片与矩阵乘法：

class CSRMatrix:
    """CSR (Compressed Sparse Row) 格式稀疏矩阵

    数据结构：
    - values: 非零元素值数组
    - col_indices: 非零元素列索引数组
    - row_ptr: 行指针数组，row_ptr[i] 到 row_ptr[i+1]-1 是第 i 行的非零元素
    """

    def __init__(self, dense: List[List[float]]):
        self.rows = len(dense)
        self.cols = len(dense[0]) if dense else 0
        self.values: List[float] = []
        self.col_indices: List[int] = []
        self.row_ptr: List[int] = [0]  # row_ptr[0] = 0

        for i in range(self.rows):
            for j in range(self.cols):
                if dense[i][j] != 0:
                    self.values.append(dense[i][j])
                    self.col_indices.append(j)
            self.row_ptr.append(len(self.values))

    def get(self, i: int, j: int) -> float:
        """获取元素 O(nnz_row)，nnz_row 为第 i 行非零元素数"""
        for k in range(self.row_ptr[i], self.row_ptr[i + 1]):
            if self.col_indices[k] == j:
                return self.values[k]
        return 0.0

    def row(self, i: int) -> List[float]:
        """获取第 i 行 O(cols)"""
        result = [0.0] * self.cols
        for k in range(self.row_ptr[i], self.row_ptr[i + 1]):
            result[self.col_indices[k]] = self.values[k]
        return result

8.4 CSR vs COO vs CSC 对比#

9. 数组经典算法技巧#

9.1 双指针技巧#

思路：用两个指针协同遍历，将 $O(n^2)$ 降为 $O(n)$。

9.1.1 快慢指针（原地去重）

// LeetCode 26：删除有序数组中的重复项（原地）
public int removeDuplicates(int[] nums) {
    if (nums.length == 0) return 0;
    int slow = 0;  // 慢指针：唯一元素的写入位置
    for (int fast = 1; fast < nums.length; fast++) {  // 快指针：扫描所有元素
        if (nums[fast] != nums[slow]) {
            nums[++slow] = nums[fast];  // 发现新元素，写入
        }
    }
    return slow + 1;
}

9.1.2 左右指针（两数之和）

# LeetCode 167：两数之和 II（有序数组）
def two_sum_sorted(nums: list[int], target: int) -> list[int]:
    left, right = 0, len(nums) - 1
    while left < right:
        s = nums[left] + nums[right]
        if s == target:
            return [left + 1, right + 1]  # 1-based
        elif s < target:
            left += 1
        else:
            right -= 1
    return []  # 无解

9.2 滑动窗口#

思路：维护一个窗口 [left, right]，根据条件扩张或收缩，解决子数组/子串问题。

# LeetCode 209：长度最小的子数组（和 ≥ target）
def min_sub_array_len(target: int, nums: list[int]) -> int:
    n = len(nums)
    left = 0
    total = 0
    min_len = float('inf')

    for right in range(n):
        total += nums[right]  # 扩张右边界
        while total >= target:
            min_len = min(min_len, right - left + 1)
            total -= nums[left]  # 收缩左边界
            left += 1

    return min_len if min_len != float('inf') else 0

# 复杂度：O(n) - 每个元素至多被 left 和 right 各访问一次

9.2.1 滑动窗口模板

def sliding_window_template(s: str) -> int:
    """滑动窗口通用模板"""
    left = 0
    window = {}  # 窗口内元素的计数/状态
    result = 0

    for right in range(len(s)):
        # 1. 扩张右边界，更新窗口状态
        c = s[right]
        window[c] = window.get(c, 0) + 1

        # 2. 收缩左边界（当窗口不满足条件时）
        while window_invalid(window):  # 替换为具体的判断条件
            d = s[left]
            window[d] -= 1
            if window[d] == 0:
                del window[d]
            left += 1

        # 3. 更新结果
        result = max(result, right - left + 1)

    return result

9.3 前缀和#

思路：预处理前缀和数组，将区间求和从 $O(n)$ 降为 $O(1)$。

# LeetCode 303：区域和检索 - 数组不可变
class NumArray:
    def __init__(self, nums: list[int]):
        # 前缀和数组：prefix[i] = nums[0] + nums[1] + ... + nums[i-1]
        # prefix[0] = 0（哨兵）
        self.prefix = [0] * (len(nums) + 1)
        for i in range(len(nums)):
            self.prefix[i + 1] = self.prefix[i] + nums[i]

    def sum_range(self, left: int, right: int) -> int:
        """区间和 O(1)"""
        return self.prefix[right + 1] - self.prefix[left]

# 复杂度：
# - 构造：O(n)
# - 查询：O(1)
# - 空间：O(n)

数学定义：

$\text{prefix}[i] = \sum_{k=0}^{i-1} \text{nums}[k], \quad \text{prefix}[0] = 0$

$\text{sum}(\text{nums}[l..r]) = \text{prefix}[r+1] - \text{prefix}[l]$

9.4 差分数组#

思路：差分是前缀和的逆运算，将区间更新从 $O(n)$ 降为 $O(1)$。

数学定义：

$\text{diff}[i] = \text{nums}[i] - \text{nums}[i-1], \quad \text{diff}[0] = \text{nums}[0]$

核心性质：

• 原数组是差分数组的前缀和：$\text{nums}[i] = \sum_{k=0}^{i} \text{diff}[k]$
• 对原数组区间 $[l, r]$ 加 $c$，等价于 $\text{diff}[l] += c, \text{diff}[r+1] -= c$

# LeetCode 1109：航班预订统计
def corp_flight_bookings(bookings: list[list[int]], n: int) -> list[int]:
    """n 个航班，bookings[i] = [first, last, seats]
    表示预订 first 到 last 航班的 seats 个座位
    返回每个航班最终预订数"""
    diff = [0] * (n + 1)  # 差分数组

    for first, last, seats in bookings:
        diff[first - 1] += seats  # 0-indexed
        diff[last] -= seats       # last+1 位置减去

    # 还原原数组（前缀和）
    result = [0] * n
    running = 0
    for i in range(n):
        running += diff[i]
        result[i] = running
    return result

# 复杂度：
# - 区间更新：O(1)
# - 还原：O(n)
# - 总复杂度：O(n + m)，m 为 bookings 数量

9.5 前缀和与差分对比#

10. CPU 缓存友好性#

10.1 CPU 缓存层次结构#

现代 CPU 的存储层次：

寄存器 (1 cycle, 1ns)
    ↓
L1 缓存 (4 cycles, ~1ns, 32KB)
    ↓
L2 缓存 (10 cycles, ~3ns, 256KB)
    ↓
L3 缓存 (40 cycles, ~10ns, 8MB)
    ↓
主内存 (100+ cycles, ~100ns, GB 级)
    ↓
SSD (100000 cycles, ~100us, TB 级)

关键观察：主内存访问比 L1 缓存慢 100 倍。因此，缓存命中率（cache hit rate）对性能影响巨大。

10.2 缓存行（Cache Line）#

CPU 不是按字节访问内存，而是以缓存行（cache line）为单位，通常为 64 字节。访问数组中一个元素时，整个 64 字节缓存行会被加载到 L1。

数组: [10, 20, 30, 40, 50, 60, 70, 80, 90, 100, ...]
       └─── 缓存行 1 (64B = 16 个 int) ───┘  └─── 缓存行 2 ───┘

访问 nums[0] → 加载缓存行 1，nums[0..15] 均在缓存中
访问 nums[1] → 缓存命中！
访问 nums[2] → 缓存命中！
...

结论：数组连续存储天然具备良好的空间局部性（spatial locality），顺序遍历缓存命中率接近 100%。

10.3 数组 vs 链表的缓存性能#

// 实验代码：数组 vs 链表求和性能对比
#include <chrono>
#include <iostream>
#include <vector>
#include <list>

int main() {
    const int N = 10'000'000;

    // 数组（连续存储）
    std::vector<int> arr(N);
    for (int i = 0; i < N; ++i) arr[i] = i;

    // 链表（离散存储）
    std::list<int> lst(arr.begin(), arr.end());

    // 数组求和
    auto t1 = std::chrono::high_resolution_clock::now();
    long long sum1 = 0;
    for (int x : arr) sum1 += x;
    auto t2 = std::chrono::high_resolution_clock::now();
    auto arr_time = std::chrono::duration_cast<std::chrono::microseconds>(t2 - t1).count();

    // 链表求和
    auto t3 = std::chrono::high_resolution_clock::now();
    long long sum2 = 0;
    for (int x : lst) sum2 += x;
    auto t4 = std::chrono::high_resolution_clock::now();
    auto lst_time = std::chrono::duration_cast<std::chrono::microseconds>(t4 - t3).count();

    std::cout << "数组求和: " << arr_time << " us\n";
    std::cout << "链表求和: " << lst_time << " us\n";
    std::cout << "数组 / 链表 = " << static_cast<double>(arr_time) / lst_time << "\n";

    return 0;
}

典型结果（N = 1000 万，int 元素）：

数组比链表快 10 倍！这正是 Big-O 分析之外的真实性能差异。

10.4 SIMD 向量化#

现代 CPU 支持 SIMD（Single Instruction Multiple Data）指令集，一条指令同时处理多个数据：

// C++ AVX2 向量化求和（一次处理 8 个 int）
#include <immintrin.h>

long long sum_avx2(const int* arr, size_t n) {
    __m256i vsum = _mm256_setzero_si256();  // 8 个 int 累加器
    size_t i = 0;
    for (; i + 8 <= n; i += 8) {
        __m256i v = _mm256_loadu_si256(reinterpret_cast<const __m256i*>(arr + i));
        vsum = _mm256_add_epi32(vsum, v);  // 一次加 8 个 int
    }
    // 水平求和
    int tmp[8];
    _mm256_storeu_si256(reinterpret_cast<__m256i*>(tmp), vsum);
    long long sum = 0;
    for (int j = 0; j < 8; ++j) sum += tmp[j];
    // 处理剩余元素
    for (; i < n; ++i) sum += arr[i];
    return sum;
}

// 编译器通常会自动向量化简单的数组遍历
// 启用 -O3 -mavx2 后，普通 for 循环也能获得 AVX2 加速

关键：SIMD 要求数据连续存储且对齐，链表无法向量化。这是数组在数值计算中的根本优势。

10.5 内存对齐#

// 内存对齐影响性能
struct Misaligned {
    char c;     // 1 字节
    int i;      // 4 字节（未对齐）
    char d;     // 1 字节
};
// sizeof(Misaligned) = 12 (编译器可能填充)

struct Aligned {
    int i;      // 4 字节（对齐）
    char c;     // 1 字节
    char d;     // 1 字节
    // 2 字节填充
};
// sizeof(Aligned) = 8

// C++11 显式对齐
struct alignas(64) CacheLineAligned {  // 64 字节对齐（缓存行）
    int data[16];
};

11. 工程实践#

11.1 预分配容量#

// 反例：频繁扩容
List<Integer> list = new ArrayList<>();  // 默认容量 10
for (int i = 0; i < 100_000; i++) {
    list.add(i);  // 触发约 14 次扩容（10→15→22→...→91106）
}

// 正例：预分配容量
List<Integer> list = new ArrayList<>(100_000);  // 一次性分配
for (int i = 0; i < 100_000; i++) {
    list.add(i);  // 无扩容
}

11.2 批量插入优于逐个插入#

// 反例：逐个 push_back
std::vector<int> vec;
for (int i = 0; i < 10000; ++i) {
    vec.push_back(i);  // 多次扩容
}

// 正例：reserve + 批量
std::vector<int> vec;
vec.reserve(10000);  // 一次性分配
for (int i = 0; i < 10000; ++i) {
    vec.push_back(i);  // 无扩容，直接写入
}

// 更优：直接构造大小
std::vector<int> vec(10000);
for (int i = 0; i < 10000; ++i) {
    vec[i] = i;
}

11.3 避免在中间频繁插入#

# 反例：在列表头部反复插入
result = []
for item in data:
    result.insert(0, item)  # 每次 O(n)，总 O(n²)

# 正例：尾部追加 + 反转
result = []
for item in data:
    result.append(item)  # 均摊 O(1)
result.reverse()  # O(n)
# 总复杂度 O(n)