ciaoly
外部排序

access_time
brush 1086个字
whatshot 34 ℃

外部排序

外部排序指的是大文件的排序,即待排序的记录存储在外存储器上,待排序的文件无法一次装入内存,需要在内存和外部存储器之间进行多次数据交换,以达到排序整个文件的目的。

外部排序的基本思路

  1. 把外存上含有n个记录的文件分成若干个长度为L的子文件,把这些子文件依次读入内存,并利用有效的内部排序方法对它们进行排序,再将排序后得到的有序子文件重新写入外存;
  2. 对这些有序子文件逐趟归并,使其逐渐由小到大,直至得到整个有序文件为止。

明确概念: 称排序后的 “有序子文件”为“归并段” ,称每次归并时参与归并的“归并段”的数量为“路数”

由第二步“归并”操作可以看出,归并时构成了一棵以各归并段为根节点、以归并路数为度的“归并树”

效率优化

效率计算 首先,外部排序的总时间一般为:

t_{ES} = r \times t_{RS} + d \times t_{IO} +S \times (n-1) \times t_{mg}

式中,n 为每次参加归并的记录的个数,t_{MG} 是每做一次内部归并是查找最值的时间。

当然上式完全是个唬人的玩意,常理来说,做一只外部排序的耗时大头主要是I/O操作。 因此,计算一次外部排序的时间,主要是计算做I/O操作的次数。 假设外部I/O设备是硬盘,硬盘的读写是以块为单位,因此分析读写次数主要是分析总体加载和写入块的次数。 可以看出,读写总次数为分段时读写次数 + 归并时读写次数。其中,分段时要求读写所有数据一次,这是不可避免的;归并时每轮归并要求读写所有数据一次(即归并树中每一层都要读写所有数据一次)。因此,若要减少总读写次数,只能减少归并树的层次。

归并数的层次(高度)为:

h = \log_k(m)

式中,k 为归并的路数,m 为归并段数

优化归并路数

归并时,每次要从各段中选择出一个最值进行写出,查找这个“最值”的时间随着数据规模的上升而上升;而每次查找该“最值”的“数据规模”即为“归并路数”(因为要从每一路中加载一个数参与比较),因此归并路数上升会导致内部排序变慢。 S 轮归并总共需要的比较次数为:(注意选择题会考)

S= (n-1) \times (k-1) = \lceil\log_km\rceil\times (n-1) \times (k-1) = \frac{\lceil\log_2m\rceil \times (n-1) \times (k-1) }{\lceil \log_2k\rceil}

到这里,设法使查找操作不随问题规模增加而显著增加。

使用“败者树”(借鉴“堆排序”)

内存中持续维护一棵“败者树”,使每次新数据进入时都能借助上次排序的结果 ,从而减少查找时间,这便是“堆排序”的思路。 堆排序的最坏时间复杂度为log_2k 因此,总比较次数便为:

S= (n-1) \times \lceil\log_2k\rceil = \lceil\log_km\rceil\times (n-1) \times \lceil\log_2k\rceil = (n-1)\times \lceil\log_2k\rceil

优化归并段数

既然归并操作时能够摆脱内存大小的限制,将超过内存的数据合并排序,那么在分段时也可尝试超过内存个数的分段。

置换-选择排序

// TODO

解决参差不齐的分段问题:最佳归并树

上文示,归并操作时构成了一棵“归并树”。记录数最多(最长)的段,归并时其I/O操作也即越多,因此应将其较晚归并,这可以用“霍夫曼树”解决。

在构造霍夫曼树时有一个问题,若段的数目不足以构成一棵“严格 k 叉树”(k 为归并路数),则应添加权值为0的“虚段”。由于权值为0,“虚段”永远在离根最远的层。

添加“虚段”的方法 设度为0的节点(叶子节点)有 n_0 个,度为 k 的节点(中间节点)有 n_k 个,则对于“严格 k 叉树”有 n_0 = (k-1)n_k + 1 ,则 n_k = (n_0-1)/ (k-1),有:

  • (n_0-1) % (k-1) ==0 : 恰好构成严格 k 叉树,无需添加虚节点
  • (n_0-1) % (k-1) == u != 0 : 有 u 个节点多余,则添加 m-u-1 个“虚结点”。(解释:可添加一个中间节点来“收留”此 u 个节点,由于此中间节点的添加也占用了一个原有的“叶子节点位“,因此应该补加 m-(u+1) = m-u-1 个“虚结点”)

https://www.sohu.com/a/258751244_81869251244_8186929251244_81869286924_8186928692_8186928692

#如无特别声明,该文章均为 ciaoly 原创,转载请遵循 署名-非商业性使用 4.0 国际(CC BY-NC 4.0) 协议,即转载请注明文章来源。
#最后编辑时间为: 2019 年 10 月 12 日


create 添加新评论


account_circle
email
language
textsms





关于 DreamCat

主题名称:DreamCat | 版本:X2.6.220211

主题开发:HanFengA7 | TeddyNight | Dev-Leo | CornWorld | WhiteBearcn | DFFZMXJ

Designed by HanFengA7 Power by Typecho

Copyright © 2015-2022 by LychApe All rights reserved!

加我的QQ
加我的微博
加我的支付宝
加我的微信