【学习笔记】数据结构（十一）

news/2025/1/12 23:15:21/

外部排序

文章目录

  • 外部排序
    • 11.1 外存信息的存取
    • 11.2 外部排序的方法
    • 11.3 多路平衡归并的实现 - 增加k
    • 11.4 置换-选择排序 - 减少m
    • 11.5 最佳归并树

外部排序 指的是大文件的排序，即待排序的记录存储在外存储器 上，在排序过程中需进行多次的内、外存之间的交换。

11.1 外存信息的存取

计算机一般有 两种存储器： 内存储器（主存）和外存储器（辅存）。

  • 内存的信息可随机存取，且存取速度快，但价格贵、容量小。

  • 外存储器包括磁带和磁盘（或磁鼓），前者为顺序存取的设备，后者为随机存取的设备。

1、磁带信息的存取

磁带是薄薄涂上一层磁性材料的一条窄带。

磁带不是连续运转的设备，而是一种启停设备（启停时间约为 5 毫秒），它可以根据读 ／写的需要随时启动和停止。由千读／写信息应在旋转稳定时进行，而磁带从静止状态启 动后，要经过一个加速的过程才能达到稳定状态；反之，在读／写结束后，从运动状态到完 全停止，要经过一个减速的过程。因此，在磁带上相邻两组字符组（记录）之间要留一空白 区，叫做 间隙 IRG(lnter Record Gap) 。

在每次写信息时， 将若干个字符组合并成一块后一次写入磁带。 于是，每个字符组间就没有 IRG,而变成 块间的间隙 IBG(lnter Block Gap) , 从而可以减少IRG 的数目，提高磁带的利用率，块的长度大于 IBG 的长度。

在这里插入图片描述

成块还可减少I/O操作。 因为一次1/0操作可把整个物理块都读到内存缓冲区中． 然后再从缓冲区中取出所需要的信息（一个字符组）。每当要读一个字符组时，首先要查 缓冲区中是否已有，若有，则不必执行I/O操作，直接从缓冲区读取即可。

在磁带上 读写一块信息所需的时间 由两部分组成： TI/O = ta + n · tw

  • ta 为延迟时间，读／写头到达传输信息所在物理块起始位置所需时间；
  • tw 为传输一 个字符的时间。

缺点：

由于磁带是 顺序存取 的设备，则读／写信息之前先要进行顺序查找，并且当读／写头位于磁带尾端，而要读的信息在磁带始端时，尚需使磁带倒转运动。这是顺序存取设备的主要缺点，它使检索和修改信息很不方便。

2、磁盘信息的存取

磁盘是一种 直接存取 的存储设备(DASO)。它的容量大、速度快，存 取速度比磁带快得多。

磁盘可以是单片的，也可以由若干盘片组成盘组。每一片上有两个面。以 6 片盘组为例，由于最顶上和最低下盘片的外侧面不存信息，所以总共只有10个面可用来保存信 息。盘片装在一个主轴上，并绕主轴高速旋转，当磁道在读／写头下通过时，便可以进行信息的读／写。

把磁盘分为 固定头盘和活动头盘 ：

  • 固定头盘的每 一道上都有独立的磁头，它是固定不动的，专负责读／写某一 道上的信息。
  • 活动头盘的磁头是可移动的。盘组也是可变的。一个 面上只有一个磁头，它可以从该面上的一道移动到另一道。 磁头装在一个动臂上，不同面上的磁头是同时移动的，并处 于同一圆柱面上。各个面上半径相同的磁道组成一个圆柱 面，圆柱面的个数就是盘片面上的磁道数。

在这里插入图片描述

在磁盘上标明一个具体信息必须用一个三维地址：柱面号、盘面号、块号

  • 柱面号确定读／写头的径向运动，
  • 块号确定信息在盘片圆圈上的位置。

在磁盘上读写一块信息步骤：

  • 首先必须找柱面，移动臂使磁头移 动到所需柱面上（称为定位或寻查）；
  • 然后等待要访问的信息转到磁头之下；
  • 最后，读／写所需信息。

在磁盘上读写一块信息所需的时间 由 3 部分组成： TI/O = tseek + tla + twm

  • tseek 为寻查时间(seek time) , 即读／写头定位的时间；
  • tla 为等待时间(latency time), 即等待信息块的初始位置旋转到读写头下的时间；
  • twm 为传输时间(transmission time)

内外存之间的数据交换原理：

在这里插入图片描述

11.2 外部排序的方法

外部排序基本上由两个相对独立的阶段组成:

  • 按可用内存大小，将外存上含 n 个记录的文件分成若干长度为 l 的子文件或段(segment),依次读入内存并利用有效的内 部排序方法对它们进行排序，并将排序后得到的有序子文件重新写入外存，通常称这些有序子文件为归并段或顺串(run);
  • 对这些归并段进行逐趟归并，使归并段（有序的子文件）逐渐由小至大，直至得到整个有序文件为止

在这里插入图片描述

外部排序所需总的时间＝内部排序（产生初始归并段）所需的时间(m * tIS) + 外存信息读写的时间(d * tIO) + 内部归并所需的时间(s * utmg）

  • tIS：为得到一个初始归并段进行内部排序所需时间的均值；
  • m：为经过内部排序之后得到的初始归并段的个数I
  • tIO：是进行一次外存 读／写时间的均值；取决于所用的外存设备；
  • d：为总的读／写次数
  • utmg：对u 个记录进行内部归并所需时间；
  • s ：为归并的趟数；

tIO 比 tmg大得多，所以提高外排的效率应主要 着眼于减少外存信息读写的次数d

假设在每个物理块可以容纳 200个记录，则每一趟归并需进行 50 次“读” 和 50 次“写"’

利用 2-路归并：4 趟 * 100 + 100 内部排序 = 500 次的读／写。

利用 5-路归并：2 趟 * 100 + 100 内部排序 = 300 次的读／写。

可见，对同一文件而言，进行外排时所需读／写外存的次数和归并的趟数 s成正比。

对m个初始归并段进行k-路平衡归并时，归并的趟数 s = ⌊ logkm ⌋ —— 可见，若增加 K 或减少m 便能减少s。

若能增加初始归并段的长度则可减少初始归并段数量m

例子：

在这里插入图片描述

11.3 多路平衡归并的实现 - 增加k

每一趟从m个归并段得到 ⌈m/k⌉ 归并段。这种归并方法称为 k-路平衡归并

使用k路平衡归并策略，选出一个最小元素需要对比关键字(k-1)次，所以增加k会导致内部归并所需时间增加

eg：8路平衡归并，从公企归并段中选出一个最小元素需要对比关键字7次

在这里插入图片描述

“败者树"(Tree of Loser)：可视为一棵完全二叉树)(根节点上多了一个结点)。k个叶结点分别是当前参加比较的元素，非叶子结点用来记忆左右子树中的“失败者”，而让胜者往上继续进行比较，一直到根结点。目的- 使k元素的关键字对比次数变少

在这里插入图片描述

#define _CRT_SECURE_NO_WARNINGS 1  // 禁用 Visual Studio 的安全警告（例如 scanf 的安全问题）
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>// 定义状态码，用于表示函数执行的成功或失败
#define OK 1
#define OVERFLOW -2
#define ERROR -1// 栈的初始大小
#define STACK_INIT_SIZE 4// 定义归并段的数量
#define K 5// 定义最大键值和最小键值
#define MAXKEY INT_MAX  // 表示归并段结束的特殊键值
#define MINKEY INT_MIN  // 用于初始化败者树的虚拟键值// 定义状态类型
typedef int Status;// 定义栈的结构体
typedef struct {int* base;      // 栈的基地址（栈底）int* top;       // 栈顶指针int stacksize;  // 栈的当前容量
} SqStack;// 定义键值类型
typedef int KeyType;// 定义败者树，大小为 K
typedef int LoserTree[K];// 定义外部节点结构体
typedef struct {KeyType key;  // 外部节点的键值
} ExNode, External[K + 1];  // 外部节点数组，大小为 K + 1（用于败者树）/*** 初始化栈* @param S 栈的指针* @return 成功返回 OK，失败返回 OVERFLOW*/
Status InitStack(SqStack* S) {S->base = (int*)malloc(STACK_INIT_SIZE * sizeof(int));  // 分配栈的初始内存if (!S->base)exit(OVERFLOW);  // 内存分配失败，退出程序S->top = S->base;  // 初始化栈顶指针为栈底S->stacksize = STACK_INIT_SIZE;  // 初始化栈的容量return OK;  // 初始化成功
}/*** 向栈中压入元素* @param S 栈的指针* @param e 要压入的元素* @return 成功返回 OK，失败返回 OVERFLOW*/
Status Push(SqStack* S, int e) {// 如果栈已满，则需要扩容if (S->top - S->base >= S->stacksize) {int* new_base = (int*)realloc(S->base, (S->stacksize + STACK_INIT_SIZE) * sizeof(int));  // 重新分配内存if (!new_base) {return OVERFLOW;  // 内存分配失败，返回错误}S->base = new_base;  // 更新栈底指针S->stacksize += STACK_INIT_SIZE;  // 更新栈的容量}*S->top++ = e;  // 将元素压入栈顶，并移动栈顶指针return OK;  // 成功返回 OK
}/*** 从栈中弹出元素* @param S 栈的指针* @param e 用于存储弹出元素的变量* @return 成功返回 OK，失败返回 ERROR*/
Status Pop(SqStack* S, int* e) {if (S->top == S->base) {return ERROR;  // 如果栈为空，返回错误}*e = *(--S->top);  // 弹出栈顶元素，并移动栈顶指针return OK;  // 成功返回 OK
}/*** 调整败者树的某个节点* @param ls 败者树* @param b 外部节点数组* @param s 当前要调整的节点索引*/
void Adjust(LoserTree ls, External b, int s) {int t, tmp;// 计算当前节点的父节点索引t = (s + K) / 2;  // 公式：(s + K) / 2，用于找到父节点索引// 从当前节点向上调整到根节点while (t > 0) {// 如果当前节点的值大于父节点的值if (b[s].key > b[ls[t]].key) {tmp = s;  // 交换当前节点和父节点s = ls[t];ls[t] = tmp;}t = t / 2;  // 继续向上调整}ls[0] = s;  // 更新胜者节点（ls[0] 始终存储当前胜者）
}/*** 创建败者树* @param ls 败者树* @param b 外部节点数组*/
void CreateLoserTree(LoserTree ls, External b) {int i;// 初始化外部节点的虚拟节点（用于处理特殊情况）b[K].key = MINKEY;  // 第 K 个外部节点的键值设置为 MINKEY// 初始化败者树的叶子节点（归并段的索引）for (i = 0; i < K; i++) {ls[i] = K;  // 初始化败者树的叶子节点为虚拟节点}// 从最后一个叶子节点开始调整败者树for (i = K - 1; i >= 0; i--) {Adjust(ls, b, i);  // 调整败者树}
}/*** K 路归并* @param ls 败者树* @param b 外部节点数组* @param S 栈数组*/
void K_merge(LoserTree ls, External b, SqStack* S) {int i, q;// 从每个栈中弹出第一个元素作为初始值for (i = 0; i < K; i++) {Pop(&S[i], &b[i].key);  // 从第 i 个栈中弹出第一个元素}// 创建败者树CreateLoserTree(ls, b);// 当胜者节点的值不为 MAXKEY 时，继续归并while (b[ls[0]].key != MAXKEY) {q = ls[0];  // 获取当前胜者节点（ls[0] 始终存储胜者索引）printf("%d ", b[q].key);  // 输出胜者节点的值// 从胜者节点的栈中弹出下一个元素Pop(&S[q], &b[q].key);// 调整败者树Adjust(ls, b, q);}printf("\n");  // 输出换行符
}/*** 主函数*/
void main() {int i, j;int e;SqStack S[K];  // 每个归并段对应一个栈LoserTree ls;  // 败者树External b;  // 外部节点数组// 初始化每个归并段的栈for (i = 0; i < K; i++) {InitStack(&S[i]);  // 初始化第 i 个栈Push(&S[i], MAXKEY);  // 将 MAXKEY 压入栈底，表示归并结束// 输入 3 个元素for (j = 0; j < 3; j++) {printf("S[%d] push: ", i);scanf("%d", &e);  // 从标准输入读取一个整数Push(&S[i], e);  // 将读取的整数压入栈中}}// 执行 K 路归并K_merge(ls, b, S);
}

在这里插入图片描述

11.4 置换-选择排序 - 减少m

m是外部文件经过内部排序之后 得到的初始归并段的个数，

m = ⌈n/l⌉, 其中 n 为外部文件中的记录数，l 为初始归并段中的记录数

注意事项：

  • 当归并段为空时，选择工作区内最小数
  • 当归并段不为空时，选择工作区内【大于归并段最大值的-归并段最后一个值】最小数
  • 不能被放进归并段时，需重新创建一个归并段

在这里插入图片描述

11.5 最佳归并树

2路归并

在这里插入图片描述

多路归并

在这里插入图片描述

补充虚段

k路最佳归并树：

  • 一定是一棵严格的 k叉树
  • 只有度为0和度为k的结点

在这里插入图片描述

添加虚段的数量：

初始归并段数量 + 虚段数量 = n0 = 度为0的结点数

度为k的结点数 = nk

① 总结点数 = n = n0 + nk

② 叉的数量 = 分支结点 nk * 每个分支结点发出的分叉数 k = 除根节点外的其他结点都被一个分叉连着 n - 1 即 nk * k = n - 1

① 和 ② => n0 =（k-1）nk + 1 => nk = (n0 - 1) / (k - 1) 如果是“严格k叉树”一定能除得尽

① 若(初始归并段数量 -1) % (k-1)=0，说明刚好可以构成严格k叉树，此时不需要添加虚段

② 若(初始归并段数量 -1) % (k-1) = u ≠ 0，则需要添加虚段(k-1) - u个

在这里插入图片描述

例题：设外存上有120个初始归并段，进行12路归并时，为实现最佳归并，需要补充的虚段个数是()
A.1 B.2 C.3 D.4

（120 - 1）% (12 - 1) = 9; 则补充 (12 - 1) - 9 = 2

例题：已知三叉树T中6个叶结点的权分别是2，3，4，5，6，7，T的带权(外部)路径长度最小的是()
A.27 B.46 C.54 D.56

（6 - 1）% (3 - 1) = 1 ≠ 0; 需要补充的虚段个数是1；则变成【0，2，3，4，5，6，7】，WPLmin = (2+3)*3 + (4+5)*2 + (6+7)*1 = 15 + 18 + 13 = 46

0
2
3
4
5
6
7
5
14
27

参考：

教材：严蔚敏《数据结构》（C语言版）.pdf

视频：

外部排序

败者树

置换选择排序

博客：

多路平衡归并败者树(Tree of Loser)算法


http://www.ppmy.cn/news/1562630.html

相关文章

【cs.AI】25.1.10 arxiv更新速递

【cs.AI】25.1.10 arxiv更新速递

25.1.9 12:00 - 25.1.10 12:00 共更新91 篇 —第1篇---- ===== Progressive Growing of Video Tokenizers for Highly Compressed Latent Spaces 🔍 关键词: 视频分词器, 潜在视频扩散模型, 时间压缩, 重构质量, 视频生成 PDF链接 摘要: 视频分词器对于潜在视频扩散模型…
阅读更多...
spring boot发送邮箱，java实现邮箱发送（邮件带附件）3中方式【保姆级教程一，代码直接用】

spring boot发送邮箱，java实现邮箱发送（邮件带附件）3中方式【保姆级教程一，代码直接用】

文章目录 Java发送邮箱的方式1. 基于 Javax.mail 实现关于附件上传的方法 2. 基于 org.apache.commons.mail 实现常见报错 3. 基于 spring-boot-starter-mail 实现&#xff08;推荐&#xff09; 实际开发时需要实现邮件发送&#xff0c;本文章实现如何从零实现邮件发送。也就是…
阅读更多...
使用 Docker 构建 preboot 交叉编译环境

使用 Docker 构建 preboot 交叉编译环境

ASR1606/ASR1603 的 preboot 代码需要在 Linux 环境下编译&#xff0c;通常使用 VMware 或者 VirtualBox 软件创建一个 Linux 虚拟机&#xff0c;在虚拟机中做交叉编译。但 preboot 不是那种需要经常编译的代码&#xff0c;完全可以将 preboot 的编译环境制作成 docker 镜像&am…
阅读更多...
TCP通信原理学习

TCP通信原理学习

TCP三次握手和四次挥手以及为什么_哔哩哔哩_bilibili
阅读更多...
【设计模式】介绍常见的设计模式

【设计模式】介绍常见的设计模式

&#x1f970;&#x1f970;&#x1f970;来都来了&#xff0c;不妨点个关注叭&#xff01; &#x1f449;博客主页&#xff1a;欢迎各位大佬!&#x1f448; 文章目录 ✨ 介绍一下常见的设计模式✨ Spring 中常见的设计模式 这期内容主要是总结一下常见的设计模式&#xff0c;可…
阅读更多...
应急响应之入侵排查（下）

应急响应之入侵排查（下）

一.进程排查 1.Windows 任务管理器查看 在 Windows 系统中&#xff0c;可通过任务管理器查看进程信息。操作步骤为&#xff1a;在任务管理器界面&#xff0c;于 “查看” 选项中选择 “选择列”&#xff0c;随后添加 “映像路径名称” 和 “命令行”&#xff0c;以此查看更多进…
阅读更多...
探索 Oracle 数据库：核心概念与实践指南

探索 Oracle 数据库：核心概念与实践指南

Oracle 数据库是业界领先的关系型数据库管理系统 (RDBMS)&#xff0c;广泛应用于企业级应用和大型数据处理。本文将深入探讨 Oracle 数据库的核心概念、常用功能以及最佳实践&#xff0c;帮助你更好地理解和使用 Oracle 数据库。 1. Oracle 数据库的核心概念 1.1 体系结构 O…
阅读更多...
Android中Activity

Android中Activity

一、AndroidManifest中的<activity>标签 <activity>标签在AndroidManifest.xml文件中用于定义和配置应用中的每一个Activity。Activity是Android应用的基本构建块之一&#xff0c;主要负责展示用户界面&#xff0c;并处理用户与之的交互。每个在应用中显示给用户的…
阅读更多...
最新文章

Copyright @ 2022~2023