数据结构之外部排序
数据结构之外部排序
外部排序的基本概念
- 外部排序定义:
- 当待排序文件的大小超出内存的容量时，必须使用外部存储（如磁盘）进行排序。这种排序方式称为外部排序。
- 内部排序 vs 外部排序:
- 内部排序: 所有数据都可以放入内存中进行排序。
- 外部排序: 数据量过大，需要分块处理，一部分数据在内存中，另一部分在外存中。
外部排序的方法
外部排序通常使用归并排序法，其主要步骤包括：
- 划分阶段:
- 将外存文件分割成多个长度适合内存的子文件（归并段）。
- 对每个子文件进行内部排序，然后将其写回外存。
- 归并阶段:
- 对这些已排序的归并段进行归并，逐步合并成一个完整的有序文件。
降低读写次数的策略
由于外部排序的性能主要受到磁盘读写次数的影响，以下方法被用来减少读写次数：
- 增大归并路数:
- 增加每次归并的输入段数（归并路数），从而减少归并的趟数。例如，从2路归并改为4路归并。
- 利用败者树:
- 通过构建败者树结构来优化归并过程，使得每次归并的输入段数更多，从而减少趟数。
- 置换-选择排序:
- 通过优化归并段的长度，以减少初始归并段的数量，从而降低归并趟数。
- 构造最佳归并树:
- 对于长度不等的归并段，通过合理的树形结构安排合并次序，以减少归并趟数。
外部排序的过程示例
例如，考虑一个包含2000个记录的文件，每个磁盘块可以容纳125个记录：
- 初始划分:
- 将文件分成8个归并段（每个250个记录），进行内部排序后写回外存，得到 $ R_1, R_2, ..., R_8 $。
- 归并过程:
- 采用2路归并，首先将 $ R_1 $ 和 $ R_2 $ 合并，再将 $ R_3 $ 和 $ R_4 $ 合并，依此类推，直到所有段都归并完成。
- 归并示意图:
- 第一趟归并: $ R_1 $ 和 $ R_2 $ -> $ R_1' $
- 第二趟归并: $ R_3 $ 和 $ R_4 $ -> $ R_3' $
- 继续进行，直到得到最终有序文件。
外部排序的效率分析
外部排序的总时间可以表示为： $ = + + $
- 由于外存读写时间通常远大于内部操作时间，因此减少磁盘读写次数是优化外部排序性能的关键。
归并树的结构
在外部排序中，通过构建归并树来优化归并过程。每次归并可以看作是一个树的节点，树的高度决定了归并的趟数。
- 若有 $ r $ 个初始归并段，进行 $ k $ 路归并，树的高度（归并趟数）为： $ = _k r $
多路平衡归并与败者树
概述
在外部排序中，增加归并路数 $ k $ 可以减少归并趟数 $ S $，从而降低外存的读写次数。然而，随着 $ k $ 的增加，内部归并所需的时间也会增加。这是因为在进行内部归并时，需要对 $ k $ 个元素进行比较，导致比较次数随 $ k $ 增长而增加。为了解决这一问题，引入了败者树。
败者树的概念
败者树是一种树形选择排序的变体，可以视为一棵完全二叉树。其主要作用是在进行多路归并时，高效地选择最小的关键字记录。败者树的结构包括：
- 叶结点：存放当前参与比较的 $ k $ 个归并段的记录。
- 内部结点：存储左右子树中的“失败者”，即不胜出的记录，从而让胜者继续进行比较。
在归并过程中，根结点指向最小的关键字。例如，图 8.15(a) 中展示了如何通过比较记录来更新败者树。
比较次数分析
在 $ k $ 个记录中选择最小关键字，最多需要 $ _2 k $ 次比较。因此，归并过程中总的比较次数为： $ S(n-1) _2 k $
总结就是：每次比较，节点是失败者， 推上去的和输出的是胜利者，输出后需要对那条包含输出者的路线进行修改，从而改变败者树。
- 总比较次数：使用败者树后，总比较次数为 $ S(n-1) _2 k $，其中 $ S $ 是归并趟数，$ n $ 是每趟归并的记录数量。
归并路数的选择
使用败者树后，内部归并的比较次数与 $ k $ 无关，意味着只要内存空间允许，可以有效地增大归并路数 $ k $，从而减少归并树的高度和 IO 次数，提高外部排序的速度。
增加归并路数的优势
- 降低归并趟数：随着 $ k $ 的增大，归并趟数 $ S $ 减少，从而降低磁盘的读写次数。
- 提高排序效率：通过有效利用内存，可以在归并过程中减少 IO 操作，提高整体排序速度。
限制因素
- 内存使用：增加 $ k $ 时，需要相应增加输入缓冲区的数量。如果内存空间有限，可能需要减少每个输入缓冲区的容量，导致内存与外存交换数据的次数增多。
- 平衡考虑：虽然增大 $ k $ 有助于减少归并趟数，但 $ k $ 过大时，虽然归并趟数减少，外存读写次数可能反而增加。因此，选择合适的 $ k $ 是至关重要的。
置换-选择排序（生成初始归并段）
置换-选择排序是一种有效生成初始归并段的算法，旨在减少归并趟数 $ S $，从而提高外部排序的效率。
算法概述
置换-选择排序利用内存工作区（WA）和待排文件（FI）来逐步生成初始归并段，最后将这些归并段输出到输出文件（FO）。该算法依赖于一个固定的内存工作区大小 $ w $。
算法步骤
算法步骤如下：
- 初始化：
- 从待排文件 FI 输入 $ w $ 个记录到工作区 WA。
- 输出文件 FO 和工作区 WA 的初始状态为空。
- 选择最小值：
- 从 WA 中选择关键字最小的记录，称为 MINIMAX 记录。
- 输出记录：
- 将 MINIMAX 记录输出到输出文件 FO 中。
- 输入新记录：
- 如果 FI 不为空，则从 FI 输入下一个记录到 WA 中。
- 更新 MINIMAX：
- 从 WA 中所有关键字大于 MINIMAX 记录关键字的记录中，选择最小关键字记录作为新的 MINIMAX 记录。
- 重复过程：
- 重复步骤 3 到 5，直到在 WA 中选不出新的 MINIMAX 记录为止。这时，输出一个归并段的结束标志到 FO 中。
- 继续处理：
- 重复步骤 2 到 6，直到 WA 为空。此时，所有初始归并段已生成并输出到 FO。
算法示例
假设待排文件 FI 为
{17, 21, 5, 44, 10, 12, 56, 32, 29}，工作区 WA 容量为
3。排序过程如表 8.2 所示：
使用败者树
在 WA 中选择 MINIMAX 记录的过程可以通过使用败者树来实现。这种结构能够有效地进行多路比较，以快速找到最小的关键字记录，具体步骤如下：
- 构建败者树：
- 将 WA 中的记录插入到败者树中。
- 每次插入时，根据记录的关键字调整败者树的结构，确保树的根节点总是指向当前最小的记录。
- 选择并输出：
- 从败者树的根节点输出最小的记录到 FO，并更新该记录。
- 若在 WA 中有新记录输入，则调整败者树，保持其正确性。
- 迭代处理：
- 持续选择、输出最小记录，更新败者树，直到没有更多的记录可选。
置换-选择排序就是每次从中拿出比当前有序段最后一个数大的最小的一个数字进行替换。
最佳归并树
目标：
通过优化初始归并段的归并顺序，尽量减少 I/O 次数。
情景分析：
长度不等的初始归并段：
假设通过置换-选择算法得到的初始归并段长度依次为 $ {9, 30, 12, 18, 3, 17, 2, 6, 24} $。归并树构建：
可以使用 3 路平衡归并的方法构建归并树。树的叶节点表示初始归并段，路径长度表示参与归并的趟数。WPL（带权路径长度）计算：
计算归并过程中的总读记录数（I/O 次数为 $ 2 = 484 $）。优化策略：
应用类似哈夫曼树的思想，优先合并记录数少的初始归并段，直到合并成根节点，最后构建最佳归并树。
构建最佳归并树的步骤：
树的严格性：
在构建归并树时，确保树的度数为 $ k $，并使用零权值的“虚段”来填充不够的叶节点。添加虚段的判定：
- 设度为 0 的节点有 $ n_0 = n $ 个，度为 $ k $ 的节点有 $ m $ 个。对于严格 $ k $ 叉树，有 $ n_0 = (k - 1)n + 1 $。
- 从中可以得出 $ n = $。
- 若 $ (n - 1) % (k - 1) = 0 $，说明叶节点可构成严格的 $ k $ 叉树；否则，需要添加一个内节点替代一个叶节点，再补充 $ k - u - 1 $ 个虚段。
实例分析：
在 $ 8 $ 个初始归并段构成 $ 3 $ 叉树的例子中，若缺少一个段，最后添加的空段应放置在距离树根最远的位置。
