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

本文主要是介绍外部排序快速入门详解:基本原理,败者树,置换-选择排序,最佳归并树,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

文章目录

  • 外部排序
    • 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路归并的最佳归并树。
在这里插入图片描述

这篇关于外部排序快速入门详解:基本原理,败者树,置换-选择排序,最佳归并树的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1048020

相关文章

java中反射(Reflection)机制举例详解

《java中反射(Reflection)机制举例详解》Java中的反射机制是指Java程序在运行期间可以获取到一个对象的全部信息,:本文主要介绍java中反射(Reflection)机制的相关资料... 目录一、什么是反射?二、反射的用途三、获取Class对象四、Class类型的对象使用场景1五、Class

golang 日志log与logrus示例详解

《golang日志log与logrus示例详解》log是Go语言标准库中一个简单的日志库,本文给大家介绍golang日志log与logrus示例详解,感兴趣的朋友一起看看吧... 目录一、Go 标准库 log 详解1. 功能特点2. 常用函数3. 示例代码4. 优势和局限二、第三方库 logrus 详解1.

一文详解如何从零构建Spring Boot Starter并实现整合

《一文详解如何从零构建SpringBootStarter并实现整合》SpringBoot是一个开源的Java基础框架,用于创建独立、生产级的基于Spring框架的应用程序,:本文主要介绍如何从... 目录一、Spring Boot Starter的核心价值二、Starter项目创建全流程2.1 项目初始化(

Spring Boot3虚拟线程的使用步骤详解

《SpringBoot3虚拟线程的使用步骤详解》虚拟线程是Java19中引入的一个新特性,旨在通过简化线程管理来提升应用程序的并发性能,:本文主要介绍SpringBoot3虚拟线程的使用步骤,... 目录问题根源分析解决方案验证验证实验实验1:未启用keep-alive实验2:启用keep-alive扩展建

Java异常架构Exception(异常)详解

《Java异常架构Exception(异常)详解》:本文主要介绍Java异常架构Exception(异常),具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录1. Exception 类的概述Exception的分类2. 受检异常(Checked Exception)

C#基础之委托详解(Delegate)

《C#基础之委托详解(Delegate)》:本文主要介绍C#基础之委托(Delegate),具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录1. 委托定义2. 委托实例化3. 多播委托(Multicast Delegates)4. 委托的用途事件处理回调函数LINQ

Python GUI框架中的PyQt详解

《PythonGUI框架中的PyQt详解》PyQt是Python语言中最强大且广泛应用的GUI框架之一,基于Qt库的Python绑定实现,本文将深入解析PyQt的核心模块,并通过代码示例展示其应用场... 目录一、PyQt核心模块概览二、核心模块详解与示例1. QtCore - 核心基础模块2. QtWid

SpringBoot使用OkHttp完成高效网络请求详解

《SpringBoot使用OkHttp完成高效网络请求详解》OkHttp是一个高效的HTTP客户端,支持同步和异步请求,且具备自动处理cookie、缓存和连接池等高级功能,下面我们来看看SpringB... 目录一、OkHttp 简介二、在 Spring Boot 中集成 OkHttp三、封装 OkHttp

Redis 中的热点键和数据倾斜示例详解

《Redis中的热点键和数据倾斜示例详解》热点键是指在Redis中被频繁访问的特定键,这些键由于其高访问频率,可能导致Redis服务器的性能问题,尤其是在高并发场景下,本文给大家介绍Redis中的热... 目录Redis 中的热点键和数据倾斜热点键(Hot Key)定义特点应对策略示例数据倾斜(Data S

Android Kotlin 高阶函数详解及其在协程中的应用小结

《AndroidKotlin高阶函数详解及其在协程中的应用小结》高阶函数是Kotlin中的一个重要特性,它能够将函数作为一等公民(First-ClassCitizen),使得代码更加简洁、灵活和可... 目录1. 引言2. 什么是高阶函数?3. 高阶函数的基础用法3.1 传递函数作为参数3.2 Lambda