物料管理7

1物料管理EXST1AlgorithmsandDataStructures:EXSORT1、外存信息的存取2、外部排序的方法3、多路平衡归并的实现4、置换-选择排序5、最佳归并树目录第11章外部排序2物料管理EXST2AlgorithmsandDataStructures:EXSORT1、外存信息的存取1、外部排序：内部排序：信息一次可全部调入内存，信息在内存中的处理时间是主要的时间耗费。外部排序：信息量巨大，无法一次调入内存。只能驻留在带、盘、CD-ROM上。特点为内存运行时间短，内、外存进行交换需要时间长。减少I/O时间成为主要矛盾。•记录（Record）：数据项的集合存于内存，称之为结点。如果存之于外存，则叫做记录。原因起源于是在历史上研究管理应用和计算机科学的两部分人员的习惯。•域（场）：记录中的每个数据项，称之为域（Field）。•文件：记录的集合。•关键字：唯一标识记录的域，称之为关键字。•有序文件：文件根据关键字的大小。排成递增或递减的序列。2、基本术语：3、常用外存：•磁带：由磁带介质、读、写磁头、驱动器、接收盘和原始盘组成。便宜、可反复使用、是一种顺序存取设备。查找费时、速度幔。3物料管理EXST3AlgorithmsandDataStructures:EXSORT1、外存信息的存取3、常用外存：•磁带：由磁带介质、读、写磁头、驱动器、接收盘和原始盘组成。便宜、可反复使用、是一种顺序存取设备。查找费时、速度慢。•带信息的表示：一种磁化方向、代表1另一种磁化方向，代表001001001101011114物料管理EXST4AlgorithmsandDataStructures:EXSORT1、外存信息的存取3、常用外存：•磁带：由磁带介质、读、写磁头、驱动器、接收盘和原始盘组成。便宜、可反复使用、是一种顺序存取设备。查找费时、速度慢（尤其是查找末端记录时）。..磁带机走向读出头写入头原始盘接收盘•带文件的组织：记录1记录3记录2IRG（InterRecordGap）记录间隙5物料管理EXST5AlgorithmsandDataStructures:EXSORT1、外存信息的存取3、常用外存：•带文件的组织：记录1记录3记录2IRG（InterRecordGap）记录间隙vt可靠读写区IRG：.5~.75inch，带来的问题是什么？带的利用率下降，如：密度800byteperinch的带。设每个记录有80byte，共1000个记录。如果，IRG＝.6inch;带的利用率？1000×(80/800)＝100inch(filel)1000×0.6＝600inch(totalIRG)利用率＝1/7=14%必须改进带的利用率!•带文件的读写时间：Ti/o=ta+n×twta延迟时间：读写头到达相应的物理块的起始位置的时间。tw读/写一个字符的时间；n记录数。读写头6物料管理EXST6AlgorithmsandDataStructures:EXSORT1、外存信息的存取3、常用外存：•带文件的组织的改进：块1块3块2IBG（InterBlockGap）块间间隙IBG：.5~.75inch，带来的好处是什么？每一块是一个物理记录，包含若干个逻辑记录。B.F（块因子）＝一个物理记录包含逻辑记录的个数带的利用率上升，如上例：设B.F=1001000/100×0.6＝6inch(totalIBG)1000×80/800＝100inch(file)利用率＝100/106=94.3%7物料管理EXST7AlgorithmsandDataStructures:EXSORT1、外存信息的存取3、常用外存：•磁盘：由存取装置、读、写磁头、活动臂、盘片（磁道、扇区）、旋转主轴构成。速度快、容量大、直接存取设备。•种类：固定头磁盘、活动头磁盘固定头磁盘：每个磁道都有一个磁头（速度快）活动头磁盘：每个盘面共用一个磁头，增加了找道的时间，应用广泛。•柱面：各盘面的直径相同的磁道的总和。•物理位置：盘组号、若干个磁盘构成一组，系统可能有许多组。柱面号、磁道号、块（扇区号）•盘文件的读写时间：Ti/o=tseck+tla+n×twmtseck：找道时间tla：等待时间twm：传输时间/字符，n记录数。8物料管理EXST8AlgorithmsandDataStructures:EXSORT2、外部排序的方法1、步骤：•生成合并段（run）：读入文件的部分记录到内存－在内存中进行内部排序－将排好序的这些记录写入外存，形成合并段－再读入该文件的下面的记录，往复进行，直至文件中的记录全部形成合并段为止。•外部合并：将上一阶段生成的合并段调入内存，进行合并，直至最后形成一个有序的文件。•平衡合并分类法：被合并的初始合并段均匀分布在K条磁带上，即分布在T1、T2、……Tk上。对这K条带进行合并，将生成的中间归并段分布在TK+1、TK+2、……T2K上。然后，循环往复，直至最后形成一个单一的合并段为止。e.g:平衡2路归并，K＝2。2K=4,需4条磁带。六个初始合并段均匀分布在T1、T2上。每个合并段有1000个记录。T3、T4初始为空。合并过程如下：初始分布：R（1……1000）R（2001…2000）R（4001...5001）R（1001……2000）R（3001…4000）R（5001...6000）T1T2T4：空T3：空7、15、198、11、1316、23、315、129物料管理EXST9AlgorithmsandDataStructures:EXSORT2、外部排序的方法•初始分布：R（1……1000）R（2001…2000）R（4001...5001）R（1001……2000）R（3001…4000）R（5001...6000）T1T2T4：空T3：空•第一趟归并：T1：空T2：空T3：T4：R（1……2000）R（4001…6000）R（2001……4000）10物料管理EXST10AlgorithmsandDataStructures:EXSORT2、外部排序的方法•第二趟归并：T3：空T4：空T1：T2：R（1……4000）R（4001……6000）•第三趟归并：T3：T4：空T1：空T2：空R（1……6000）11物料管理EXST11AlgorithmsandDataStructures:EXSORT2、外部排序的方法e.g:平衡3路归并，K＝3。2K=6,需4条磁带。六个初始合并段均匀分布在T1、T2、T3上。每个合并段有1000个记录。T4、T5、T6初始为空。合并过程如下：初始分布：R（1……1000）R（3001…4000）R（1001……2000）R（4001…5000）T1：T2：T4：空T3：R（2001……3000）R（5001…6000）T5：空T6：空•第一趟归并：R（1……3000）R（3001……6000）T4：T5：T1：空T2：空T3：空T6：空12物料管理EXST12AlgorithmsandDataStructures:EXSORT2、外部排序的方法e.g:平衡3路归并，K＝3。2K=6,需4条磁带。六个初始合并段均匀分布在T1、T2、T3上。每个合并段有1000个记录。T4、T5、T6初始为空。合并过程如下：•第一趟归并：R（1……3000）R（3001……6000）T4：T5：T1：空T2：空T3：空T6：空•第二趟归并：R（1……6000）T1：T2：空T3：空T4：空T5：空T6：空13物料管理EXST13AlgorithmsandDataStructures:EXSORT2、外部排序的方法•时间分析:归并趟数:logkmwherek是路数；m是初始合并段数。在上例中：log26=3而log36=2此外，还有一次生成所有合并段的时间。对文件中的所有的记录全部读写一次。每一趟归并时，对文件中的所有的记录都要全部读写一次。K大，趟数减少，读写记录的总数将减少。但K大，需要的内存将越多。减少初始合并段数m,将使趟数减少，读写记录的总数将减少。这就要求在内存一定且进行内部排序时，生成尽可能长的归并段，从而减少归并段的总数。•输入、输出缓冲区的安排:设进行平衡2路归并，K＝2。2K=4,需4条磁带。六个初始合并段均匀分布在T1、T2。每个合并段有1000个记录。T3、T4初始为空。R（1……1000）R（2001…2000）R（4001...5001）R（1001……2000）R（3001…4000）R（5001...6000）T1T2T4：空T3：空14物料管理EXST14AlgorithmsandDataStructures:EXSORT2、外部排序的方法•输入、输出缓冲区的安排:设进行平衡2路归并，K＝2。2K=4,需4条磁带。六个初始合并段均匀分布在T1、T2。每个合并段有1000个记录。T3、T4初始为空。设每个物理块包含250个记录，则每个初始合并段包含4个物理块。K路合并，K个输入输入缓冲区和一个输出缓冲区。R（1……1000）R（2001…2000）R（4001...5001）R（1001……2000）R（3001…4000）R（5001...6000）T1T2T4：空T3：空250个记录T1T2250个记录250个记录250个记录250个记录250个记录250个记录250个记录IBG（InterBlockGap）初始合并段(R（1……1000）)250个记录T3250个记录大250个记录大K(＝2)个输入缓冲区250个记录大1个输出缓冲区15物料管理EXST15AlgorithmsandDataStructures:EXSORT3、多路平衡归并的实现•时间分析:logkm趟K大，趟数减少，读写记录的总数将减少。但K大，会带来什么问题呢？1、带、盘的平衡多路归并的性质：•e.g:K=2时,m个归并串。总共n个记录。合并段1合并段2合并段m-1合并段m中间合并段中间合并段中间合并段中间合并段有序文件层数：log2m+1归并趟数：log2m16物料管理EXST16AlgorithmsandDataStructures:EXSORT3、多路平衡归并的实现1、带、盘的平衡多路归并的性质：•e.g:K2时,趟数将会减少。m个归并串。总共n个记录。合并段1合并段k合并段m-1合并段m中间合并段中间合并段有序文件层数：logkm+1归并趟数：logkm•设从k个元素中挑选一个最小的元素需(k-1)次比较。每次比较耗费的时间代价为:tmg，那么在进行k路平衡归并时，总的时间耗费不会超过：logkm×(k-1)×(n-1)×tmg=log2m/log2k×(k-1)×(n-1)×tmgklog2m/log2k×(k-1)大大17物料管理EXST17AlgorithmsandDataStructures:EXSORT3、多路平衡归并的实现1、带、盘的平衡多路归并的性质：•设从k个元素中挑选一个最小的元素需(k-1)次比较。每次比较耗费的时间代价为:tmg，那么在进行k平衡归并时，总的时间耗费不会超过：logkm×(k-1)×(n-1)×tmg=log2m/log2k×(k-1)×(n-1)×tmgklog2m/log2k×(k-1)大大•改进：采用胜者树或者败者树，从K个元素中挑选一个最小的元素仅需log2k次比较，这时总的时间耗费将下降：logkm×log2k×(n-1)×tmg2、胜者树及其使用胜者进入下一轮，直至决出本次比赛的冠军。决出冠军之后，充分利用上一次比赛的结果，使得更快地挑出亚军、第三名……。18物料管理EXST18AlgorithmsandDataStructures:EXSORT953、多路平衡归并的实现2、胜者树及其使用胜者进入下一轮，直至决出本次比赛的冠军。决出冠军之后，充分利用上一次比赛的结果，使得更快地挑出亚军、第三名……。72959551649527871225849129385766719224748597654321输入缓冲区输出缓冲区55957299765