第8.9章: RAM 模型及其局限

概述

到目前为止，我们所有的时间复杂度分析都建立在一个简单而理想化的机器模型之上，它叫 RAM 模型（随机访问机）。这也是算法教科书和 C++ 标准库所采用的标准模型。

RAM 模型极其有用，但它在很多方面也不符合现实。理解它的长处与局限，能帮助你诚实地推理性能。

你将学到：

• RAM 模型的各项假设
• 为什么我们用做渐近复杂度分析
• RAM 模型在哪里失效
• 真实硬件的行为有何不同
• 为什么存储层次结构主导性能
• 为什么链表在实践中很慢
• 为什么大整数打破了常数时间算术
• 数据移动在物理上的极限

1. RAM 模型

RAM 模型假设：

• 每个基本操作耗时常数时间
• 每次内存访问耗时常数时间
• 机器拥有无限内存
• 机器一次执行一条指令

在这些假设下，我们可以数操作次数，得出干净漂亮的渐近界，例如 Θ(n) 与 O(n ln n)。

这个模型简单、优雅，在数学上也很方便。

2. RAM 模型为什么有用

RAM 模型并不是为了贴近现实，而是为了有预测能力：

• 渐近复杂度更低的算法通常更快。
• 线性时间的算法通常胜过平方时间的算法。
• 对数时间的算法扩展性极好。
• 指数时间的算法面对大规模输入毫无希望。

尽管真实硬件更复杂，RAM 模型仍然抓住了算法性能中的主导趋势。

3. RAM 模型在哪里失效

真实的计算机并不像 RAM 模型那样工作。现实中：

• 内存访问时间不是常数
• 缓存未命中比缓存命中慢几百倍
• 虚拟内存会引入缺页
• 磁盘访问比内存慢几百万倍
• 对大规模数据集来说，数据移动主导运行时间

这些效应可能主导性能，尤其是面对大数据时。

4. 存储层次结构

现代 CPU 有多级存储：

• L1 缓存（极快、极小）
• L2 缓存
• L3 缓存
• RAM
• SSD / 磁盘

访问 L1 缓存可能只要约 1 个周期；访问 RAM 可能要约 200 个周期；访问磁盘可能要几百万个周期。

RAM 模型却假装这些都是同一回事。

这就是为什么局部性好的算法（例如顺序扫描 vector）往往比局部性差的算法（例如在链表中追逐指针）快得多，即使两者都是 Θ(n)。

5. 为什么 RAM 模型会误判链表的性能

在 RAM 模型中，跟随一次指针被认为耗 Θ(1) 时间。在这个假设下，遍历链表被当作一种每步常数时间的线性时间操作。

在真实硬件上，这个假设并不成立。

现代 CPU 严重依赖缓存和空间局部性。链表把结点散布在内存各处，因此每次解引用指针往往都会跳到不在缓存中的位置，迫使 CPU 从更慢的存储层次取回新的缓存行。

这种行为的精确数学复杂度很难建模，它取决于许多硬件细节。不过我们可以有把握地说：

访问链表结点在现实世界中的代价并不是 Θ(1)，它要高得多，而且随着链表变长而增长。

实测（例如 “The Myth of RAM” 一文中的测量）表明，这种减慢随 n 增大而加剧，整体遍历时间的增长快于 RAM 模型的预测。有些实验甚至观察到类似 O(√n) 的行为，但具体形式并不是重点。

重要的教训是：RAM 模型对指针追逐所作“常数时间”的假设并不反映真实硬件。链表在实践中慢得多，因为它们破坏了缓存。

6. 为什么大整数打破了常数时间假设

RAM 模型假设加法、减法、乘法这类基本运算耗常数时间。这只在数字能放进一个机器字（通常是 32 或 64 位）时成立。

当数字大于一个机器字时，就必须用多个字来存储。两个规模为 k 的大整数相加，需要把 k 个机器字相加并传播进位。

这意味着大整数加法耗时：

Θ(k)
      

而不是 Θ(1)。

大整数乘法更昂贵。最简单的算法是 Θ(k²)，更先进的算法（Karatsuba、基于 FFT 的乘法）是 Θ(k^1.58) 或 Θ(k log k)。

这打破了 RAM 模型“算术是常数时间”的假设。处理大数的算法（密码学、任意精度数学、符号计算）必须把大整数运算的代价计算在内。

在实践中，这意味着一个算法的真实运行时间可能不仅取决于操作次数，还取决于所操作数字的规模。

7. 数据与计算在物理上的极限

RAM 模型假设内存无限，并且访问任何位置都耗常数时间。现实中，随着数据增长，这两个假设都会失效。

数据越多，它占据的物理空间越大。即使信号以光速传播，把信息从一个地方搬到另一个地方也仍然存在硬性的下界。这意味着延迟随距离增长，而距离随我们存储的数据量增长。

当数据能装进 CPU 缓存时，访问极快；当它超出缓存时，就必须用 RAM，更慢；当它超出 RAM 时，就必须用磁盘，慢得多；当它超出单台机器时，就必须存放在：

• 局域网（LAN）
• 数据中心（集群存储）
• 广域网（WAN）
• 全球互联网

每一级都比上一级更慢。MapReduce 这类分布式系统之所以存在，正是因为跨机器搬数据太昂贵，以至于我们必须把计算搬到数据旁边，而不是反过来。

如果数据继续增长，我们就需要更多物理存储空间，甚至可能跨越大洲。极端情况下，存储任意大的数据将需要超出宇宙所能提供的物理空间。规模的每一次提升，都会增加延迟、能耗，以及搬运和处理数据所需的时间。

事实上，我们下载文件就是为了降低延迟：我们手动把互联网上的数据“缓存”到本地存储中，以便后续访问更快。这与硬件缓存的自动机制是同一条原则。

这些物理约束意味着：随着数据增长，访问和处理它的代价也在增长。这种增长不是常数时间的，而是数据规模及其物理分布的严格递增函数。

要点

• RAM 模型假设操作和内存访问都是常数时间。
• 它简单，适合做理论分析。
• 真实硬件有缓存、有存储层次，也有物理延迟极限。
• 在真实硬件上，链表遍历每步并不是 Θ(1)，它随数据规模增长。
• 大整数打破了常数时间算术，代价随数字规模增长。
• 数据移动有物理极限：距离、带宽、能耗以及光速。
• 当数据超出缓存、RAM、磁盘乃至单台机器时，每一层的延迟都在增加。
• 下载就是手动缓存：我们把数据搬到更近的地方以降低延迟。