外部排序的方法

在实际应用中,由于外存设备的不同,通常又可分配磁盘文件排序和磁带文件排序两大类。磁带排序和磁盘排序的基本步骤相类似,主要的不同之处在于初始归并段在外存介质中的分布方式,磁盘是直接存储设备,磁带是顺序存储设备。下面以磁盘为例进行说明。

文件通常是按块存储在磁盘上的,操作系统也是按块对磁盘上的信息进行读写的。因为磁盘读写的机械动作所需时间远远超过内存运算的时间(相比而言,可以忽略不计)。因此,在外部排序过程中的时间代价主要考虑访问磁盘的次数,即I/O次数。

外部排序通常采用归并排序方法。它包括两个相对独立的阶段:首先,根据内存缓冲区的大小,将外存上含n个记录的文件分成若干个长度为h的子文件,依次读入内存并利用有效的内存排序方法对它们进行排序,并将排序后得到的有序子文件重新写回外存,通常称这些有序子文件为归并段或顺串;然后,对这些归并段进行逐趟归并,使归并段(有序的子文件)逐渐由小到大,直至得到整个有序文件为止。

例如,一个含有2000个记录的文件,每个磁盘可容纳250个记录,则该文件包含8个磁盘块。然后对该文件作二路归并排序,每次往内存读入两个磁盘块,排序后再写回磁盘。若把内存工作区等分为3个缓冲区。其中的两个为输入缓冲区。一个为输出缓冲区,在内存中利用简单二路归并merge函数实现二路归并。

首先,从参加归并排序的两个输入归并段R1和R2中分别读入一个块,放入输入缓冲区1和输入缓冲区2中。然后,在内存中进行二路归并,归并出来的对象顺序存放在输出缓冲区中。若输出缓冲区存满,则将其内的对象顺序写到归并段(R1')中,再将该输出缓冲区清空,继续存放归并后的对象。若某一个输入缓冲区的对象取空,则从对应的输入归并段中再读取下一块(这种情况在第一趟归并时不会出现),继续参加归并。如此继续,直到两个输入归并段中对象全部读入内存并都归并完成为止。当R1和R2归并完后,再归并R3和R4、R5和R6、最后归并R7和R8,这算作一趟归并。再把上一趟的结果R1'、R2'、R3'、R4'两两归并,这又是一趟归并。最后把R1''和R2"两两归并,这又是一趟归并。最后把R1"和R2"两两归并段归并,结果得到最终的有序文件,一共进行了3趟归并。

在外部排序中实现两两归并时,不仅要调用merge过程,而且要进行外存的读写;由于不可能将两个有序段及归并结果段同时存放在内存中,需要不停地将数据读出、写入磁盘,这将耗费大量的时间。一般情况下:

Tes=R*Tis+d*Tio+S*(n-1)*Tmg

其中,r是初始归并段个数,Tis是对每一个初始归并段进行内部排序的时间,d是访问外存块的次数,Tio是每一个块的存取时间,S是归并趟数,n是每趟参加二路归并的记录个数,Tmg是每作一次内部归并,取得一个关键字最小记录的时间。显然磁盘存取的时间远远大于内部排序和内部归并的时间,因此要提高外排序的速度,应着力减少d,即I/O次数。

由于外存上信息的读写是以“物理块”为单位的,且每个物理块可容纳250个记录,可知每一趟归并需要进行8次读和8次写,3趟归并加上内部排序时所需进行的读写使得在外排中总共需要进行16*4=64次的读写。故上述二路归并排序的总时间为:

8*Tis+64*Tio+3*2000Tmg

对于上例,若采用思路归并排序只需要2趟归并,外排时总的读写次数便减至2*16+16=48.因此,增大归并路数,可以减少归并趟数,从而减少总的I/O次数。

一般地,对r个初始归并段,作m路平衡归并,归并树可用严格m叉树(即只有度为m与度为0的结点的m叉树)来表示。第一趟可将r个初始并段归并为[r/m]个归并段,以后每一趟归并将L个归并段归并成【L/m】(向下取整)个归并段,直到最后形成一个大的归并段为止。树的高度=【logm r】(向下取整)=归并趟数S.

可见只要增大归并路m,或减少初始归并段个数r,都能减少归并趟数S,以减少读写磁盘次数d,达到提高外部排序速度的目的。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏python学习路

数据结构与算法(一)

算法的概念 算法是计算机处理信息的本质,因为计算机程序本质上是一个算法来告诉计算机确切的步骤来执行一个指定的任务。一般地,当算法在处理信息时,会从输入设备或数据...

44650
来自专栏老九学堂

初学C语言?先搞懂这些基础知识再谈深度学习吧!

编译程序: 如何把源程序转换成机器能够接受的目标程序,软件工作者编制了一系列的软件.通过这些软件,把用户按规定语法写出的语句一一翻译成二进制的机器指令. 这种具...

14820
来自专栏极客编程

nodejs之async异步编程

在回调函数中进行下一步操作的代码编写风格,常见的如setTimeout函数、ajax请求等等。

17320
来自专栏好好学java的技术栈

Java面试2018常考题目汇总

Linux起源于1991年,1995年流行起来的免费操作系统,目前, Linux是主流的服务器操作系统, 广泛应用于互联网、云计算、智能手机(Android)等...

13430
来自专栏章鱼的慢慢技术路

《算法图解》第二章笔记与课后练习_选择排序算法

17530
来自专栏韩伟的专栏

框架设计原则和规范(二)

此文是《.NET:框架设计原则、规范》的读书笔记,本文内容较多,共分九章,将分4天进行推送,今天推送4-5章。 1. 什么是好的框架 2. 框架设计...

31250
来自专栏CDA数据分析师

工具丨用C语言扩展Python的功能

一、简介 Python是一门功能强大的高级脚本语言,它的强大不仅表现在其自身的功能上,而且还表现在其良好的可扩展性上,正因如此,Python已经开始受到越来越多...

30590
来自专栏CRPER折腾记

ES6折腾记- 模板字符串

总体来说,模板字符串的出现了,让我们的字符串拼接写的更加优美了;相当简易实用;但是这货并不是万能的,有部分unicode编码字符会造成编译报错

12030
来自专栏xingoo, 一个梦想做发明家的程序员

第三章 C++中的C ----《C++编程思想》

1 创建函数 2 执行控制语句   break:退出循环,不再执行循环中的生育语句   continue:停止执行当前的循环,返回到循环的起始处开始新的一轮循环...

17770
来自专栏帅小子的日常

Javac的实现过程

36850

扫码关注云+社区

领取腾讯云代金券