当前位置: 首页 > news >正文

多路归并、败者树、置换-选择排序、最佳归并树

目录
  • 一、多路归并
  • 二、败者树
  • 三、置换-选择排序
  • 四、最佳归并树


一、多路归并

1. 基本概念
多路归并是外部排序第二阶段的核心操作。它将多个已经排序好的序列(称为“归并段”或“顺串”)合并成一个更大的有序序列。这里的“路”(K)指的是同时进行合并的归并段数量。

2. 为什么需要多路归并?

  • 减少归并轮数:这是最根本的原因。归并轮数 \(S = \lceil \log_K N \rceil\),其中 \(N\) 是初始归并段的数量。增大 K 可以显著减少 S。
    • 例子:有 100 个初始归并段。
      • 二路归并(K=2):需要 \(\lceil \log_2 100 \rceil = 7\) 轮归并。
      • 十路归并(K=10):需要 \(\lceil \log_{10} 100 \rceil = 2\) 轮归并。
    • 归并轮数减少,意味着磁盘 I/O 次数大大降低,从而提升了整体排序效率。

3. 工作原理

  1. 初始化:为 K 个归并段分别开设一个输入缓冲区,并从每个归并段中读入一部分数据到对应的缓冲区。
  2. 选择最小元:从 K 个缓冲区的当前元素中,选出最小的那个元素。
  3. 输出:将选出的最小元素输出到最终结果文件(或下一个临时文件)中。
  4. 补充数据:从刚刚输出元素所在的归并段中,读取下一个元素到其缓冲区。如果该归并段已读完,则忽略该路。
  5. 重复:重复步骤 2-4,直到所有 K 个归并段的所有数据都被处理完毕。

4. 核心挑战与解决方案

  • 挑战:在步骤 2 中,如何高效地从 K 个元素中找出最小值?如果使用简单的顺序比较,每次需要 K-1 次比较,当 K 很大时,CPU 开销会变得很大。
  • 解决方案:使用 败者树。它可以将每次选择最小元的比较次数降低到 O(log K)

二、败者树

1. 基本概念
败者树是完全二叉树,它是多路归并中用于高效选择最小元(或最大元)的数据结构。它是锦标赛排序思想的延伸。

2. 为什么需要败者树?
为了解决多路归并中顺序比较效率低下的问题。它通过树形结构记录比较结果,使得每次选出最小元后,重新调整树的代价很小。

3. 工作原理
我们以最小败者树为例(用于选出最小值):

  • 叶子节点:存放 K 路归并段当前参与比较的元素。
  • 内部节点:存放的是其子节点之间比较的 “败者”(即较大的那个)。而 “胜者”(较小的那个)则继续向上比较。
  • 根节点之上:有一个额外的节点,用于存放最终的 “胜者”(即全局最小元)。

工作流程分为初始化和调整两步:

  1. 初始化

    • 将 K 路元素的第一个值放入叶子节点。
    • 从底向上,两两比较,将败者(大值)记录在父节点中,胜者(小值)继续向上比较。
    • 最终,树顶的“胜者”就是当前 K 个元素中的最小值。
  2. 调整

    • 当我们输出这个最小值后,需要从该最小值所在的归并段中读取下一个元素,替换掉对应的叶子节点。
    • 然后,沿着从该叶子节点到根节点的路径,重新进行比赛。
    • 比较只在兄弟节点之间进行,新的败者留在父节点,胜者继续向上。
    • 这个过程只需要 \(\lceil \log_2 K \rceil\) 次比较。

4. 优势

  • 效率高:初始化需要 K-1 次比较,但之后每次调整(即每次选出一个最小元)仅需 \(\lceil \log_2 K \rceil\) 次比较,与 K 的大小无关。
  • 稳定:比较次数不随 K 的增大而线性增长,使得采用非常大的 K 值进行归并成为可能。

三、置换-选择排序

1. 基本概念
置换-选择排序用于外部排序的第一阶段,即生成初始归并段。它的目标是突破内存工作区大小的限制,生成长度大于内存容量的初始归并段

2. 为什么需要置换-选择排序?
传统方法生成的归并段大小 ≈ 内存工作区大小。如果归并段数量 N 减少,根据公式 \(S = \lceil \log_K N \rceil\),归并轮数 S 也会减少。置换-选择排序正是通过生成更少、更长的归并段来提升整体效率。

3. 工作原理
假设内存工作区大小为 w

  1. 初始化:从输入文件中读入 w 个记录到内存工作区。
  2. 创建归并段
    a. 从工作区中选出最小的记录(记为 MIN),将其输出到当前归并段。
    b. 从输入文件中读入下一个记录。
    c. 关键判断
    - 如果新读入的记录 大于或等于 刚输出的 MIN,那么它可以被纳入 当前 归并段。将其填入刚才 MIN 空出的位置。
    - 如果新读入的记录 小于 刚输出的 MIN,那么它不能被纳入当前归并段(否则会破坏有序性)。它只能被纳入 下一个 归并段。此时,我们将其放在一边,并缩小有效工作区范围。
    d. 从 当前有效的 工作区中再次选出最小记录作为新的 MIN,重复输出和替换过程。
  3. 结束当前归并段:当工作区中不再有任何大于等于上一个输出 MIN 的记录时(即所有记录都只能留给下一个归并段),当前归并段结束。
  4. 开始新归并段:将之前为下一个归并段“囤积”的记录重新纳入有效工作区,开始生成下一个归并段。
  5. 重复:直到所有输入记录处理完毕。

4. 效果

  • 生成的初始归并段的平均长度是 2w
  • 归并段数量减少,从而优化了后续的归并过程。

四、最佳归并树

1. 基本概念
最佳归并树解决了当前初始归并段长度不相等时,如何组织多路归并的顺序,使得总的 I/O 次数最少的问题。它的本质是 K 叉哈夫曼树

2. 为什么需要最佳归并树?

  • 使用置换-选择排序后,初始归并段的长度各不相同。
  • 如果随意进行归并,可能会将大的归并段过早地参与合并,导致“笨重的”数据被反复读写,增加 I/O 负担。
  • 最佳归并树通过 “让短的段先合并,长的段后合并” 的策略,使带权路径长度最短,即总 I/O 次数最少。

3. 构建过程(以 K 路归并为例)

  1. 构造虚拟归并段:如果初始归并段数量 N 无法直接构成一棵严格的 K 叉树(即 (N-1) % (K-1) != 0),需要补充 (K-1) - (N-1) % (K-1) 个长度为 0 的 虚段。这是为了确保在归并过程中,每次都是合并 K 个段,避免最后轮次合并的段数不足,造成浪费。
  2. 构建 K 叉哈夫曼树
    • 将所有归并段(包括虚段)视为叶子节点,其权重就是归并段的长度(记录数或字节数)。
    • 每次从集合中选择 K 个权重最小 的节点。
    • 将它们合并,生成一个新的父节点,该父节点的权重为这 K 个子节点权重之和。
    • 将这个新的父节点放回集合中。
    • 重复上述过程,直到集合中只剩下一个节点(根节点)。这棵树就是最佳归并树。

4. 如何指导归并?
这棵最佳归并树就指明了最优的归并顺序。从叶子节点开始,按照树的层次进行归并。父节点的权重就是合并这 K 个段所需进行的 I/O 次数(读入这 K 个段 + 写出合并后的段)。根节点的权重就是整个归并过程的总 I/O 代价。

5. 目标
最小化总的归并代价,即 最小化带权路径长度(WPL),从而最大限度地减少磁盘读写次数。

http://www.hskmm.com/?act=detail&tid=26124

相关文章:

  • 看vue文档记录(未整理)
  • Spring5笔记
  • 50天50个前端项目 - HTML/CSS和JavaScript实战合集
  • [BalticOI 2002] Tennis Club (Day1) 解题报告
  • 党徽
  • ZKEACMS:基于ASP.Net Core开发的开源免费内容管理系统
  • MySQL面试题汇总
  • 穷人的中国象棋打谱程序
  • 文件系统的层次结构
  • oracle 19c学习笔记2
  • 文件保护
  • 一些数数杂题
  • AI元人文:规则与人文的统一之路
  • 10.7
  • qmd 模拟赛的一道题
  • 四元数:从理论基础到实际应用的深度探索 - 教程
  • Day12
  • HoneyWell(霍尼韦尔)1450g扫码枪说明书
  • 课上动手东脑问题
  • 箭头函数的疑问
  • 文件共享
  • 【万字长文】让面试没有难撕的JS基础题
  • Java总览
  • PCoT: Persuasion-Augmented Chain of Thought for Detecting Fake News and Social Media Disinformation
  • 博客地址
  • 宏定义中,为什么使用:do{}while(0)这种模式是最安全的
  • 20251007J赛合订本
  • XML 元素:基础、应用与优化 - 教程
  • Educational Codeforces Round 183 (Rated for Div. 2) A~D
  • Cisco vManage漏洞分析:未授权RCE与权限提升完整攻击链