外部存储器算法

在计算中，外部存储器算法或核心外算法是指旨在处理那些大到无法一次性装入计算机主存储器的数据的算法。这种算法必须进行优化，以有效地获取和访问存储在慢速散装存储器（辅助存储器）中的数据，如硬盘或磁带机，或者当存储器在计算机网络上时。外部存储器算法是在外部存储器模型中分析的。

外部存储器算法是在一个理想化的计算模型中分析的，这个模型称为外部存储器模型（或I/O模型，或磁盘访问模型）。外部存储器模型是一个类似于RAM机器模型的抽象机器，但是除了主存储器之外还有一个高速缓存。该模型抓住了这样一个事实：在高速缓存中的读写操作比在主内存中快得多，而且读取长的连续块比使用磁盘读写头随机读取快。外部存储器模型中算法的运行时间是由所需的对存储器的读写次数决定的。该模型是由AlokAggarwal和JeffreyVitter在1988年提出的。外部存储器模型与缓存无关模型有关，但外部存储器模型中的算法可能同时知道块大小和缓存大小。由于这个原因，该模型有时被称为高速缓存感知模型。该模型包括一个具有内部存储器或大小为M的高速缓存的处理器，与一个无界的外部存储器相连。一个输入/输出或内存转移操作包括将一个由B个连续元素组成的块从外部内存转移到内部内存，一个算法的运行时间由这些输入/输出操作的数量决定。

外部存储器模型中的算法利用了这样一个事实：从外部存储器中检索一个对象会检索出整个大小为B{displaystyleB}。.这个属性有时被称为定位性。时间（用大O符号表示）。从信息理论上讲，这是这些操作可能的最小运行时间，所以使用B树是渐进式的最优。外部排序是在外部内存环境下的排序。外部排序可以通过分布式排序来完成，它类似于quicksort，或者通过一个MB{displaystyle{tfrac{M}{B}}}的方式进行。-方式的合并排序。这两种变体的渐进最优运行时间为来分类N个对象。这个约束也适用于外部存储器模型中的快速傅里叶变换。替换问题是重新排列N{DisplaystyleN}的元素重新排列成一个特定的排列。元素重新排列成一个特定的互换。这既可以通过排序来完成，这需要上述排序的运行时间，也可以按顺序插入每个元素，而忽略了位置性的好处。因此，排列组合可以在以下时间内完成

外部存储器模型捕捉到了存储器的层次结构，这在分析数据结构的其他常用模型中是没有的，比如随机存取机，对于证明数据结构的下限很有用。该模型对于分析那些工作在内部存储器中无法容纳的大数据集的算法也很有用。一个典型的例子是地理信息系统，特别是数字高程模型，其中完整的数据集很容易超过几千兆字节甚至是几百万兆字节的数据。这种方法超出了通用CPU的范围，还包括GPU计算以及经典的数字信号处理。在图形处理单元（GPGPU）的通用计算中，强大的图形卡（GPU）的内存很少（与更熟悉的系统内存相比，它最常被简单地称为RAM），利用CPU到GPU的内存传输相对缓慢（与计算带宽相比）。