外存信息的存取外部排序的方法多路平衡归并的实.ppt

1、外存信息的存取 2、外部排序的方法 3、多路平衡归并的实现 4、置换-选择排序 5、最佳归并树,第 11 章 外部排序,1、外存信息的存取,1、外部排序： 待排序的记录数量巨大，无法一次调入内存，只能驻留在外存上（磁带、磁盘、CD-ROM）上。不能使用内部排序的方法进行排序。否则将引起频繁访问外存。 外部排序主要的时间开销用在信息的内、外存交换上，所以减少 I/O 时间成为要解决的主要问题。,2、常用外存：,磁带：由磁带介质、读、写磁头、驱动器、接收盘和原始盘组成。便宜、可反复使用、是一种顺序存取设备。查找费时、速度慢（尤其是查找末端记录时）,1、外存信息的存取,磁带信息的表示：,1、外存信息的存取,磁带文件的组织：,记录 1,记录 3,记录 2,IRG（Inter Record Gap）记录间隙,IRG：0.50.75 inch，带来的问题是什么？ 磁带的利用率下降。 例如： 密度 1600 byte per inch 的带。设每个记录有 80 byte ，如果 IRG 0.75 inch ; 带的利用率？,读写头,记录所用：(80/1600) 0.005 inch IRG所用： 0.75 inch 利用率 0.005/(1+0.75)= 1/16 必须改进磁带的利用率 !,1、外存信息的存取,磁带文件的组织的改进：,块 1,块 3,块 2,IBG（Inter Block Gap）块间间隙,IBG：.5.75 inch，带来的好处是磁带的利用率上升,如上例：设 每一块包含20个记录 每一块所占 20 80/1600 1 inch 利用率 1/1+0.75 = 57%,磁带文件的读写时间：T i/o = ta + ntw ta 延迟时间：读写头到达相应的物理块的起始位置的时间。 tw 读/写一个字符的时间； n 字符数。,由于磁带是顺序存取设备，在读一个记录时，必须先顺序检索，直到所需信息通过读写头时才能得到。因此检索速度很慢。 磁带主要用于存储顺序存取的大量数据。,1、外存信息的存取,1、外存信息的存取,2）磁盘：,结构：由磁盘驱动器、读、写磁头、活动臂、盘片（磁道、扇区）、旋转主轴构成。速度快、容量大、直接存取设备。,柱面：各盘面的直径相同的磁道的总和。,物理位置：柱面号、磁道号、块（扇区号）,盘文件的读写时间：T i/o = tseck + tla + ntwm tseck (0.1秒) ：找道时间； tla (25豪秒) ：等待时间twm (105个字符/秒)：传输时间/ 字符，n 字符数。,种类：固定头磁盘、活动头磁盘 固定头磁盘：每个磁道都有一个磁头（速度快） 活动头磁盘：每个盘面共用一个磁头，增加了找道的时间，应用广泛。,2）磁盘：,外部排序的基本过程,11.2 外部排序的方法,按可用内存大小,利用内部排序方法，构造若干个记录的有序子序列写入外存，通常称这些记录的有序子序列为 “归并段”;,由相对独立的两个步骤组成：,通过“归并”，逐步扩大(记录的)有序子序列的长度，直至外存中整个记录序列按关键字有序为止。,例如：假设有一个含10,000个记录的磁盘文件，而当前所用的计算机一次只能对1,000个记录进行内部排序，则首先利用内部排序的方法得到10个初始归并段，然后进行逐趟归并。,假设进行2路归并(即两两归并)，则第一趟由10个归并段得到5个归并段;,最后一趟归并得到整个记录的有序序列。,第三趟由 3 个归并段得到2个归并段;,第二趟由 5 个归并段得到3个归并段;,11.2 外部排序的方法,假设“数据块”的大小为200，即每一次访问外存可以读/写200个记录。 则对于10,000个记录，处理一遍需访问外存100次(读和写各50次)。,分析上述外排过程中访问外存(对外存进行读/写)的次数：,1)求得10个初始归并段需访问外存100次; 2)每进行一趟归并需访问外存100次; 3)总计访问外存 100 + 4 100 = 500次,11.2 外部排序的方法,外排总的时间还应包括内部排序所需时间和逐趟归并时进行内部归并的时间,11.2 外部排序的方法,tIO值取决于外存，远远大于tIS和tmg。 外部排序的时间取决于读写外存的次数d。,外部排序总时间=产生初始归并段的时间 m*tIS +外存信息读写时间 d*tIO +内部归并所需时间 s*utmg,例如:若对上述例子采用2路归并,则只需进行4趟归并， 外排所需总的时间： 10*tIS+500*tIO+4*1000*tmg,若对上述例子采用5路归并,则只需进行2趟归并，总的访问外存的次数为100+2100=300次,11.2 外部排序的方法,一般情况下，假设待排记录序列含 m 个初始归并段，外排时采用 k路归并，则归并趟数s=logkm，显然，随着k的增大或m的减小，归并的趟数将减少，因此对外排而言，通常采用多路归并。k 的大小可选，但需综合考虑各种因素。,11.3 多路平衡归并的实现,分析: m 个初始归并段，外排时采用 k路归并，则归并趟数为 logkm , K 大，趟数减少，读写记录的总数将减少。但 K 大，会使内部归并时间tmg增大?。,一、多路平衡归并的性质：,改进：采用胜者树或者败者树，从 K 个元素中挑选一个最小的元素仅需 log2k 次比较，这时总的时间耗费将下降为： log2m ( n - 1 ) tmg,11.3 多路平衡归并的实现,11.3 多路平衡归并的实现,二、胜者树及其使用,1,9,5,7,29,5,9,5,7,6,5,4,3,2,输 入 缓 冲 区,5 16 49 52 78,7 12 25 84 91,29 38 57 66 71,9 22 47 48 59,输 出 缓 冲 区,5,4路平衡归并,9,7,11.3 多路平衡归并的实现,7,29,16,9,7,5 16 49 52 78,7 12 25 84 91,29 38 57 66 71,9 22 47 48 59,7,6,5,4,3,2,1,输 入 缓 冲 区,输 出 缓 冲 区,7,7,9,16,7,29,9,7,6,5,4,3,2,1,5 7,二、胜者树及其使用,4路平衡归并,9,12,11.3 多路平衡归并的实现,12,29,16,9,9,5 16 49 52 78,7 12 25 84 91,29 38 57 66 71,9 22 47 48 59,7,6,5,4,3,2,1,输 入 缓 冲 区,输 出 缓 冲 区,9,12,9,16,12,29,9,7,6,5,4,3,2,1,5 7 9,4路平衡归并,二、胜者树及其使用,11.3 多路平衡归并的实现,改进：采用胜者树，从K个元素中选取最小元素之后，从根结点到它的相应的叶子结点路径上的结点都需要进行修改，为了加快程序运行的速度产生了败者树。,采用胜者树，从 K 个元素中挑选一个最小的元素仅需 log2m ( n - 1 ) tmg 即内部归并时间与k无关, K 增大，归并趟数logkm减少，读写外存次数减少，外排总时间减少。,2,1,11.3 多路平衡归并的实现,三、败者树及其使用,7,29,5,9,3,5 16 49 52 78,7 12 25 84 91,29 38 57 66 71,9 22 47 48 59,b0,ls1,输 入 缓 冲 区,输 出 缓 冲 区,9,7,29,5,7,29,9,7,6,5,4,3,2,1,5,注意：挑出冠军 需要进行 k-1 次 比较，此处需要 比较 3 次。,0,ls 0,0,5,ls2,ls3,b1,b2,b3,4路平衡归并,2,0,11.3 多路平衡归并的实现,三、败者树及其使用,7,29,16,9,3,5 16 49 52 78,7 12 25 84 91,29 38 57 66 71,9 22 47 48 59,b0,ls1,输 入 缓 冲 区,输 出 缓 冲 区,9,7,29,5,7,29,9,7,6,5,4,3,2,1,5 7,注意：挑出冠军 需要进行 k-1 次 比较，此处需要 比较 3 次。,1,ls 0,0,5,ls2,ls3,b1,b2,b3,4路平衡归并,2,0,11.3 多路平衡归并的实现,三、败者树及其使用,12,29,16,9,1,5 16 49 52 78,7 12 25 84 91,29 38 57 66 71,9 22 47 48 59,b0,ls1,输 入 缓 冲 区,输 出 缓 冲 区,9,7,29,5,7,29,9,7,6,5,4,3,2,1,5 7 9 ,注意：挑出冠军 需要进行 k-1 次 比较，此处需要 比较 3 次。,3,ls 0,0,5,ls2,ls3,b1,b2,b3,4路平衡归并,typedef int LoserTreek; typedef struct KeyType key; Exnode, Externalk+1;,Void K_Merge ( LoserTree / K_Merge,四、利用败者树进行k-路归并算法的描述:,void Adjust ( LoserTree / Adjust,四、调整败者树的算法描述如下:,void CreateLoserTree ( LoserTree /依次从bk-1,bk-2,b0出发调整败者. / CreateLoserTree,四、建立败者树的算法描述如下:,11.4 置换-选择排序,一、问题的提出 m个初始归并段做k路平衡归并排序时归并的趟数为logkm.为了减少归并趟数，也可以减小m的值。如何减小初始归并段的个数（也就是增加归并段的长度）?,解决：在内存长度一定时，假设容纳M条记录，按照通常的 排序方法，初始归并段的长度可以是M,一种更好的方法是使用置换选择(replace selection)算法，平均情况下可以产生可以生成两倍内存长度的初始归并段。,4、置换-选择排序,2.置换选择排序 置换选择排序是堆排序的变体。,输入文件FI,内存工作区WA,输出文件Fo,内存工作区可容纳w个记录,输出缓冲,输入缓冲,(1) 从FI输入W个记录到WA； (2) 从WA中选择关键字最小的记录，记为MINIMAX (3) 将MINIMAX输出到FO中； (4)若FI不空，从FI输入下一个记录到WA； (5)从WA中所有关键字比MINIMAX的关键字大的记录中选出最小关键字记录，作为新的MINIMAX记录。 (6)重复（3）-（5）直至WA中选不出新的MINIMAX。到此得到一个初始归并段 （7）重复（2）-（6），直至WA为空。,置换选择排序的操作过程：,实例：输入文件FI中记录关键字为：51、49、39、46、38、29、14、61、15、30、1、48、52、3、63、27、4、13、89、24、46、58、33、76，假定使用的内存可容纳 6 个记录，利用置换-选择分类法产生初始合并段。,51 49 39 46 38 29 14 61 15 30 1 48 52 3 63 27 4 13 89 24 46 58 33 76,FI,51 49 39 46 38 29,WA,FO,实例：输入文件FI中记录关键字为：51、49、39、46、38、29、14、61、15、30、1、48、52、3、63、27、4、13、89、24、46、58、33、76，假定使用的内存可容纳 6 个记录，利用置换-选择分类法产生初始合并段。,51 49 39 46 38 29 14 61 15 30 1 48 52 3 63 27 4 13 89 24 46 58 33 76,FI,51 49 39 46 38 14,WA,29,FO,实例：输入文件FI中记录关键字为：51、49、39、46、38、29、14、61、15、30、1、48、52、3、63、27、4、13、89、24、46、58、33、76，假定使用的内存可容纳 6 个记录，利用置换-选择分类法产生初始合并段。,51 49 39 46 38 29 14 61 15 30 1 48 52 3 63 27 4 13 89 24 46 58 33 76,FI,51 49 46 39 14 61,WA,29 38,FO,实例：输入文件FI中记录关键字为：51、49、39、46、38、29、14、61、15、30、1、48、52、3、63、27、4、13、89、24、46、58、33、76，假定使用的内存可容纳 6 个记录，利用置换-选择分类法产生初始合并段。,51 49 39 46 38 29 14 61 15 30 1 48 52 3 63 27 4 13 89 24 46 58 33 76,FI,51 49 46 14 61 15,WA,29 38 39,FO,实例：输入文件FI中记录关键字为：51、49、39、46、38、29、14、61、15、30、1、48、52、3、63、27、4、13、89、24、46、58、33、76，假定使用的内存可容纳 6 个记录，利用置换-选择分类法产生初始合并段。,51 49 39 46 38 29 14 61 15 30 1 48 52 3 63 27 4 13 89 24 46 58 33 76,FI,51 49 14 61 15 30,WA,29 38 39 46,FO,实例：输入文件FI中记录关键字为：51、49、39、46、38、29、14、61、15、30、1、48、52、3、63、27、4、13、89、24、46、58、33、76，假定使用的内存可容纳 6 个记录，利用置换-选择分类法产生初始合并段。,51 49 39 46 38 29 14 61 15 30 1 48 52 3 63 27 4 13 89 24 46 58 33 76,FI,51 14 61 15 30 1,WA,29 38 39 46 49,FO,实例：输入文件FI中记录关键字为：51、49、39、46、38、29、14、61、15、30、1、48、52、3、63、27、4、13、89、24、46、58、33、76，假定使用的内存可容纳 6 个记录，利用置换-选择分类法产生初始合并段。,51 49 39 46 38 29 14 61 15 30 1 48 52 3 63 27 4 13 89 24 46 58 33 76,FI,14 61 15 30 1 48,WA,29 38 39 46 49 51 #,FO,实例：输入文件FI中记录关键字为：51、49、39、46、38、29、14、61、15、30、1、48、52、3、63、27、4、13、89、24、46、58、33、76，假定使用的内存可容纳 6 个记录，利用置换-选择分类法产生初始合并段。,51 49 39 46 38 29 14 61 15 30 1 48 52 3 63 27 4 13 89 24 46 58 33 76,FI,14 15 30 1 48 52,WA,29 38 39 46 49 51 61,FO,实例：输入文件FI中记录关键字为：51、49、39、46、38、29、14、61、15、30、1、48、52、3、63、27、4、13、89、24、46、58、33、76，假定使用的内存可容纳 6 个记录，利用置换-选择分类法产生初始合并段。,51 49 39 46 38 29 14 61 15 30 1 48 52 3 63 27 4 13 89 24 46 58 33 76,FI,14 15 30 1 48 52,WA,29 38 39 46 49 51 61#,FO,实例：输入文件FI中记录关键字为：51、49、39、46、38、29、14、61、15、30、1、48、52、3、63、27、4、13、89、24、46、58、33、76，假定使用的内存可容纳 6 个记录，利用置换-选择分类法产生初始合并段。,51 49 39 46 38 29 14 61 15 30 1 48 52 3 63 27 4 13 89 24 46 58 33 76,FI,14 15 30 48 52 3,WA,29 38 39 46 49 51 61 # 1,FO,实例：输入文件FI中记录关键字为：51、49、39、46、38、29、14、61、15、30、1、48、52、3、63、27、4、13、89、24、46、58、33、76，假定使用的内存可容纳 6 个记录，利用置换-选择分类法产生初始合并段。,51 49 39 46 38 29 14 61 15 30 1 48 52 3 63 27 4 13 89 24 46 58 33 76,FI,14 15 30 48 52 63,WA,29 38 39 46 49 51 61 # 1 3,FO,实例：输入文件FI中记录关键字为：51、49、39、46、38、29、14、61、15、30、1、48、52、3、63、27、4、13、89、24、46、58、33、76，假定使用的内存可容纳 6 个记录，利用置换-选择分类法产生初始合并段。,51 49 39 46 38 29 14 61 15 30 1 48 52 3 63 27 4 13 89 24 46 58 33 76,FI,15 30 48 52 63 27,WA,29 38 39 46 49 51 61 # 1 3 14,FO,实例：输入文件FI中记录关键字为：51、49、39、46、38、29、14、61、15、30、1、48、52、3、63、27、4、13、89、24、46、58、33、76，假定使用的内存可容纳 6 个记录，利用置换-选择分类法产生初始合并段。,51 49 39 46 38 29 14 61 15 30 1 48 52 3 63 27 4 13 89 24 46 58 33 76,FI,15 30 48 52 63 27,WA,29 38 39 46 49 51 61 # 1 3 14,FO,实例：输入文件FI中记录关键字为：51、49、39、46、38、29、14、61、15、30、1、48、52、3、63、27、4、13、89、24、46、58、33、76，假定使用的内存可容纳 6 个记录，利用置换-选择分类法产生初始合并段。,51 49 39 46 38 29 14 61 15 30 1 48 52 3 63 27 4 13 89 24 46 58 33 76,FI,30 48 52 63 27 4,WA,29 38 39 46 49 51 61 # 1 3 14 15,FO,实例：输入文件FI中记录关键字为：51、49、39、46、38、29、14、61、15、30、1、48、52、3、63、27、4、13、89、24、46、58、33、76，假定使用的内存可容纳 6 个记录，利用置换-选择分类法产生初始合并段。,51 49 39 46 38 29 14 61 15 30 1 48 52 3 63 27 4 13 89 24 46 58 33 76,FI,30 48 52 63 4 13,WA,29 38 39 46 49 51 61 # 1 3 14 15 27,FO,实例：输入文件FI中记录关键字为：51、49、39、46、38、29、14、61、15、30、1、48、52、3、63、27、4、13、89、24、46、58、33、76，假定使用的内存可容纳 6 个记录，利用置换-选择分类法产生初始合并段。,51 49 39 46 38 29 14 61 15 30 1 48 52 3 63 27 4 13 89 24 46 58 33 76,FI,48 52 63 4 13 89,WA,29 38 39 46 49 51 61 # 1 3 14 15 27 30,FO,实例：输入文件FI中记录关键字为：51、49、39、46、38、29、14、61、15、30、1、48、52、3、63、27、4、13、89、24、46、58、33、76，假定使用的内存可容纳 6 个记录，利用置换-选择分类法产生初始合并段。,51 49 39 46 38 29 14 61 15 30 1 48 52 3 63 27 4 13 89 24 46 58 33 76,FI,52 63 4 13 89 24,WA,29 38 39 46 49 51 61 # 1 3 14 15 27 30 48,FO,实例：输入文件FI中记录关键字为：51、49、39、46、38、29、14、61、15、30、1、48、52、3、63、27、4、13、89、24、46、58、33、76，假定使用的内存可容纳 6 个记录，利用置换-选择分类法产生初始合并段。,51 49 39 46 38 29 14 61 15 30 1 48 52 3 63 27 4 13 89 24 46 58 33 76,FI,63 4 13 89 24 46,WA,29 38 39 46 49 51 61 # 1 3 14 15 27 30 48 52,FO,实例：输入文件FI中记录关键字为：51、49、39、46、38、29、14、61、15、30、1、48、52、3、63、27、4、13、89、24、46、58、33、76，假定使用的内存可容纳 6 个记录，利用置换-选择分类法产生初始合并段。,51 49 39 46 38 29 14 61 15 30 1 48 52 3 63 27 4 13 89 24 46 58 33 76,FI,4 13 89 24 46 58,WA,29 38 39 46 49 51 61 # 1 3 14 15 27 30 48 52 63,FO,实例：输入文件FI中记录关键字为：51、49、39、46、38、29、14、61、15、30、1、48、52、3、63、27、4、13、89、24、46、58、33、76，假定使用的内存可容纳 6 个记录，利用置换-选择分类法产生初始合并段。,51 49 39 46 38 29 14 61 15 30 1 48 52 3 63 27 4 13 89 24 46 58 33 76,FI,4 13 24 46 58 33,WA,29 38 39 46 49 51 61 # 1 3 14 15 27 30 48 52 63 89#,FO,实例：输入文件FI中记录关键字为：51、49、39、46、38、29、14、61、15、30、1、48、52、3、63、27、4、13、89、24、46、58、33、76，假定使用的内存可容纳 6 个记录，利用置换-选择分类法产生初始合并段。,51 49 39 46 38 29 14 61 15 30 1 48 52 3 63 27 4 13 89 24 46 58 33 76,FI,13 24 46 58 33 76,WA,29 38 39 46 49 51 61 # 1 3 14 15 27 30 48 52 63 89# 4,FO,实例：输入文件FI中记录关键字为：51、49、39、46、38、29、14、61、15、30、1、48、52、3、63、27、4、13、89、24、46、58、33、76，假定使用的内存可容纳 6 个记录，利用置换-选择分类法产生初始合并段。,51 49 39 46 38 29 14 61 15 30 1 48 52 3 63 27 4 13 89 24 46 58 33 76,FI,24 46 58 33 76,WA,29 38 39 46 49 51 61 # 1 3 14 15 27 30 48 52 63 89# 4 13,FO,实例：输入文件FI中记录关键字为：51、49、39、46、38、29、14、61、15、30、1、48、52、3、63、27、4、13、89、24、46、58、33、76，假定使用的内存可容纳 6 个记录，利用置换-选择分类法产生初始合并段。,51 49 39 46 38 29 14 61 15 30 1 48 52 3 63 27 4 13 89 24 46 58 33 76,FI,46 58 33 76,WA,29 38 39 46 49 51 61 # 1 3 14 15 27 30 48 52 63 89# 4 13 24,FO,实例：输入文件FI中记录关键字为：51、49、39、46、38、29、14、61、15、30、1、48、52、3、63、27、4、13、89、24、46、58、33、76，假定使用的内存可容纳 6 个记录，利用置换-选择分类法产生初始合并段。,51 49 39 46 38 29 14 61 15 30 1 48 52 3 63 27 4 13 89 24 46 58 33 76,FI,46 58 76,WA,29 38 39 46 49 51 61 # 1 3 14 15 27 30 48 52 63 89# 4 13 24 33,FO,实例：输入文件FI中记录关键字为：51、49、39、46、38、29、14、61、15、30、1、48、52、3、63、27、4、13、89、24、46、58、33、76，假定使用的内存可容纳 6 个记录，利用置换-选择分类法产生初始合并段。,51 49 39 46 38 29 14 61 15 30 1 48 52 3 63 27 4 13 89 24 46 58 33 76,FI,58 76,WA,29 38 39 46 49 51 61 # 1 3 14 15 27 30 48 52 63 89# 4 13 24 33 46,FO,实例：输入文件FI中记录关键字为：51、49、39、46、38、29、14、61、15、30、1、48、52、3、63、27、4、13、89、24、46、58、33、76，假定使用的内存可容纳 6 个记录，利用置换-选择分类法产生初始合并段。,51 49 39 46 38 29 14 61 15 30 1 48 52 3 63 27 4 13 89 24 46 58 33 76,FI,76,WA,29 38 39 46 49 51 61 # 1 3 14 15 27 30 48 52 63 89# 4 13 24 33 46 58,FO,实例：输入文件FI中记录关键字为：51、49、39、46、38、29、14、61、15、30、1、48、52、3、63、27、4、13、89、24、46、58、33、76，假定使用的内存可容纳 6 个记录，利用置换-选择分类法产生初始合并段。,51 49 39 46 38 29 14 61 15 30 1 48 52 3 63 27 4 13 89 24 46 58 33 76,FI,WA,29 38 39 46 49 51 61 # 1 3 14 15 27 30 48 52 63 89# 4 13 24 33 46 58 76 #,FO,4、置换-选择排序,3、长度分析： 设内存可以存放 m 个记录，则首先从文件读入 m 记录到内存。这 m 个记录肯定可以归入本初始合并段内。这样，必须从文件中读入 m 个记录。这 m 个记录中平均有一半可以归入本合并段，一半归入下一合并段。 因此，合并段的平均长度为： m + m/2 + m/4 + = 2m 所以，在平均情况下，合并段的平均长度为 2m 。 该结论由：EFMoore 在 1961 年从置换选择排序同扫雪机的类比中得到的。,1)存储结构定义 可以用败者树的办法 加以实现。,typedef struct RcdType rec; /记录 KeyType key; /关键字 int rnum; /所属归并段的段号 RcdNode,WorkAreaw;,4、实现：,2)模块结构图,Replace_selection,Get_run,置换-选择算法,得到一个初始归并段,Construct_Loser,Select_MiniMax,选择每个段中最小值,void Replace_Selection(LoserTree /Replace_Selection,3)模块实现,void get_run(LoserTree /while /get_run,void Select_MiniMax(LoserTree ,void Construct_Loser(LoserTree /end for /Construct_Loser,3,2,1,4,4、置换-选择排序,5、败者树实现置换-选择排序,5,2,29,0,1,0,51、49、39、46、38、29、14、61、15,46 1,39 1,49 1,51 1,29 1,38 1,5,4,3,3,2,0,4,4、置换-选择排序,5、败者树实现置换-选择排序,5,2,29 38,0,1,1,51、49、39、46、38、29、14、61、15,46 1,39 1,49 1,51 1,14 2,38 1,5,