外部存储模型

当我们要理解和预测一个内存受限的算法性能时，我们需要创建一个新的成本模型。这个模型需要对昂贵的块I/O（Input/Output，输入输出）操作更敏感，但又不能过于严格以至于失去其实用性。

缓存感知模型（Cache-Aware Model）

标准的 RAM 模型忽略了一点：完成不同基本操作所需的时间是不相同的。更为关键的是，这个模型并未区别对待对不同类型内存的操作。例如，直接从 RAM 中读取数据，现实中大约需要 50 纳秒的时间；而从硬盘读取数据则大约需要 5 毫秒的时间，这比从 RAM 读取数据的时间要长大约 100,000 倍。

在外部存储模型中，我们只关注与输入输出（I/O）操作相关的部分，而忽视了所有其他非输入输出操作的部分。另外，我们假设系统只有一级缓存层次，并且有如下关于硬件和其他问题的假设：

数据集的总大小为 $N$ ，所有的数据都保存在外部的存储设备中，可以在单位时间内进行读取或者写入 $B$ 个元素的数据块（读取整个块和只读取一个元素所需的时间相同）。
我们可以在内存中存储 $M$ 个元素，意味着我们可以存储至多 $⌊\frac{M}{B}⌋$ 个块。
我们只关注I/O操作：在读取和写入之间进行的任何计算都是“免费”的。
我们另外假设 $N \gg M \gg B$ 。

在这个模型中，我们衡量一个算法的性能是根据其高级I/O操作，或者叫IOPS——即在执行期间对外部存储（如硬盘）读写数据块的次数。

这里我们将主要关注内部内存是RAM，外部内存是SSD或HDD的情况，尽管我们将要讲解的底层分析技术适用于缓存层次结构中的任何层次。在这些前提设定下，合理的数据块大小 $B$ 大约是1MB，内部内存大小 $M$ 通常是几个GB，N最多是几个TB。

数组遍历

作为一个简单的例子，当我们依次遍历数组中的每个元素来求和时，实际上是通过隐式地加载若干个包含 $O(B)$ 个元素的块来实现的，在外存模型的角度来看，我们就是在逐个处理这些块。

$\underbrace{a_1,a_2,a_3,}_{B_1}\underbrace{a_4,a_5,a_6,}_{B_2}\dots\underbrace{a_{n-3},a_{n-2},a_{n-1}}_{B_{m-1}}$

因此，在外部存储器模型中，求和以及其他线性数组遍历的复杂性为

$SCAN(N)\stackrel{def}{=}O(⌈\frac{N}{B}⌉)\space IOPS$

你可以像这样显式地实现外部矩阵遍历：

FILE *input = fopen("input.bin", "rb");

const int M = 1024;
int buffer[M], sum = 0;

// while the file is not fully processed
while (true) {
    // read up to M of 4-byte elements from the input stream
    int n = fread(buffer, 4, M, input);
    //  ^ the number of elements that were actually read

    // if we can't read any more elements, finish
    if (n == 0)
        break;
    
    // sum elements in-memory
    for (int i = 0; i < n; i++)
        sum += buffer[i];
}

fclose(input);
printf("%d\n", sum);