跳转至

15:External Sorting

在实际场景中，能用于排序的内存 memory 比较有限，相较之下，磁带或者硬盘的大小会大很多，但是这二者都不能做到高效地随机访问（磁头只往一个方向扫效率更高），于是我们有如下定义：

相关定义

  1. 存储数据的容器称为磁带（tape），其中的元素只能顺序访问；
  2. 在 tape 中一段已经排序好的块称为顺串（run）；
  3. 将两个 tape 中的数据通过归并的方式有序合并，将结果存储到另一个 tape， 或者将原数据划分为 run 的过程，称为一趟（pass）。

那么整个外部排序过程大致可以按如下描述：

我们假设手上有若干个磁带，足够让我们进行 \(k\)-way 的合并，并且数据总量为 \(n\)，memory 大小为 \(m\)。

  1. 将存储在初始 tape 中的数据按 \(m\) 个 run 排序，该过程平凡；
  2. 每次将一个 tape 中的 run 分配到 \(k\) 个其它tape 中去；
  3. 将 \(k\) 个 tape 中的数据，按每 \(k\) 个 run 归并为一个 run，并分配到另外 \(k\) 个 tape 中去。若总共 run 的个数仍不为 \(1\)，则重回 2；
  4. 结束外部排序。

按上述过程中，可以看见对于磁带充足的情况下，我们知道需要的趟数 passes 为

\[ 1+\lceil\log_k{\dfrac{n}{m}}\rceil \]

接下来我们考虑优化整个过程，我们的目标有四个：

  1. Reduction of the number of passes
  2. Buffer handling for parallel operation
  3. Run generation
  4. Run merging

Reduction of the number of passes

当我们增大归并的路数，也就是增大 \(k\) 的时候能够减少趟数。

但是我们发现，要想实现 \(k\) 路的归并，至少需要 \(2k\) 个 tape。现实中我们不可能拥有非常多的 tape。

那我们可以使用较少的 tape 来实现 \(k\) 路的归并吗？显然是可以的。比方说我可以将归并的结果先存在初始的 tape 中，在归并结束之后再通过同样的方式分配到其余 \(k\) 个 tape 中去。但是这样仍然会有问题，我们会发现每次的会比原策略多一次复制的过程，使得整个过程仍然比较慢。

如何规避掉不断从某个 tape 中读取再存入的过程呢？

采取斐波那契数列的思想。如下：

若 \(n=F_n\)，则初始的时候将其分为 \(F_{n-1}\) 和 \(F_{n-2}\)，归并时将 \(F_{n-2}\) 对 run 合并后存入初始的 tape1，事实上就自动地变成了要合并 \(F_{n-2}\) 和 \(F_{n-1}-F_{n-2}=F_{n-3}\) 个 run 的过程。这样一直做下去，只需要 \(n\) 次 pass，就能实现外部排序。

事实上与 \(k=2\) 等价，但是考得不多。

若 \(n\) 可以分为：

  • \(F_{n-1}^{(k)}+F_{n-2}^{(k)}+\cdots+F_{n-k}^{(k)}\)
  • \(F_{n-2}^{(k)}+\cdots+F_{n-k}^{(k)}\)
  • \(\cdots\)
  • \(F_{n-k}^{(k)}\)

那么也可以进行同样的过程，每次 pass 之后会发现最终 tape 中自动地满足了上述形式。不难发现，\(k=2\) 实际上是它的平凡形式。

如此，我们便能用 \(k+1\) 个 tape 来实现 \(k\) 路的外部排序。若 \(n\) 不满足上述形式，则考虑往后面加空数据凑成满足上述形式的值。该方法称为 Polyphase merge。

Buffer handling for parallel operation

我们发现当在 memory 中归并的时候，读写头是空闲的。于是我们希望能够实现读、归并、写的并行。这就需要我们好好利用 memory 中的空间。

我们将 memory 中的空间分成 input buffers 和 output buffer。

结论

对于 \(k\) 路归并，要想实现并行，需要 \(2k\) 个 input buffer 和 \(2\) 个 output buffer。

Run generation

如何更好地生成 run 呢？根据前文提到的 tape 顺序读写的特性，我们不难考虑贪心算法如下：

run generation

  1. 初始化一个大小为 \(m\) 的堆/优先队列；
  2. 每次从堆顶读出一个数；
  3. 若该数比当前 run 的最后一个数要大，则读出存入当前 run，并从原 tape 中读取一个数存入堆；
  4. 若该数比当前 run 的最后一个数小，则锁定该数不可成为堆顶；
  5. 当堆中所有数都锁定后，结束当前 run，开始下一个 run，并解锁所有数。

Run merging

由此我们可能会得到大小不同的 run，如何将它们合并呢？我们知道归并两个串的花销为 \(O(n+m)\)，因此我们希望短的串尽可能早开始合并，也就是哈夫曼树/哈夫曼编码的思想。