数据结构第十一部分外部排序.ppt

数据结构 第十一章 外部排序,本章内容 11.1 外存信息的存取 11.2 外部排序的方法 11.3 多路平衡归并的实现 11.4 置换-选择排序 11.5 最佳归并树,11-3,11.1 外存信息的存取,常用的外存储器分类： 顺序存取的设备（如磁带）； 随机存取的设备（如磁盘）。 常用的外存储器是磁表面存储器, 信息记录在一薄层磁性材料的表面上, 这层材料附着于载体表面, 随着载体作高速旋转或直线运动, 在运动过程中用磁头进行读或写。 外存信息的存取特点, 决定了外部排序的策略选择。,11-4,11.1 外存信息的存取,磁带信息的存取 磁带存储器的工作原理和磁带录音机一样, 不同之处在于它存储的是数字信息而不是模拟信息。 磁带上的信息在横向分布、纵向分布以及首尾标志等都一定的格式。 以1/2英寸九道的磁带为例, 每一横排就可表示一个字符（8位+1个校验位）。 纵向按区进行存储, 区的长度不固定, 但有一个范围, 例如2到4096字节, 相邻区之间有一定长度的间隔（IBG, Inter Block Gap）, 作为磁带起停之用。,11-5,11.1 外存信息的存取,在磁带上读写一块信息所需的时间由两部分组成： TI/O = ta + n tw ta为延迟时间, 即读/写头到达传输信息所在物理快起始位置所需时间； tw为传输一个字符的时间。 显然, 延迟时间和信息在磁带上的位置、当前读/写头所在的位置有关。 所以磁带便宜、可反复使用、是一种顺序存取设备, 但查找费时、速度慢（尤其是查找末端记录时）。,11-6,11.1 外存信息的存取,磁盘信息的存取 磁盘是一种直接存取的存储设备(DASD）。 页块的读写时间：TI/O = tseek + tlatency + n twm tseek：寻道时间 tlatency：等待时间 twm：传输时间,11-7,11.2 外部排序的方法,外部排序基本上由两个相对独立的阶段组成： 首先, 按可用内存大小, 将外存上含n个记录的文件分成若干长度为l的子文件或段(segment), 依次读入内存并利用有效的内部排序方法对它们进行排序, 并将排序后得到的有序子文件重新写入外存, 通常称这些有序子文件为归并段或顺串(run)； 然后, 对这些归并段进行逐躺归并, 使归并段（有序的子文件）逐渐由小至大, 直到得到整个有序文件为止。,11-8,11.2 外部排序的方法,例：一文件含10000记录, 通过10次内部排序得到10个初始归并段R1R10, 其中每一段都含有1000个记录。 然后作两两归并： R1 R2 R3 R4 R5 R6 R7 R8 R9 R10 R1 R2 R3 R4 R5 R1 R2 R3 R1 R2 有序文件 由10个初始归并段到一个有序文件, 共进行了4趟归并, 每一趟都从m个归并段得到ceil(m/2)个归并段。这种归并方法称为2-路平衡归并。,11-9,11.2 外部排序的方法,外存上信息的读/写是以“物理块”为单位进行的, 假设每个物理块可以容纳200个记录, 则每一趟归并需进行50次“读”和50次“写”, 4趟归并加上内部排序时所需进行的读/写使得在外排序中总共需进行500次读/写。,11-10,11.2 外部排序的方法,外部排序所需总的时间 = 内部排序（产生初始归并段）所需的时间(m tIS) + 外存信息读写的时间(d tIO) +内部归并所需的时间(s utmg) 其中： tIS 是为得到一个初始归并段进行内部排序所需时间的均值； tIO 是进行一次外存读/写时间的均值； utmg 是对u个记录进行内部归并所需时间； m 为经过内部排序之后得到的初始归并段的个数； s 为归并的趟数； d 为总的读/写次数。 于是上例进行外排序所需总的时间为：10 tIS + 500 tIO + 4x10000 tmg 显然tIO较tmg要大的多, 因此提高外排序的效率应主要着眼于减少外存信息读写的次数d。,11-11,11.2 外部排序的方法,d和“归并过程”的关系： 若对上例进行5路平衡归并： R1 R2 R3 R4 R5 R6 R7 R8 R9 R10 R1 R2 有序文件 仅需两趟归并, 总的读/写次数便减少为：2x100+100=300, 比2路归并减少了200次的读/写。对同一文件, 进行外排序时所需读/写外存的次数和归并的趟数s成正比。一般情况下, 对m个初始归并段进行k路平衡归并时, 归并的趟数s=floor(logkm). 可见：若能增加k或减少m便能减少s, 因此减少d.,11-12,11.3 多路平衡归并的实现,对于2路归并, 令两个归并段上有u个记录, 每得到归并后的一个记录, 仅需一次比较即可, 因此得到含u个记录的归并段需进行u-1次比较。 对于k路归并, 令u个记录分布在k个归并段上, 显然, 归并后的第一个记录应是k个归并段中关键字最小的记录, 这需要进行k-1次比较, 得到u个记录的归并段, 共需(u-1)(k-1)次比较。由此, 对n个记录的文件进行外排序时, 在内部归并过程中进行的总的比较次数为s(k-1)(n-1)。假设所得初始归并段为m个, 则归并过程中进行比较的总的时间为： floor(logkm)(k-1)(n-1)tmg = floor(log2m/log2k)(k-1)(n-1)tmg 由于(k-1)/log2k 随 k 的增长而增长, 这将抵消由于增大k而减少外存信息读写时间所得效益。,11-13,11.3 多路平衡归并的实现,在进行k路归并时利用“败者树(Tree of Loser)”, 则可使在k个记录中选出关键字最小的记录时仅需进行floor(log2k)次比较, 从而使总的归并时间变为： floor(log2m)(n-1)tmg 与k无关, 不再随k的增长而增长。,11-14,11.3 多路平衡归并的实现,胜者树及其使用 胜者进入下一轮, 直至决出本次比赛的冠军。决出冠军之后, 充分利用上一次比赛的结果, 使得更快地挑出亚军、第三名 。,7,29,5,9,7,6,5,4,挑出冠军 需要进行 k-1 次比较, 此处需要比较 3 次。,9,5,5,3,2,0,5,1,11-15,11.3 多路平衡归并的实现,胜者树及其使用 胜者进入下一轮, 直至决出本次比赛的冠军。决出冠军之后, 充分利用上一次比赛的结果, 使得更快地挑出亚军、第三名 。,7,29,16,9,7,6,5,4,挑出亚军 需要进行 log2k 次比较, 此处需要比较 2次。,9,7,7,3,2,0,7,1,11-16,11.3 多路平衡归并的实现,胜者树及其使用 胜者进入下一轮, 直至决出本次比赛的冠军。决出冠军之后, 充分利用上一次比赛的结果, 使得更快地挑出亚军、第三名 。 决出第一名需比较： k - 1 次 决出第二名需比较： log2k 次 决出第三名需比较： log2k 次 结果：采用胜者树后, 从 k 个元素中挑选一个最小的元素仅需 log2k 次比较, 这时总的比较次数下降为： logkm log2k ( n - 1 ) tmg log2m ( n - 1 ) tmg 该结果和 k 无关, 这是通过多用空间换来的。 改进：采用胜者树, k个元素中最小的元素输出之后, 从根结点到它的相应的叶子结点路径上的结点都需要进行修改, 为了加快程序运行的速度产生了败者树。,11-17,11.3 多路平衡归并的实现,败者树 在父节点中记下刚进行完的比赛中的败者, 但同样让胜者去参加下一轮的竞赛, 便得到一棵“败者树”。,11-18,11.3 多路平衡归并的实现,下图即为一棵实现5-路归并的败者树ls04, 图中方形结点表示叶子结点(也可看成是外结点), 分别为5个归并段中当前参加归并的待选择记录的关键码；败者树中根结点ls1的双亲结点ls0为“冠军”, 在此指示各归并段中的最小关键码记录为第三段中的记录；结点ls3指示b1和b2两个叶子结点中的败者即是b2, 而胜者b1和b3(b3是叶子结点b3、b4和b0经过两场比赛后选出的获胜者)进行比较, 结点ls1则指示它们中的败者为b1。,11-19,11.3 多路平衡归并的实现,5-路归并的败者树例,9,20,ls0,ls1,ls3,ls2,ls4,b0,b1,b2,b4,b3,6 15 25,12 37 48,10 15 15,9 18 20,20 22 40,2,1,3,0,6,12,10,4,11-20,11.3 多路平衡归并的实现,在选得最小关键码的记录之后, 只要修改叶子结点b3中的值, 使其为同一归并段中的下一个记录的关键码, 然后从该结点向上和双亲结点所指的关键码进行比较, 败者留在该双亲, 胜者继续向上直至树根的双亲。如下图所示。当第3个归并段中第2个记录参加归并时, 选得最小关键码记录为第一个归并段中的记录。为了防止在归并过程中某个归并段变为空, 可以在每个归并段中附加一个关键码为最大的记录。当选出的“冠军”记录的关键码为最大值时, 表明此次归并已完成。,11-21,11.3 多路平衡归并的实现,5-路归并的败者树例,9,20,ls0,ls1,ls3,ls2,ls4,b0,b1,b2,b4,b3,15 25,12 37 48,10 15 15,9 18 20,20 22 40,2,0,1,4,15,12,10,3,11-22,11.3 多路平衡归并的实现,实现k-路归并的败者树的初始化也容易实现, 只要先令所有的非终端结点指向一个含最小关键码的叶子结点, 然后从各叶子结点出发调整非终端结点为新的败者即可。 下面程序中简单描述了利用败者树进行k-路归并的过程, 为了突出如何利用败者树进行归并, 避开了外存信息存取的细节, 可以认为归并段已存在。,typedef int LoserTreek; /败者树是完全二叉树且不含叶子, 可采用顺序存储结构 typedef struct KeyType key; ExNode, Externalk; /外结点, 只存放待归并记录的关键码,11-23,11.3 多路平衡归并的实现,void K_Merge(LoserTree *ls, External *b) /k-路归并处理程序利用败者树ls将编号从0到k-1的k个输入归并段中的记录归并到输出归并段b0 /到bk-1为败者树上的k个叶子结点, 分别存放k个输入归并段中当前记录的关键码 for(i=0;ik;i+) input(bi.key); /分别从k个输入归并段读入该段当前第一个记录的关键码到外结点 CreateLoserTree(ls); /建败者树ls, 选得最小关键码为b0.key while(bls0.key!=MAXKEY) q=ls0; /q指示当前最小关键码所在归并段 output(q); /将编号为q的归并段中当前(关键码为bq.key的记录写至输出归并段) input(bq.key); /从编号为q的输入归并段中读入下一个记录的关键码 Adjust(ls, q); /调整败者树, 选择新的最小关键码 output(ls0); /将含最大关键码MAXKEY的记录写至输出归并段 ,11-24,11.3 多路平衡归并的实现,void Adjust(LoserTree *ls, int s) /选得最小关键码记录后, 从叶到根调整败者树, /选下一个最小关键码, 从叶子结点bs到根结 /点ls0的路径调整败者树 t=(s+k)/2; /lst是bs的双亲结点 while(t0) if(bs.keyblst.key) slst; /s指示新的胜者 t=t/2; ls0=s; ,void CreateLoserTree(LoserTree *ls) /建立败者树 /已知b0到bk-1为完全二叉树ls的叶子结点存有k个关 /键码,沿从叶子到根的k条路径将ls调整为败者树 bk.key=MINKEY; /设MINKEY为关键码可能的最小值 for(i=0;i0;i-) Adjust(ls, i); /依次从bk-1, bk-2, , b0出发调整败者 ,最后要提及一点, k值的选择并非越大越好, 如何选择合适的k是一个 需要综合考虑的问题。,11-25,11.4 置换-选择排序,归并的趟数不仅和k成反比, 也和m成正比, 因此减少m是减少s的另一条途径。这里m是外部文件经过内部排序之后得到的初始归并段的个数, m=ceil(n/l)。 若要减少m, 就需要增加l, 但是内存的容量有限, 利用上一章内排序的方法无法做到, 所以必须探索新的排序方法。 置换-选择排序(Replacement-Selection Sorting)是在树形选择排序的基础上得来的, 它的特点是：在整个排序（得到所有初始归并段）的过程中, 选择最小（或最大）关键字和输入、输出交叉或平行进行。,11-26,11.4 置换-选择排序,假设初始待排文件为输入文件FI, 初始归并段文件为输出文件FO, 内存工作区为WA, FO和WA的初始状态为空, 并设内存工作区WA的容量为w个记录, 则置换-选择排序的操作过程为： 从FI输入w个记录到工作区WA; 从WA中选出其中关键字最小值的记录, 记为MINIMAX记录； 将MINIMAX记录输出到FO中去； 若FI不空, 则从FI输入下一个记录到WA中； 从WA中所有关键字比MINIMAX记录的关键字大的记录中选出最小关键字记录, 作为新的MINIMAX记录； 重复3-5, 直至在WA中选不出新的MINIMAX记录为止, 由此得到一个初始归并段, 输出一个归并段的结束标志到FO中去； 重复2-6, 直至WA为空, 由此得到全部初始归并段。,11-27,11.4 置换-选择排序,例如：初始文件含24个记录, 关键字分别为： 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个记录，则用内排序的方法可以得到4个初始段： RUN1: 29, 38, 39, 46, 49, 51 RUN2: 1, 14, 15, 30, 48, 61 RUN3: 3, 4, 13, 27, 52, 63 RUN3: 24, 33, 46, 58, 76, 89 而用置换-选择排序，则可求得如下3个初始归并段： RUN1: 29, 38, 39, 46, 49, 51, 61 RUN2: 1, 3, 14, 15, 27, 30, 48, 52, 63, 89 RUN3: 4, 13, 24, 33, 46, 58, 76,11-28,11.4 置换-选择排序,置换-选择排序的过程 (见教材第300页)：,11-29,11.4 置换-选择排序,在WA中选择MINIMAX记录的过程需利用“败者树”来实现。 内存工作区中的记录作为败者树的外部节点，而败者树的根节点的父节点指示工作区中关键字最小的纪录； 为了便于选出MINIMAX记录，为每一个记录附设一个所在归并段的序号，在进行关键字的比较时，现比较段号，段号小的为胜者，段号相同的则关键字小的为胜者； 败者树的建立可从设工作区中所有记录的段号均为“0”开始，然后从FI逐个输入w个记录到工作区是，自下而上调整败者树，由于这些记录的段号为“1”，则他们对于“0”段的记录而言均为败者，从而逐个填充到败者树的各节点中去。,11-30,11.4 置换-选择排序,可以证明, 利用置换-选择排序，初始归并段的平均长度可达内存允许尺寸w的二倍。,最小值 最大值,值递增,