5外部排序.ppt

1、外部排序,内容,外存信息的存取 外部排序的基本方法归并排序法 多路平衡归并 置换-选择排序,外部排序的应用对象 保存在外存储器上的信息量很大的数据记录文件。 外排序与内排序的差别 内部排序充分利用内存可以随机存取的特点，如 希尔排序中，相隔di的记录关键字可作比较； 堆排序中，完全二叉树中父Ri与子R2i，R2i+1可比 快速排序中，需正向和逆向访问记录序列 外存信息的定位和存取受其物理特性的限制 外部排序的实现手段 在排序过程中，进行多次内外存之间的数据交换,外部排序的特点,所谓内排序就是可以在内存中完成的排序。RAM的访问速度大约是磁盘的25万倍，我们当然希望如果可以的话都是内排来完成。但

2、对于大数据集来说，内存是远远不够的，这时候就涉及到外排序的知识了。 外排序分为两个步骤：预处理和合并排序。即首先根据内存的大小，将有n个记录的磁盘文件分批读入内存，采用有效的内存排序方法进行排序，将其预处理为若干个有序的子文件，这些有序子文件就是初始顺串，然后采用合并的方法将这些初始顺串逐趟合并成一个有序文件。,外排序的时间消耗又由最初归并段的内排序时间，文件I/O时间和归并排序时间几部分组成，但影响排序时间的主要是文件I/O时间，因此应尽量采取一些手段，如减少文件扫描次数，有效利用缓冲区，使I/O和CPU处理尽可能重叠来提高外排序速度 在外存上进行排序的最通常的方法是合并排序。这种方法由两个

3、相对独立的阶段组成：预处理和合并排序，即首先根据内存的大小，将有n个记录的磁盘文件分批读入内存，采用有效的排序方法进行排序，将其预处理为若干个有序的子文件，这些有序子文件被称为初始游程或顺串(run)，然后采用合并的方法将这些初始游程逐趟合并成一个有序文件。 对文件扫描一遍，意味着文件中的每个记录被读/写一次，即从磁盘上读入内存一次，在内存中完成合并后，再写到磁盘一次。由此看来，扫描的遍数对于合并排序的时间起着决定性作用。 预处理时先产生初始游程能提高外排序的效率，很重要的原因是减少了对磁盘数据的扫描遍数。,外排序基本方法：归并排序,步骤 生成若干初始归并串/顺串(文件预处理) 把含有n个记录

4、的文件，按内存缓冲区大小分成若干长度为L的子文件（段）； 分别调入内存用有效的内排序方法排序后送回外存； 多路合并 对初始归并串逐趟合并，直至最后在外存上得到整个有序文件为止,例某文件共10000个记录，设每个物理块可以容纳200个记录，内存缓冲区可以容纳5个物理块 1)经过10次内排序后得到10个初始归并段R1R10 2)采用两路归并，需四趟可以得到排好序的文件 R1 R2 R3 R4 R5 R6 R7 R8 R9 R10 2000 2000 2000 2000 2000 4000 4000 8000 10000,提高外排序效率的途径,扩大初始归并段长度，从而减少初始归并段个数m 进行多路(

5、k路)归并 减少合并趟数s，以减少I/O次数 s = logkm,多 路 归 并,多路平衡归并,通过简单比较进行K路归并存在的问题 设记录总数为n，初始归并段的个数为m， 从k个记录中选择一个关键字最小的记录时的比较次数为c 则s趟内部归并总的比较次数为： C=sc(n-1)= logkm c (n-1)= log2m/ log2k c (n-1) k，s，可减少I/O次数； k， c=(k-1) ，归并效率 解决矛盾的方法 利用“败者树”选关键字最小的记录 此时c= log2k 则 C= log2m(n-1) ，与k无关,矛盾,1 2 k,胜者树(树形选择排序),6 8 6 8 9 8 9

6、6 8 90 9 15 8 90 10 9 20 6 8 12 10 9 20 15 8 12 10 9 20 6 8 12 90 10 9 20 15 8 12 90 14 22 24 15 16 17 92 14 22 24 25 16 17 92 26 38 30 25 50 18 97 26 38 30 50 18 97 7路合并胜者树 重构后的胜者树 重构胜者树时，从根结点至新补入记录的叶结点的路径上的所有结点都必须更新。,败者树,5 2 2 0 4 0 1 3 6 90 1 3 6 90 10 9 20 6 8 12 10 9 20 15 8 12 10 9 20 6 8 12 9

7、0 10 9 20 15 8 12 90 14 22 24 15 16 11 92 14 22 24 25 16 11 92 26 38 30 25 50 18 97 26 38 30 50 18 97 7路合并败者树 重构后的败者树 败者树的特点：记录败者，胜者参加下一轮比赛 败者树的优点：重构时修改结点较少,0,1 2 3 4 5 6,4,ls0,5,ls0,1 2 3 4 5 6,0,4 5 2 0 1 3 6 90 0 10 9 20 6 8 12 1 2 3 4 5 6 调整败者树的方法: 将新补充的结点与其双亲结点比较, 败者留在该双亲结点,胜者继续向上直至树根的双亲,以在b4补充

8、15为例,15,4与3比较,4与2比较,4,2与5比较,2,5,调整败者树的方法,7 7 7 7 7 7 7 90 0 10 9 20 6 8 12 1 2 3 4 5 6 k-路归并对内存的要求 至少要有k个输入缓冲区和一个输出缓冲区,建败者树的过程,7,-1,初始化败者树,调整b6,6,调整b5,5,调整b4,4,调整b3,3,4,调整b2,2,调整b1,1,2,4,调整b0,0,5,4,建败者树的过程,数据结构 (依据：败者树为完全二叉树) 主：b0. k b0. k-1k个叶结点 ，存放k个输入归并段中当前 参加归并的记录（缓冲区） bk虚拟记录，该关键字取可能的最小值minkey 辅

9、：ls0. k-1 不含叶结点的败者树 存放最后胜出的编号（ls0）以及所记录的败者编号 处理步骤 建败者树ls0. k-1 重复下列操作直至k路归并完毕 将bls0写至输出归并段 补充记录(某归并段变空时,补)，调整败者树,多路平衡归并算法,算法描述：建立败者树,void CreateLoserTree() bk = MINKEY; for (i = 0; i = 0; i+) Adjust(i); void Adjust(int s) for (t = (s + k) / 2; t 0; t /= 2) if (bs blst) s lst; ls0 = s; ,算法描述: K路合并,vo

10、id K_Merge() for (i = 0; i k; i+) input(i); /* 第i路输入一个元素到bi */ CreateLoserTree(ls); while (bls0 != MAXKEY) q = ls0; output(bq); input(q); Adjust(q); ,置 换 - 选 择 排 序,置换-选择排序,目标 扩大初始归并段长度，突破内存工作区容量(设w个记录)的限制。 置换-选择排序原理 内存 外存 原始文件 内存工作区 FI WA 初始归并段文件 (w个记录) FO 为简化问题，设每个物理块存放一个记录,1) 从FI输入w个记录到工作区WA； 2) 在

11、FO中标记一个归并段开始； 3) 从WA中选出最小关键字记录，记为minimax记录； 4) 将minimax记录输出到FO中； 5) 从FI输入下一个记录到WA中； 6) 在WA中的关键字比minimax大的记录中选出关键字最小的记录 6.1) 若不能选到，在FO中标记一个归并段结束； 若由于WA为空而未选出，则结束处理； 否则，标记下一个归并段开始，转 3) 6.2) 否则，将选出的记录作为新的minimax记录，转 4),FO WA(4个记录) FI 空 空 36,21,33,87,23,7,62,16, 54,43,29, 空 36,21,33,87 23,7,62,16,54, 43

12、,29, 21 36,23,33,87 7,62,16,54, 43,29, 21,23 36,7,33,87 62,16,54,43,29, 21,23,33 36,7,62,87 16,54,43,29, 21,23,33,36 16,7,62,87 54,43,29, 21,23,33,36,62 16,7,54,87 43,29, 21,23,33,36,62,87 16,7,54,43 29, 21,23,33,36,62,87|7 16,29,54,43 ,置换-选择排序的效果,所得初始排序段的长度不等 当输入文件记录的关键字大小随机分布时，初始归并段的平均长度为内存工作区大小w的

13、两倍,最 佳 归 并 树,最佳归并树,文件经过置换-选择排序之后，得到长度不等的初始归并段，进行k路归并时，初始归并段的不同搭配，会导致归并过程中I/O的次数不同。 设有9个初始归并段，记录个数(长度)分别为： 9，30，12，18，3，17，2，6，24 121 121 51 38 32 30 32 59 9 30 12 18 3 17 2 6 24 11 9 12 17 18 24 2 3 6 (9+30+12+18+3+17+2+6+24)2 (2+3+6) 3+(9+12+17 +(51+38+32) 2 +18+24) 2+30 1 2 =484 =446,3-路归并,所有叶结点加权

14、外通路长度的2倍,IO,方案二,方案一,最佳归并树的构造,最佳归并树即k叉(阶)哈夫曼树。 设初始归并段为m个，进行k-路归并 1）若 (m-1) mod (k-1) 0 则需附加(k-1)- (m-1) mod (k-1) 个长度为0的虚段，以使每次归并都可以对应k个段 2）按照哈夫曼树的构造原则（权值越小的结点离根结点越远）构造最佳归并树。,k阶哈夫曼树示例,长度分别为2，3，6，9，12，17，18，24的8个初始归并段进行3路归并，求最佳归并树。 91 20 24 47 5 6 9 12 17 18 0 2 3 I/O次数： (2+3)3 + (6+9+12+17+18)2 + 241

15、 2 = 326,计数排序,计数排序是一种算法复杂度 O(n) 的排序方法，适合于小范围集合的排序。比如100万学生参加高考，我们想对这100万学生的数学成绩（假设分数为0到100）做个排序。,计数排序是一个类似于桶排序的排序算法，其优势是对已知数量范围的数组进行排序。它创建一个长度为这个数据范围的数组C，C中每个元素记录要排序数组中对应记录的出现个数。这个算法于1954年由 Harold H. Seward 提出。 下面以示例来说明这个算法 假设要排序的数组为 A = 1,0,3,1,0,1,1 这里最大值为3，最小值为0，那么我们创建一个数组C，长度为4. 然后一趟扫描数组A，得到A中各个

16、元素的总数，并保持到数组C的对应单元中。 比如0 的出现次数为2次，则 C0 = 2;1 的出现次数为4次，则C1 = 4 由于C 是以A的元素为下标的，所以这样一做，A中的元素在C中自然就成为有序的了，这里我们可以知道 顺序为 0,1,3 (2 的计数为0) 然后我们把这个在C中的记录按每个元素的计数展开到输出数组B中，排序就完成了。,这种排序算法，依靠一个辅助数组来实现，不基于比较，算法复杂度为 O(n) ，但由于要一个辅助数组C，所以空间复杂度要大一些，由于计算机的内存有限，这种算法不适合范围很大的数的排序。 注：基于比较的排序算法的最佳平均时间复杂度为 O(nlogn),public

17、static void Sort(int A, int k) Debug.Assert(k 0); Debug.Assert(A != null); int C = new intk + 1; for (int j = 0; j 0) Az+ = i; ,关于海量数据处理,常用的数据结构： 1.Bloom Filter 大致思想是这样，把一个数据通过N个哈希函数映射到一个长度为M的数组的一位上，将hash函数对应的值的位数组置1，查找时如果发现所有hash函数对应位都是1说明该数据的存在。但不能保证完全正确性，但是此方法无比高效。 【实例】给你A,B两个文件，各存放50亿条URL，每条URL占

18、用64字节，内存限制是4G，让你找出A,B文件共同的URL。 2.哈希法 这个简单，无非是通过一些哈希函数把元素搞到一个指定的位置，简单的说就是一种将任意长度的消息压缩到某一固定长度的消息摘要的函数。这个很一般啊感觉。无非就是分类查找么，完全不如1猛。 3.最大或最小堆 就是一个完全的最大或最小二叉树，用途，比如:1)100w个数中找最大的前100个数。用一个100个元素大小的最小堆即可。感觉还是不错的。 4.Bit-map 所谓的Bit-map就是用一个bit位来标记某个元素对应的Value， 而Key即是该元素。由于采用了Bit为单位来存储数据，因此在存储空间方面，可以大大节省。,大数查找

19、排序,1 在一个文件中有 10G 个整数，乱序排列，要求找出中位数。内存限制为 2G . 2 一个文件中有9亿条不重复的9位整数，要求对这个文件进行排序 4)已知某个文件内包含一些电话号码，每个号码为8位数字，统计不同号码的个数 5)2.5亿个整数中找出不重复的整数的个数，内存空间不足以容纳这2.5亿个整数,中位数：数据排序后，位置在最中间的数值。 将数据分成两部分，一部分大于该数值，一部分小于该数值。 中位数的位置：当样本数为奇数时，中位数=(N+1)/2 ; 当样本数为偶数时，中位数为N/2与1+N/2的均值（那么10G个数的中位数，就第5G大的数与第5G+1大的数的均值了）,分析：明显是

20、一道工程性很强的题目，和一般的查找中位数的题目有几点不同。1. 原数据不能读进内存，不然可以用快速选择，如果数的范围合适的话还可以考虑桶排序或者计数排序，但这里假设是32位整数，仍有4G种取值，需要一个16G大小的数组来计数。 2. 若看成从N个数中找出第K大的数，如果K个数可以读进内存，可以利用最小或最大堆，但这里K=N/2,有5G个数，仍然不能读进内存。 3. 对于N个数和K个数都不能一次读进内存的情况，一个可行方案： 设kK,且k个数可以完全读进内存，那么先构建k个数的堆，先找出第0到k大的数，再扫描一遍数组找出第k+1到2k的数，再扫描直到找出第K个数。虽然每次时间大约是nlog(k)

21、，但需要扫描ceil(K/k)次，这里要扫描5次。,解法：首先假设是32位无符号整数。1. 读一遍10G个整数，把整数映射到256M个区段中，用一个64位无符号整数给每个相应区段记数。说明：整数范围是0 - 232 - 1，一共有4G种取值，映射到256M个区段，则每个区段有16（4G/256M = 16）种值，每16个值算一段， 015是第1段，1631是第2段，232-16 232-1是第256M段。一个64位无符号整数最大值是08G-1，这里先不考虑溢出的情况。总共占用内存256M8B=2GB。 2. 从前到后对每一段的计数累加，当累加的和超过5G时停止，找出这个区段（即累加停止时达到的

22、区段，也是中位数所在的区段）的数值范围，设为a，a+15，同时记录累加到前一个区段的总数，设为m。然后，释放除这个区段占用的内存。 3. 再读一遍10G个整数，把在a，a+15内的每个值计数，即有16个计数。 4. 对新的计数依次累加，每次的和设为n，当m+n的值超过5G时停止，此时的这个计数所对应的数就是中位数。,总结：1.以上方法只要读两遍整数，对每个整数也只是常数时间的操作，总体来说是线性时间。 2. 考虑其他情况。若是有符号的整数，只需改变映射即可。若是64为整数，则增加每个区段的范围，那么在第二次读数时，要考虑更多的计数。若过某个计数溢出，那么可认定所在的区段或代表整数为所求，这里只

23、需做好相应的处理。噢，忘了还要找第5G+1大的数了，相信有了以上的成果，找到这个数也不难了吧。 3. 时空权衡。花费256M个区段也许只是恰好配合2GB的内存4. 映射时尽量用位操作，由于每个区段的起点都是2的整数幂，映射起来也很方便。,2 一个文件中有9亿条不重复的9位整数，要求对这个文件进行排序,一般解题思路: 1、将数据导入到内存中 2、将数据进行排序（比如插入排序、快速排序） 3、将排序好的数据存入文件,难题: 一个整数为4个字节 即使使用数组也需要900,000,000 * 4byte = 3.4G内存 对于32位系统，访问2G以上的内存非常困难，而且一般设备也没有这么多的物理内存

24、将数据完全导入到内存中的做法不现实,其他解决办法: 1、导入数据库运算 2、分段排序运算 3、使用bit位运算,解决方案一:数据库排序 将文本文件导入到数据库，让数据库进行索引排序操作后提取数据到文件 优点：操作简单 缺点：运算速度慢，而且需要数据库设备。,解决方案二:分段排序 操作方式： 规定一个内存大小，比如200M，200M可以记录(200*1024*1024/4) = 52428800条记录，我们可以每次提取5000万条记录到文件进行排序，要装满9位整数需要20次，所以一共要进行20次排序，需要对文件进行20次读操作 缺点： 编码复杂，速度也慢(至少20次搜索) 关键步骤： 先将整个9

25、位整数进行分段，亿条数据进行分成20段，每段5000万条 在文件中依次搜索05000万，500000011亿 将排序的结果存入文件,解决方案三:bit位操作 思考下面的问题: 一个最大的9位整数为999999999 这9亿条数据是不重复的 可不可以把这些数据组成一个队列或数组，让它有0999999999(10亿个)元素 数组下标表示数值，节点中用0表示这个数没有，1表示有这个数 判断0或1只用一个bit存储就够了,声明一个可以包含9位整数的bit数组(10亿)，一共需要10亿/8=120M内存 把内存中的数据全部初始化为0, 读取文件中的数据，并将数据放入内存。比如读到一个数据为3412459

26、09这个数据，那就先在内存中找到341245909这个bit，并将bit值置为1遍历整个bit数组，将bit为1的数组下标存入文件,关键代码 检查是某一个char里面(first)的第second位中存储的数据是否为1 bool CompareBit (unsigned char first, int second) const static int mark_buf = 0 x1, 0 x2, 0 x4, 0 x8, 0 x10, 0 x20, 0 x40, 0 x80; if (second .8) return false; return (first ,4)已知某个文件内包含一些电话号

27、码，每个号码为8位数字，统计不同号码的个数 解： 8位最多99 999 999，大概需要99M个bit，大概10几m字节的内存即可。 （可以理解为从0-99 999 999的数字，每个数字对应一个Bit位，所以只需要99M个Bit=1.2MBytes，这样，就用了小小的1.2M左右的内存表示了所有的8位数的电话）,5)2.5亿个整数中找出不重复的整数的个数，内存空间不足以容纳这2.5亿个整数 解：将bit-map扩展一下，用2bit表示一个数即可，0表示未出现，1表示出现一次，2表示出现2次及以上，在遍历这些数的时候，如果对应位置的值是0，则将其置为1；如果是1，将其置为2；如果是2，则保持不变。或者我们不用2bit来进行表示，我们用两个bit-map即可模拟实现这个2bit-map，都是一样的道理。,6 在某个项目中，我们需要对2亿条手机号码删除重