Lec7 Sorting(5)

接下来登场的是External Sorting。😎该结束排序这一章了！！！

外部排序算法（External Sorting Algorithms）

• 外部排序的定义
  外部排序算法是设计用来处理非常大的输入数据的算法。
  由于输入数据太大，无法完全加载到内存中，因此需要特殊的排序方法来处理。

• 外部排序的工作过程
  外部排序的过程通常包括以下几个步骤：

  1. 从磁盘中读取一些记录（数据）。
  2. 对读取的记录进行一些排序或重新排列。
  3. 将排序后的记录写回到磁盘。
  4. 重复上述过程，直到文件完全排序。

• 磁带存储与顺序访问 假设记录存储在磁带上，磁带只能进行顺序访问，不能像硬盘那样进行随机访问。 在这种情况下，外部排序算法必须设计成顺序读取和写入数据。

• 假设至少使用三张磁带 假设外部排序算法将使用至少三张磁带进行操作。通过使用多张磁带，可以实现更高效的数据交换和合并操作，减少磁带的反复读取和写入次数。

• 主要目标
  外部排序算法的主要目标是最小化从存储设备读取或写入数据的次数。
  因为磁盘的读写速度相较于内存要慢得多，因此减少磁盘操作是提高外部排序效率的关键。

核心点

• 外部排序用于处理内存无法容纳的大型数据集。
• 外部排序的过程通过多次读写磁盘来实现数据的排序。
• 其核心目标是优化磁盘I/O操作，减少数据读写的次数。

简单算法：外部归并排序（External Mergesort）

外部归并排序是一种处理大规模数据的外部排序算法。假设我们有四个磁带：Ta1、Ta2、Tb1、Tb2，数据最初存储在Ta1上，而内部内存能够容纳和排序M个记录。这里假设M=3，即内部内存每次能处理3个记录。

外部归并排序的工作原理

1. 初始运行（Initial Runs）
   • 数据被分为初始运行，初始运行的大小由内部内存的容量决定。在每次读取时，内部内存处理M个记录并将它们排序，生成一个有序的运行（run），然后写回磁带。
   • 假设每个运行包含M个记录，所有的初始运行总数为：$ $，其中N是总记录数。
2. 归并过程（Merging Process）
   • 外部归并排序的过程类似于内部归并排序，不同之处在于数据存储在外部存储设备（磁带）上。算法需要多次将小的、有序的运行合并成更大的运行。
   • 每次归并时，我们将多个运行合并为一个新的、更大的运行，直到所有数据被归并到一个最终的有序运行中。

image-20241120135902226

image-20241120135927713

image-20241120140114514

算法的步骤

1. 初始运行构建
   • 假设我们有N个记录，内部内存能够容纳M个记录。初始运行的数量为：$ $。
   • 比如，假设有1000万个记录（$ 10 ^{20} \(），每个记录128字节（\) 2^7 \(字节），而内部内存大小为4MB（\) 4 ^{20} \(字节），那么可以一次性处理3个记录，因此，初始运行数为：\) = 3,333,334 $个运行。
2. 归并过程的次数
   • 每次归并操作可以合并M个运行到一个新的运行中，经过$ _M ( ) $次归并操作后，最终得到一个有序运行。
   • 假设初始运行数为320，则需要的归并次数为：$ _2(320) = 9 $次。

提升优化

1. 构建尽可能大的初始运行
   • 通过合理使用内部内存，可以尽可能将每个初始运行的大小增大，减少初始运行的数量。这样可以减少需要归并的次数，从而提高排序效率。
2. 增加每次归并时合并的运行数
   • 在每次归并时，不仅仅合并2个运行，可以尝试增加每次归并时合并的运行数（例如多路归并）。这样每次归并能够处理更多的数据，从而减少归并的次数。

多路归并（Multiway Merge）

• 多路归并：在外部排序中，可以使用多路归并代替传统的二路归并，即每次归并多个运行。例如，使用k路归并将k个运行合并到一起。这样可以更高效地利用磁带和内部内存，加速归并过程。

image-20241120140130811

image-20241120140145825

总结

• 外部归并排序的步骤：首先构建初始运行，然后通过多次归并逐步将数据合并成一个最终的有序运行。
• 优化方法：可以通过构建尽可能大的初始运行和增加每次归并时合并的运行数（多路归并）来提高效率。

替代选择算法（Replacement Selection）

如何创建尽可能大的初始运行？

在外部归并排序中，我们希望构建尽可能大的初始运行，以减少归并次数，优化排序效率。假设可用内存可以容纳M个记录，在简单的外部归并排序中，通常的做法是：

1. 加载M个记录到内存：将输入文件的M个记录加载到内存中并进行排序。
2. 划分初始运行：根据内存大小，划分出长度为M的初始运行。

但更好的方法是使用替代选择算法（Replacement Selection）来创建平均长度为2M的初始运行。这样，初始运行的大小大约是内存容量的两倍，从而减少了初始运行的数量。

替代选择算法（Replacement Selection）概述

替代选择算法是一种堆排序（Heapsort）的变种。其主要思想是利用堆来动态地生成更长的有序运行，具体步骤如下：

1. 初始化：
   • 将M个记录加载到内存中，设置 LAST = M - 1（记录的最后位置）。
2. 构建最小堆：
   • 将这M个记录放入一个最小堆中（堆的根节点为最小的记录）。
3. 重复以下步骤直到堆为空：
   • 删除最小值：从堆中删除最小的记录，并将该记录写入输出磁带（即输出到外部存储）。
   • 读取新记录：读取输入磁带中的下一个记录 R：
     • 如果 R 的值大于刚输出的记录（堆根节点），则将 R 放入堆根。
     • 否则，将堆根替换为当前数组位置 LAST 中的记录，并将 R 放到 LAST 位置，然后将 LAST 设置为 LAST - 1。
   • 重新调整堆：调整堆结构，确保其仍然是最小堆。
4. 期望结果：
   • 假设输入是随机分布的，通过替代选择算法生成的初始运行的长度预期是2M（即两倍于内存大小）。这样，每个初始运行将比直接使用简单排序方法生成的运行更长，优化了后续的归并过程。

示例

image-20241120140211464

image-20241120140219328

image-20241120140226092

image-20241120140233241

总结

• 替代选择算法通过使用堆来动态生成初始运行，能够使得每个初始运行的长度约为2M，从而减少了初始运行的数量。
• 优势：相比简单的外部排序方法，替代选择算法通过生成更长的初始运行，提高了外部排序的效率，减少了后续归并的次数。