外部排序
外部排序
当待排序的数据量非常大,以至于无法一次性全部加载到内存中时,就需要使用 外部排序。
外部排序 通常分为两个主要阶段:
- 初始归并段生成:使用 置换选择排序,根据原始无序文件生成若干个尽量长的的有序文件,这些有序文件叫做 初始归并段。
- 多路归并:将这些 初始归并段 逐步合并,最终得到完全有序的文件。
置换选择排序
置换选择排序(Replacement Selection Sort)是 外部排序 的一个步骤,用于生成 初始归并段,其核心思想是在 内存缓冲区 有限的情况下,尽可能地生成较长的 初始归并段。
置换选择排序 通过维护一个 工作区 来实现这一目标,工作区是一个 小根堆。
其算法步骤如下:
- 初始化:
- 将待排序文件中的前 M 个记录读入 工作区,建立一个 最小堆(M 为 工作区 的大小)。
- 生成归并段:
- 判断是否有 初始归并段
- 如果不存在任何 初始归并段 的话,创建一个 初始归并段,并添加 工作区 中的最小元素加入其中。
- 否则将 工作区 中的元素与上一个 初始归并段 的最大值 MAXV 进行比较。
- 如果 工作区 中的所有元素都 ≤ MAXV 的话,创建一个新的 初始归并段,并添加 工作区 中的最小元素加入其中。
- 否则找到第一个 > MAXV 的元素,将其添加到上一个 初始归并段 的末尾。
- 从输入文件中读取下一个值加入 工作区。
- 判断是否有 初始归并段
举一个实际的例子,假设一个输入文件 FI 的内容为 51, 94, 37, 92, 14, 63, 15, 99, 48, 56, 23, 60, 31, 17, 43, 8, 90, 166, 100。
我们可以通过 置换选择排序 生成 3 个 初始归并段,分别为 {37, 51, 63, 92, 94, 99} ,{14, 15, 23, 31, 48, 56, 60, 90, 166} ,{8, 17, 43, 100} 。
算法执行的过程如下表所示:
输出文件 FO | 工作区 WA | 输入文件 FI |
---|---|---|
—— | —— | 51, 94, 37, 92, 14, 63, 15, 99, 48, 56, 23, 60, 31, 17, 43, 8, 90, 166, 100 |
—— | 51, 94, 37, 92 | 14, 63, 15, 99, 48, 56, 23, 60, 31, 17, 43, 8, 90, 166, 100 |
37 | 51, 94, 14, 92 | 63, 15, 99, 48, 56, 23, 60, 31, 17, 43, 8, 90, 166, 100 |
37, 51 | 63, 94, 14, 92 | 15, 99, 48, 56, 23, 60, 31, 17, 43, 8, 90, 166, 100 |
37, 51, 63 | 15, 94, 14, 92 | 99, 48, 56, 23, 60, 31, 17, 43, 8, 90, 166, 100 |
37, 51, 63, 92 | 15, 94, 14, 99 | 48, 56, 23, 60, 31, 17, 43, 8, 90, 166, 100 |
37, 51, 63, 92, 94 | 15, 48, 14, 99 | 56, 23, 60, 31, 17, 43, 8, 90, 166, 100 |
37, 51, 63, 92, 94, 99 | 15, 48, 14, 56 | 23, 60, 31, 17, 43, 8, 90, 166, 100 |
37, 51, 63, 92, 94, 99# | 15, 48, 14, 56 | 23, 60, 31, 17, 43, 8, 90, 166, 100 |
14 | 15, 48, 23, 56 | 60, 31, 17, 43, 8, 90, 166, 100 |
14, 15 | 60, 48, 23, 56 | 31, 17, 43, 8, 90, 166, 100 |
14, 15, 23 | 60, 48, 31, 56 | 17, 43, 8, 90, 166, 100 |
14, 15, 23, 31 | 60, 48, 17, 56 | 43, 8, 90, 166, 100 |
14, 15, 23, 31, 48 | 60, 43, 17, 56 | 8, 90, 166, 100 |
14, 15, 23, 31, 48, 56 | 60, 43, 17, 8 | 90, 166, 100 |
14, 15, 23, 31, 48, 56, 60 | 90, 43, 17, 8 | 166, 100 |
14, 15, 23, 31, 48, 56, 60, 90 | 166, 43, 17, 8 | 100 |
14, 15, 23, 31, 48, 56, 60, 90, 166 | 100, 43, 17, 8 | —— |
14, 15, 23, 31, 48, 56, 60, 90, 166# | 100, 43, 17, 8 | —— |
8 | 100, 43, 17 | —— |
8, 17 | 100, 43 | —— |
8, 17, 43 | 100 | —— |
8, 17, 43, 100 | —— | —— |
8, 17, 43, 100# | —— | —— |
多路归并
多路归并 的目标是将多个已经排序的 初始归并段(子文件)合并成一个更大的有序文件。
其核心思想是从若干 归并段 中每次选取一个最小的元素加入 工作区(小根堆),然后从 工作区 中选取最小的元素添加到 输出文件 中,通过这种方式可以保证每次添加到 输出文件 中的值是当前的最小值。
多路归并 的具体过程如下:
- 初始化:
- 打开所有参与归并的 初始归并段,并读取每个归并段的第一个元素。
- 将这些元素放入一个数据结构中,以便快速找到最小值(例如,最小堆)。
- 归并:
- 从数据结构中取出最小的元素,将其输出到结果文件中。
- 找到该元素所属的归并段,并从该归并段中读取下一个元素。
- 将新读取的元素放入数据结构中,并调整数据结构,以保持有序。
- 重复上述步骤,直到所有归并段都被处理完毕。
- 结束:
- 当所有归并段都为空时,归并过程结束,结果文件即为完全有序的文件。
继续用上文中通过 置换选择算法 生成的三个 初始归并段 {37, 51, 63, 92, 94, 99} ,{14, 15, 23, 31, 48, 56, 60, 90, 166} ,{8, 17, 43, 100} 作为例子。对于这三个 初始归并段,多路归并 的过程如下(假设采用三路归并的话):
归并段 1 | 归并段 2 | 归并段 3 | 工作区 | 输出文件 |
---|---|---|---|---|
37, 51, 63, 92, 94, 99 | 14, 15, 23, 31, 48, 56, 60, 90, 166 | 8, 17, 43, 100 | – | – |
51, 63, 92, 94, 99 | 15, 23, 31, 48, 56, 60, 90, 166 | 17, 43, 100 | 8, 14, 37 | – |
51, 63, 92, 94, 99 | 15, 23, 31, 48, 56, 60, 90, 166 | 43, 100 | 14, 17, 37 | 8 |
51, 63, 92, 94, 99 | 23, 31, 48, 56, 60, 90, 166 | 43, 100 | 15, 17, 37 | 8, 14 |
51, 63, 92, 94, 99 | 31, 48, 56, 60, 90, 166 | 43, 100 | 17, 23, 37 | 8, 14, 15 |
51, 63, 92, 94, 99 | 31, 48, 56, 60, 90, 166 | 100 | 23, 37, 43 | 8, 14, 15, 17 |
51, 63, 92, 94, 99 | 48, 56, 60, 90, 166 | 100 | 31, 37, 43 | 8, 14, 15, 17, 23 |
51, 63, 92, 94, 99 | 56, 60, 90, 166 | 100 | 37, 43, 48 | 8, 14, 15, 17, 23, 31 |
63, 92, 94, 99 | 56, 60, 90, 166 | 100 | 43, 48, 51 | 8, 14, 15, 17, 23, 31, 37 |
63, 92, 94, 99 | 56, 60, 90, 166 | – | 48, 51, 100 | 8, 14, 15, 17, 23, 31, 37, 43 |
63, 92, 94, 99 | 60, 90, 166 | – | 51, 56, 100 | 8, 14, 15, 17, 23, 31, 37, 43, 48 |
92, 94, 99 | 60, 90, 166 | – | 56, 63, 100 | 8, 14, 15, 17, 23, 31, 37, 43, 48, 51 |
92, 94, 99 | 90, 166 | – | 60, 63, 100 | 8, 14, 15, 17, 23, 31, 37, 43, 48, 51, 56 |
92, 94, 99 | 166 | – | 63, 90, 100 | 8, 14, 15, 17, 23, 31, 37, 43, 48, 51, 56, 60 |
94, 99 | 166 | – | 90, 92, 100 | 8, 14, 15, 17, 23, 31, 37, 43, 48, 51, 56, 60, 63 |
94, 99 | – | – | 92, 100, 166 | 8, 14, 15, 17, 23, 31, 37, 43, 48, 51, 56, 60, 63, 90 |
99 | – | – | 94, 100, 166 | 8, 14, 15, 17, 23, 31, 37, 43, 48, 51, 56, 60, 63, 90, 92 |
– | – | – | 99, 100, 166 | 8, 14, 15, 17, 23, 31, 37, 43, 48, 51, 56, 60, 63, 90, 92, 94 |
– | – | – | – | 8, 14, 15, 17, 23, 31, 37, 43, 48, 51, 56, 60, 63, 90, 92, 94, 99, 100, 166 |
胜者树
在进行 $k$ 路归并(如外排序)时,我们需要从多个有序子序列中 快速找出当前最小元素,然后将其输出并替换为该序列的下一个元素。
最简单的做法就是每次遍历序列头部元素,找到最小值。该方法的时间复杂度为 $O(k)$,效率比较低,尤其是当 $k$ 比较大 时。
树形结构优化(胜者树/败者树)优化的目的就是优化这个过程:
用一棵完全二叉树维护每一轮比较的结果,使得我们可以在 $O(\log k)$ 时间内完成最小值查找与更新。
胜者树 可以理解为 胜者晋级的淘汰赛模型:类比体育比赛的淘汰制,每一轮两个选手进行比较,胜者晋级上一轮,最终全局胜者抵达根节点。
在 胜者树 中,每个 内部结点 记录的是该轮比较的 胜者(较小的元素),而 叶子节点 表示每个输入归并段的当前值。因此,整棵树的 根节点 就表示 全局最小值。
当某个归并段输出了最小值并更新为下一个元素时,需要 从该叶子节点向上,逐层与兄弟节点重新比较,构建新的胜者路径,最终将新的最小值更新到根节点。
败者树
败者树 可以理解为 败者记录的升降赛模型:类比体育比赛中每场比赛将败者淘汰出局但保留记录,胜者则继续晋级下一轮,最终全局胜者脱颖而出,但 不会被记录在树中,而是单独保留,以便快速访问。
在 败者树 中,每个 内部结点 记录的是该轮比较的 败者(较大的元素),而 叶子节点 同样表示每个输入归并段的当前值。最终的全局胜者(最小值) 不保存在树中,而是单独保存在一个外部变量中。
当某个归并段输出了最小值并更新为下一个元素时,需要 从该叶子节点出发,沿着路径向上与路径上的败者重新比较,并在每一层更新败者信息。
胜者树更加直观,败者树的优势在哪?
在用 胜者树 的时候,每个新元素上升时,首先先和兄弟结点比较,然后再更新父结点(访存 2 次)。
在使用 败者树 的时候,每个新元素上升时,只需要获得父节点并比较即可(访存 1 次)。
所以总的来说,减少了访存的时间,进而 提高了程序运行的效率。