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

外部排序快速入门详解:基本原理,败者树,置换-选择排序,最佳归并树

文章目录

  • 外部排序
    • 1.最基本的外部排序原理
    • 2.外部排序的优化
    • 2.1 败者树优化方法
    • 2.2 置换-选择排序优化方法
    • 2.3 最佳归并树

外部排序

为什么要学习外部排序?
答:
在处理数据的过程中,我们需要把磁盘(外存)中存储的数据拿到内存中处理,因为内存处理更快,但是由于内存空间较小,外存空间很大,外存中的数据元素太多,无法一次全部读入内存进行排序。所以,通过外部排序就是实现对于外存存储元素排序的方法。

1.最基本的外部排序原理

假设在外存中,我们有48个记录,按照每三个记录为一块,建立好基本16个分块。
注意:在建立基本的分块之前,外存的每个小分块要先进行内部排序,保证这16个分块内部是有序的。
内存中,有2个输入缓冲区和1个输出缓冲区,采用归并排序的思想,第一次,先从16个分块中拿出两块,分别放入缓冲区1和缓冲区2.然后每次从这两个缓冲区6的开头,选最小的,放入输出缓冲区,然后凑齐3个记录,就回填外存。以此类推,直到把这1个分块,变为8个分块。

第二次开始,本质还是这个过程,但是值得注意的是,我们必须保证输入缓冲区不空,即如果一旦一个缓冲区的元素被拿空了,要立刻用该分块的其它元素补上。
在这里插入图片描述

外部排序时间开销=读写外存的时间+内部排序所需时间+内部归并所需时间

不难得知,采用多路归并可以减少归并趟数。

记结论:
生成初始片段r个,进行k路归并
则趟数S=⌈logkr

2.外部排序的优化

方法1
方法2
优化
增加k
减少r
增加相应的输入缓冲区
减少每次从k个归并段中选一个最小元素的关键字比较次数
败者树优化方法
置换-选择排序优化方法

2.1 败者树优化方法

败者树用来减少关键字的比较次数。

将各个归并段段开头加入到败者树的叶子结点,然后开始构造败者树,注意,中间结点记录的是,当前胜者是来自哪个归并端,在得到冠军来自3号归并端后,将3号归并段的叶子结点移除,将3号归并段新的结点补上,此时,不需要比较太多次,通过败者树向上比较,就可以得出新的冠军,以此类推。
在这里插入图片描述

效率分析:
对于k路归并,第一次构造败者树需要对比关键字k-1次,
有了败者树,选出最小元素,只需要对比⌈log2k

2.2 置换-选择排序优化方法

让归并段更少,即让归并段更长。

初始待排序文件,不断的将当前内存工作区中,大于minmax的最小值,加入归并段中,每加入一个,再从初始待排序文件中补充一个,直到内存工作区中的所有元素都小于minmax,然后开始输出归并段2,更改minmax,重复上述过程。

在这里插入图片描述

在这里插入图片描述

2.3 最佳归并树

对于归并过程进一步优化。

只讲干货:
每个初始归并端对应一个叶子结点,把归并段段块数作为叶子的权值。最好的归并的过程其实就是构造哈夫曼树的过程。
归并树的WPL=归并过程中的磁盘I/O次数

值得注意的是,k叉归并的最佳归并树一定是严格k叉树,所以很可能叶子结点的个数不满足构造严格k叉归并树,这时候需要补充虚段(权值为0的叶子结点,然后将这些权值为0的结点作为最初始的构造结点.

补充虚段的数量有公式:
(初始归并段数量-1)%(k-1)=u
若u=0,则说明不需要添加虚段,否则添加(k-1)-u个虚段。

下图是一个3路归并的最佳归并树。
在这里插入图片描述

相关文章:

外部排序快速入门详解:基本原理,败者树,置换-选择排序,最佳归并树

文章目录 外部排序1.最基本的外部排序原理2.外部排序的优化2.1 败者树优化方法2.2 置换-选择排序优化方法2.3 最佳归并树 外部排序 为什么要学习外部排序? 答: 在处理数据的过程中,我们需要把磁盘(外存)中存储的数据拿到内存中处理…...

人工智能和物联网如何结合

欢迎来到 Papicatch的博客 目录 ​ 🍉引言 🍉AI与IoT的结合方式 🍈数据处理和分析 🍍实例 🍈边缘计算 🍍实例 🍈自动化和自主操作 🍍实例 🍈安全和隐私保护 &…...

【JAVASE】JAVA应用案例(下)

一:抢红包 一个大V直播时,发起了抢红包活动,分别有9,666,188,520,99999五个红包。请模拟粉丝来抽奖,按照先来先得,随机抽取,抽完即止,注意:一个红包只能被抽一次,先抽或…...

【面试干货】 B 树与 B+ 树的区别

【面试干货】 B 树与 B 树的区别 1、B 树2、 B 树3、 区别与优缺点比较4、 总结 💖The Begin💖点点关注,收藏不迷路💖 在数据库系统中,B 树和 B 树是常见的索引结构,它们在存储和组织数据方面有着不同的设计…...

Socket编程权威指南(四)彻底解密 Epoll 原理

在上一篇文章中,我们优化了基于 Socket 的网络服务器,从最初的 select/poll 模型进化到了高效的 epoll。很多读者对 epoll 的惊人性能表示极大的兴趣,对它的工作原理也充满了好奇。今天,就让我们一起揭开 epoll 神秘的面纱&#x…...

Windows开始ssh服务+密钥登录+默认启用powershell

文章内所有的命令都在power shell内执行,使用右键单击Windows徽标,选择终端管理员即可打开 Windows下OpenSSH的安装 打开Windows power shell,检查SSH服务的安装状态。会返回SSH客户端和服务器的安装状态,一下是两个都安装成功的…...

实体商铺私域流量打造策略:从引流到转化的全链路解析

在数字化时代,实体商铺面临着前所未有的挑战与机遇。随着线上购物的兴起,传统商铺如何吸引并留住顾客,成为了每个实体店家必须面对的问题。私域流量的打造,正是解决这一问题的关键所在。本文将从引流、留存、转化三个方面&#xf…...

实战 | 通过微调SegFormer改进车道检测效果(数据集 + 源码)

背景介绍 SegFormer:实例分割在自动驾驶汽车技术的快速发展中发挥了关键作用。对于任何在道路上行驶的车辆来说,车道检测都是必不可少的。车道是道路上的标记,有助于区分道路上可行驶区域和不可行驶区域。车道检测算法有很多种,每…...

翻译《The Old New Thing》- Why do messages posted by PostThreadMessage disappear?

Why do messages posted by PostThreadMessage disappear? - The Old New Thing (microsoft.com)https://devblogs.microsoft.com/oldnewthing/20090930-00/?p16553 Raymond Chen 2008年09月30日 为什么 PostThreadMessage 发布的信息会消失? 在显示用户界面的线…...

【深度学习】—— 神经网络介绍

神经网络介绍 本系列主要是吴恩达深度学习系列视频的笔记,传送门:https://www.coursera.org/deeplearning-ai 目录 神经网络介绍神经网络的应用深度学习兴起的原因 神经网络,全称人工神经网络(Artificial Neural Network&#xf…...

python-数字黑洞

[题目描述] 给定一个三位数,要求各位不能相同。例如,352是符合要求的,112是不符合要求的。将这个三位数的三个数字重新排列,得到的最大的数,减去得到的最小的数,形成一个新的三位数。对这个新的三位数可以重…...

SpringCloud 负载均衡 spring-cloud-starter-loadbalancer

简述 spring-cloud-starter-loadbalancer 是 Spring Cloud 中的一个组件,它提供了客户端负载均衡的功能。在 Spring Cloud 的早期版本中,Netflix Ribbon 被广泛用作客户端负载均衡器,但随着时间推移和 Netflix Ribbon 进入维护模式&#xff…...

牛客周赛-46

牛客周赛-46 a乐奈吃冰b素世喝茶c爱音开灯d小灯做题 a乐奈吃冰 ac code #include<iostream> using namespace std; int main(){long long a,b;cin>>a>>b;int tmpmin(b,a/2);long long resatmp;cout<<res;return 0; }b素世喝茶 #include<iostream…...

多模态vlm综述:An Introduction to Vision-Language Modeling 论文解读

目录 1、基于对比学习的VLMs 1.1 CLIP 2、基于mask的VLMs 2.1 FLAVA 2.2 MaskVLM 2.3 关于VLM目标的信息理论视角 3、基于生成的VLM 3.1 学习文本生成器的例子: 3.2 多模态生成模型的示例: 3.3 使用生成的文本到图像模型进行下游视觉语言任务 4、 基于预训练主干网…...

28.找零

上海市计算机学会竞赛平台 | YACSYACS 是由上海市计算机学会于2019年发起的活动,旨在激发青少年对学习人工智能与算法设计的热情与兴趣,提升青少年科学素养,引导青少年投身创新发现和科研实践活动。https://www.iai.sh.cn/problem/744 题目描述 有一台自动售票机,每张票卖 …...

[方法] 《鸣潮》/《原神》呼出与锁定光标的功能细节

本方法适用于Cinemachine - FreeLook。 1. 锁定与呼出光标的功能实现 // 锁定光标 private void LockMouse() {// 将光标锁定在屏幕中间Cursor.lockState CursorLockMode.Locked;// 隐藏光标Cursor.visible false; }// 呼出光标 private void UnLockMouse() {// 释放光标Cu…...

计算机网络-NAT配置与ACL

目录 一、ACL 1、ACL概述 2、ACL的作用 3、ACL的分类 4、ACL的配置格式 二、NAT 1、NAT概述 2、NAT分类 2.1 、 静态NAT 2.2 、 动态NAT 3、NAT的功能 4、NAT的工作原理 三、NAT配置 1、静态NAT配置 2、动态NAT配置 四、总结 一、ACL 1、ACL概述 ACL&#xff…...

哈尔滨三级等保测评需要测哪些设备?

哈尔滨三级等保测评需要测的设备&#xff0c;主要包括物理安全设备、网络安全设备和应用安全设备三大类别。这些设备在保障哈尔滨地区信息系统安全方面发挥着至关重要的作用。 首先&#xff0c;物理安全设备是确保信息系统实体安全的基础。在哈尔滨三级等保测评中&#xff0c;物…...

大学体育(二)(华中科技大学) 中国大学MOOC答案2024版100分完整版

大学体育&#xff08;二&#xff09;(华中科技大学) 中国大学MOOC答案2024版100分完整版 有氧运动 有氧运动单元测验 1、 世界卫生组织对18-64岁年龄组成年人的运动建议是&#xff1a;每周至少&#xff08; &#xff09;分钟的中等强度有氧身体活动&#xff0c;或者每周至少&a…...

Web前端策划:从理念到实现的全方位解析

Web前端策划&#xff1a;从理念到实现的全方位解析 在数字化时代的浪潮中&#xff0c;Web前端策划作为连接技术与用户界面的桥梁&#xff0c;扮演着至关重要的角色。它涉及从用户需求分析、设计构思到技术实现的全方位过程&#xff0c;要求策划者具备深厚的技术功底和敏锐的市…...

树莓派超全系列教程文档--(62)使用rpicam-app通过网络流式传输视频

使用rpicam-app通过网络流式传输视频 使用 rpicam-app 通过网络流式传输视频UDPTCPRTSPlibavGStreamerRTPlibcamerasrc GStreamer 元素 文章来源&#xff1a; http://raspberry.dns8844.cn/documentation 原文网址 使用 rpicam-app 通过网络流式传输视频 本节介绍来自 rpica…...

基于距离变化能量开销动态调整的WSN低功耗拓扑控制开销算法matlab仿真

目录 1.程序功能描述 2.测试软件版本以及运行结果展示 3.核心程序 4.算法仿真参数 5.算法理论概述 6.参考文献 7.完整程序 1.程序功能描述 通过动态调整节点通信的能量开销&#xff0c;平衡网络负载&#xff0c;延长WSN生命周期。具体通过建立基于距离的能量消耗模型&am…...

vscode(仍待补充)

写于2025 6.9 主包将加入vscode这个更权威的圈子 vscode的基本使用 侧边栏 vscode还能连接ssh&#xff1f; debug时使用的launch文件 1.task.json {"tasks": [{"type": "cppbuild","label": "C/C: gcc.exe 生成活动文件"…...

镜像里切换为普通用户

如果你登录远程虚拟机默认就是 root 用户&#xff0c;但你不希望用 root 权限运行 ns-3&#xff08;这是对的&#xff0c;ns3 工具会拒绝 root&#xff09;&#xff0c;你可以按以下方法创建一个 非 root 用户账号 并切换到它运行 ns-3。 一次性解决方案&#xff1a;创建非 roo…...

JVM暂停(Stop-The-World,STW)的原因分类及对应排查方案

JVM暂停(Stop-The-World,STW)的完整原因分类及对应排查方案,结合JVM运行机制和常见故障场景整理而成: 一、GC相关暂停​​ 1. ​​安全点(Safepoint)阻塞​​ ​​现象​​:JVM暂停但无GC日志,日志显示No GCs detected。​​原因​​:JVM等待所有线程进入安全点(如…...

代理篇12|深入理解 Vite中的Proxy接口代理配置

在前端开发中,常常会遇到 跨域请求接口 的情况。为了解决这个问题,Vite 和 Webpack 都提供了 proxy 代理功能,用于将本地开发请求转发到后端服务器。 什么是代理(proxy)? 代理是在开发过程中,前端项目通过开发服务器,将指定的请求“转发”到真实的后端服务器,从而绕…...

力扣-35.搜索插入位置

题目描述 给定一个排序数组和一个目标值&#xff0c;在数组中找到目标值&#xff0c;并返回其索引。如果目标值不存在于数组中&#xff0c;返回它将会被按顺序插入的位置。 请必须使用时间复杂度为 O(log n) 的算法。 class Solution {public int searchInsert(int[] nums, …...

安宝特方案丨船舶智造的“AR+AI+作业标准化管理解决方案”(装配)

船舶制造装配管理现状&#xff1a;装配工作依赖人工经验&#xff0c;装配工人凭借长期实践积累的操作技巧完成零部件组装。企业通常制定了装配作业指导书&#xff0c;但在实际执行中&#xff0c;工人对指导书的理解和遵循程度参差不齐。 船舶装配过程中的挑战与需求 挑战 (1…...

【SSH疑难排查】轻松解决新版OpenSSH连接旧服务器的“no matching...“系列算法协商失败问题

【SSH疑难排查】轻松解决新版OpenSSH连接旧服务器的"no matching..."系列算法协商失败问题 摘要&#xff1a; 近期&#xff0c;在使用较新版本的OpenSSH客户端连接老旧SSH服务器时&#xff0c;会遇到 "no matching key exchange method found"​, "n…...

django blank 与 null的区别

1.blank blank控制表单验证时是否允许字段为空 2.null null控制数据库层面是否为空 但是&#xff0c;要注意以下几点&#xff1a; Django的表单验证与null无关&#xff1a;null参数控制的是数据库层面字段是否可以为NULL&#xff0c;而blank参数控制的是Django表单验证时字…...