第1章 Introduction：算法工程与存储模型

从算法的可执行定义出发，比较 RAM 模型与真实存储层次，用两级存储模型、I/O 复杂度和局部性解释相同步数为何可能产生悬殊性能。

从“都做 n 次加法”为何不一定一样快开始

设数组里有 n 个整数。程序甲从左到右相加，程序乙按照一个与数组长度互素的大步长绕圈访问，直到每个位置恰好访问一次。两者都读取 n 个元素、执行 n 次加法，在传统复杂度分析中都是线性时间。

先预测：当数组远大于缓存和内存、必须从外部存储读取时，两者仍会一样快吗？顺序扫描可以把刚取入的一整页连续消费；大步长访问可能每次只用一小部分页面，甚至在远处页面之间来回跳转。相同的 RAM 步数没有说明每一步从哪一级存储取数，也没有说明一次传输带来的其余数据是否被利用。

这正是 algorithm engineering（算法工程） 的起点：算法不是写完证明就结束，还要把计算模型、理论边界、数据布局、实现细节和真实实验放进同一个判断过程。

先确认什么才算算法

原书从算法的基本约束出发。一个过程必须在有限步骤后终止，每一步含义明确且能够实际执行；它接收规定集合中的输入，并产生满足问题关系的输出。只写“不断尝试直到足够好”并不是完整算法，因为“足够好”与终止条件都没有被定义。

六类约束会直接影响工程实现。例如，“有限”不仅是数学上最终终止，还应追问在目标数据规模上资源是否可接受；“明确”要求把空输入、溢出、并列答案与错误处理写进契约；“有效”要求模型里的一步能够落实为机器支持的操作。

因此，正确性回答“输出是否满足规格”，复杂度回答“资源怎样随规模增长”，工程验证回答“在目标机器和工作负载上是否真的可用”。三者缺一不可。

RAM 模型给出的第一层答案

把机器抽象为能够随机访问任意地址的统一内存。若一段程序执行的基本操作数为 T(n)，使用的存储单元数为 S(n)，通常写作：

T(n)=∑k=1mck(n),S(n)=同时存活的存储单元数T(n)=\sum_{k=1}^{m} c_k(n), \qquad S(n)=\text{同时存活的存储单元数}

其中 c_k(n) 是第 k 类常数时间操作的执行次数。这个模型能隔离机器频率、编译器和设备型号，帮助我们比较线性、平方、指数等增长率。输入规模增大时，算法增长率通常比“换一台快几倍的机器”更重要。

RAM 模型的问题不在于它无用，而在于它有意忽略了存储访问的不均匀性。寄存器、缓存、主存、SSD、机械磁盘和远端对象存储的容量、延迟、带宽、传输粒度完全不同。把所有访问都计成一个常数步骤，可能把两个现实表现悬殊的算法判为等价。

RAM 分析清单
1. 定义输入规模 n 与基本操作
2. 证明输出满足规格
3. 计算最坏、平均或期望 T(n)
4. 计算峰值空间 S(n)
5. 标记模型未表达的访问模式与设备假设

最后一项不是推翻前四项，而是为下一层模型留下接口。

存储层次改变了“访问一次”的含义

现代机器的要求算法区分“数据在哪里”和“怎样搬运”。靠近 CPU 的层级容量小、延迟低；越远的层级容量通常更大，但一次访问更贵，而且往往按缓存行、页、块或网络请求批量传输。

假如一个磁盘页包含 B 个元素，读取页中一个元素的外部传输成本与读取整页相同。算法真正获得的是 B 个相邻元素，不只是请求的那一个。能否继续使用其余 B 减 1 个元素，决定了这次传输是否值得。

同理，刚在内部存储中使用过的数据若很快再用，可能仍在缓存；隔很久再访问则可能已经被淘汰。访问序列而非单条指令，才是理解性能的单位。

两级存储模型抽出最主要的瓶颈

只保留两个层级：

  • 内部存储最多容纳 M 个元素；
  • 外部存储容量视为无界；
  • 每次输入或输出传输一个含 B 个元素的页；
  • 若有 D 个并行磁盘，一次可传输 D 个页，也就是 D 乘 B 个元素。

在这个模型里，算法至少要报告页传输数、内部 CPU 时间和外部工作空间。顺序读取 n 个连续元素需要：

Scan⁡(n)=⌈nB⌉次 I/O\operatorname{Scan}(n)=\left\lceil\frac{n}{B}\right\rceil \quad\text{次 I/O}

这里的不等于 CPU 步数。顺序扫描仍做 n 次处理，却只在每跨过一个页边界时产生一次外部读取。

两级视图并不只用于“磁盘对内存”。可以选择缓存对主存、主存对 SSD，甚至本地存储对远端存储，只要 M、B 和一次传输的含义与目标层级一致。

A(s,b) 访问族：步数相同，I/O 不同

原章用 A(s,b) 家族计算数组总和。把数组逻辑上分成每块 b 个元素，处理完一个逻辑块后向右跳 s 个逻辑块；数组视为环，且选择 s 与逻辑块数量互素，使所有块最终各访问一次。

无论 s 和 b 取何值，算法都读取全部 n 个整数并做 n 次加法，所以 RAM 成本相同。若一个物理页含 B 个元素，在整除等简化假设下，其 I/O 估计为：

QA(s,b)(n)=min⁡{s,Bb}nBQ_{A(s,b)}(n) = \min\left\{s,\frac{B}{b}\right\} \frac{n}{B}

当 s 等于 1 时，算法向右扫描，成本是 n 除 B；当 s 等于 2 且 b 小于 B 时，一个页面里的逻辑块约有一半在当前访问周期被利用，成本变为 2n 除 B；当跳跃足够大时，成本退化为 n 除 b。

下面的伪代码刻意把访问顺序暴露出来。visited 只是教学用来说明“每块一次”；在满足互素条件时可以省去。

long long cyclic_block_sum(
    const std::vector<int>& data,
    std::size_t logical_block,
    std::size_t stride) {
    const std::size_t blocks =
        data.size() / logical_block;
    std::vector<bool> visited(blocks, false);
    std::size_t block = 0;
    long long sum = 0;
 
    for (std::size_t count = 0;
         count != blocks;
         ++count) {
        if (visited[block])
            throw std::logic_error("stride is not coprime");
        visited[block] = true;
 
        const std::size_t begin =
            block * logical_block;
        for (std::size_t offset = 0;
             offset != logical_block;
             ++offset)
            sum += data[begin + offset];
 
        block = (block + stride) % blocks;
    }
    return sum;
}

这段程序也提示了模型之外的现实差异：当 b 等于 B 时，不同 s 都可能得到 n 除 B 次 I/O，但顺序页面与随机页面在机械寻道、预取、请求合并和远端往返上仍不同。因此原章建议除了 I/O 数量，还描述连续或随机的分布。

两条黄金规则：空间与时间局部性

要求每次取入页面后尽可能消费其中更多相邻元素。顺序数组、紧凑结构、批量请求和连续写入通常表现良好；跨页步长和随机指针追逐通常表现较差。

要求在数据仍驻留内部存储时完成尽可能多的工作。分块算法会选择能放入 M 的工作集，在一个块上完成多个阶段后再换块。

例如要对两个大矩阵逐元素做归一化、阈值和统计，若分别扫描三遍，就搬运三次数据；若三个阶段都能在一个块驻留期间完成，外存往返可明显减少。

for (std::size_t base = 0;
     base != n;
     base += tile_size) {
    const std::size_t end =
        std::min(base + tile_size, n);
 
    load_tile(base, end);
    normalize_tile(base, end);
    threshold_tile(base, end);
    accumulate_statistics(base, end);
    store_tile(base, end);
}

tile_size 应让活跃输入、输出和临时数据共同落在 M 内。块太小会增加循环和请求开销，块太大又会破坏驻留假设；这正需要模型先给范围，再用实验确定实现参数。

少量缺页也可能造成巨大减速

原章进一步估算“只有少部分数据不在内部存储”是否可以忽略。令 a 为执行步骤中访问存储的比例，c 为一次外部访问相对内部访问的成本，p(epsilon) 为发生 I/O fault（缺页）的概率。平均步骤成本相对纯内部计算的减速为：

(1−a)+a[(1−p(ε))+c p(ε)]=1+a(c−1)p(ε)(1-a) +a\left[(1-p(\varepsilon)) +c\,p(\varepsilon)\right] = 1+a(c-1)p(\varepsilon)

当 c 很大时，即使 p(epsilon) 很小，乘积仍可能显著。重点不是把这个粗略公式当成精确基准，而是识别“少数慢路径可支配平均时间”：只看大部分访问命中，不能证明数据布局已经无关紧要。

工作集略大于 M 时，缺页概率还依赖访问分布。顺序扫描可让旧页稳定淘汰，随机反复触碰则可能让同一批页面持续竞争。两级模型能揭示传输数，真实基准再补上缓存策略、并发、预取与设备差异。

本章回顾

  1. 算法必须有限、明确、有效，具有可执行过程、规定输入和可验证输出。
  2. RAM 模型按基本操作计数，适合比较增长率，但把不同存储层级的访问近似为同一成本。
  3. 存储层次的容量、延迟、带宽和传输粒度，使访问顺序成为性能的一部分。
  4. 两级存储模型用内部容量 M、页大小 B 和可选磁盘数 D 抽象数据移动。
  5. I/O 复杂度计算页传输次数；顺序扫描 n 个元素只需约 n 除 B 次传输。
  6. A(s,b) 家族证明相同 n 次加法可因页面利用率而产生 n 除 B 到 n 除 b 的不同 I/O。
  7. 空间局部性提高每次传输的有效载荷，时间局部性提高数据驻留期间的有效工作。
  8. 少量高成本缺页仍可能主导平均时间，不能只看命中访问的多数比例。
  9. 算法工程以问题、模型、证明、实现、实验和修正构成闭环。

名词解释

讨论

评论区加载中…