张铭 数据结构与算法 数据结构与算法 ( 九 ) 张铭主讲 采用教材 : 张铭, 王腾蛟, 赵海燕编写高等教育出版社,2008 6 ( 十一五 国家级规划教材 ) http://wwwjpkpkueducn/pkujpk/course/sjjg
第 9 章 91 主存储器和外存储器 92 文件的组织和管理 931 置换选择排序 932 二路外排序 933 多路归并 选择树 2 张铭 数据结构与算法
磁盘文件的排序 对外存设备上 ( 文件 ) 的排序技术 通常由两个相对独立的阶段组成 : 文件形成尽可能长的初始顺串 (run ) 处理顺串, 最后形成对整个数据文件的排列文件 3 张铭 数据结构与算法
置换选择排序 4 张铭 数据结构与算法
输入 第九章 置换选择示例 输出重新排列堆 16 插入 29 >16 存储 输出 16 29 19<29 12 14 19 31 35 13 25 21 56 40 21<25<29 5 张铭 数据结构与算法
输入 置换选择示例 <19 输出重新排列堆 21 19 插入 >21 <25 35 14 存储 输出 14 40>31>21 35>31>25 19 56>31>29 16 35 21 31 12 13 40>29>25 35>29 56>40>35 25 29 56 40 6 张铭 数据结构与算法
置换选择算法的实现 // 模板参数 Elem 代表数组中每一个元素的类型 // A 是从外存读入 n 个元素后所存放的数组 // in 和 out 分别是输入和输出文件名 template <class Elem> void replacementselection(elem * A, int n, const char * in, const char * out) { Elem mval; // 存放最小值堆的最小值 Elem r; // 存放从输入缓冲区中读入的元素 FILE * inputfile; // 输入 输出文件句柄 FILE * outputfile; Buffer<Elem> input; // 输入 输出 buffer Buffer<Elem> output; // 初始化输入输出文件 initfiles(inputfile, outputfile, in, out); initminheaparry(inputfile, n, A); // 建堆 MinHeap<Elem> H(A, n, n); initinputbuffer(input, inputfile); 7 张铭 数据结构与算法
for(int last = (n-1); last >= 0;){ mval = HheapArray[0]; sendtooutputbuffer(input, output, inputfile, outputfile, mval); inputread(r); if (!less(r, mval)) HheapArray[0] = r; else { HheapArray[0] = HheapArray[last]; HheapArray[last] = r; HsetSize(last--); } HSiftDown(0); // 最小值 } // for endup(output, inputfile, outputfile); } // 从输入缓冲区读入一个记录 // r 放到根结点 8 张铭 数据结构与算法 // last 记录代替根结点,r 放到 last 位置 // 调整根结点
置换选择算法的效果 置换选择排序算法得到的顺串长度并不相等 如果堆的大小是 M 一个顺串的最小长度就是 M 个记录 至少原来在堆中的那些记录将成为顺串的一部分 最好的情况下, 例如输入为正序, 有可能一次就把整个文件生成为一个顺串 平均情况下, 置换选择排序算法可以形成长度为 2M 的顺串 9 张铭 数据结构与算法
扫雪机模型 10 张铭 数据结构与算法
二路外排序 归并原理 : 把第一阶段所生成的顺串加以合并 ( 例如通过若干次二路合并 ), 直至变为一个顺串为止, 即形成一个已排序的文件 为一个待排文件创建尽可能大的初始顺串, 可以大大减少扫描遍数和外存读写次数 归并顺序的安排也能影响读写次数, 把初始顺串长度作为权, 其实质就是 Huffman 树最优化问题 11 张铭 数据结构与算法
二路归并外排序 每个顺串中 每个顺串中的记 的块数 顺串 1 录数 18 4500 12 顺串 1 3000 顺串 1 顺串 2 顺串 3 6 1500 顺串 1 顺串 2 顺串 3 顺串 4 顺串 5 顺串 6 3 750 读写各 :3*6 + 6*2 + (12 +6)= 48 次 12 张铭 数据结构与算法
多路归并 13 张铭 数据结构与算法
多路归并 选择树 k 路归并是每次将 k 个顺串合并成一个排好序的顺串 在 k 路归并中, 最直接的方法就是作 k-1 次比较来找出所要的记录, 但这样做花的代价较大 我们采用选择树的方法来实现 k 路归并 选择树是完全二叉树, 有两种类型 : 赢者树和败方树 一般情况下, 对 m 个初始顺串进行 k 路归并时归并趟数为 log k m 增加每次归并的顺串数量 k 可以减少归并趟数 14 张铭 数据结构与算法
赢者树与数组的对应关系 B[2] B[1] B[3] n=6, LowExt=4, Offset=7 LowExt + Offset = 2n-1 B[4] B[5] L[5] L[6] L[1] L[2] L[3] L[4] 外部结点的数目为 n,lowext 代表最底层的外部结点数目 ; offset 代表最底层外部结点之上 ( 内部 +LowExt 之外的外部 ) 所有结点数目 每一个外部结点 L[i] 所对应的内部结点 B[p],i 和 p 之间存在如下的关系 : p = { ( i ( i offset) / 2 i LowExt LowExt n 1) / 2 LowExt 15 张铭 数据结构与算法 i
赢者树的示例 第九章 B[2] 4 B[1] 4 B[3] B[4] B[5] B[6] B[7] 2 9<15 20>15 2 4 5 4 9>8 L[1] L[2] L[3] L[4] L[5] L[6] L[7] L[8] 10 9 20 6 8 12 90 17 5 8 14 26 22 38 24 30 15 15 25 25 16 50 11 28 100 110 18 40 顺串 1 顺串 2 顺串 3 顺串 4 顺串 5 顺串 6 顺串 7 顺串 8 重构后的赢者树根结点所指向的, L[4] 改动的结点用较粗的框显示出来 为了重构记录具有最小的关键码值 6, 它所指的这棵树记录是顺串, 只须沿着从结点 4 的当前记录, L[4] 该记录即为下一个要输出的记录 到根结点的路径重新进行比赛 16 张铭 数据结构与算法
B[2] B[1] B[0] 败方树示例 B[3] n=6 LowExt=4 Offset=7 B[4] B[5] L[5] L[6] L[1] L[2] L[3] L[4] { ( i ( i offset) / 2 i LowExt LowExt n 1) / 2 i LowExt 17 张铭 数据结构与算法
B[0] 外部结点数 n 为奇数 B[2] B[1] B[3] B[4] L[4] L[5] L[1] L[2] L[3] 18 张铭 数据结构与算法
B[0] 败方树示例 全优胜者 L[2]<L[6] L[2]<L[4] B[2] B[1] 5 B[3] 2 2 L[3]>L[4] B[4] B[5] B[6] 1 3 6 L[1] L[2] L[3] 3 L[4] 4 L[5] 5 8 L[5]>L[6] L[6] 6 L[7] L[6]<L[8] B[7] 7 L[8] 10 9 20 6 8 12 90 17 15 16 顺串 1 顺串 2 顺串 3 顺串 4 顺串 5 顺串 6 顺串 7 顺串 8 19 张铭 数据结构与算法
败方树 ADT template<class T> class LoserTree{ private: int MaxSize; // 最大选手数 int n; // 当前选手数 int LowExt; // 最底层外部结点数 int offset; // 最底层外部结点之上的结点总数 int * B; // 败方树数组, 实际存放的是下标 T * L; // 元素数组 void Play(int p,int lc,int rc,int(*winner)(t A[],int b,int c)); 20 张铭 数据结构与算法
败方树 ADT( 续 ) public: LoserTree(int Treesize = MAX); ~LoserTree(){delete [] B;} void Initialize(T A[], int size,int (*winner)(t A[], int b, int c), int(*loser)(t A[], int b, int c)); // 初始化败方树 int Winner(); // 返回最终胜者索引 void RePlay(int i, int(*winner)(t A[], int b, int c), int (*loser)(t A[], int b, int c)); // 位置 i 的选手改变后重构败方树 }; // 成员函数 Winner, 返回最终胜者 B[0] 的索引 template<class T> int LoserTree<T>::Winner(){ return (n)?b[0]:0; } 21 张铭 数据结构与算法
}} 第九章 Play((offset+i)/2, i-1, i, winner, loser); if (n%2) { // n 奇数, 内部和外部比赛 Play(n/2,B[(n-1)/2],LowExt+1,winner,loser); i = LowExt+3; } else i = LowExt+2; for (; i<=n; i+=2) template<class T> // 初始化败方树 B[0] 4 B[1] void LoserTree<T>::Initialize(T A[], int size, int(*winner)(t A[], int 5 b, int c), int(*loser)(t A[], int b, int c)) { if (size > MaxSize size < 2) { B[2] 2 cout<<"bad Input!"<<endl<<endl; return; } n = size; L = A; // 初始化成员变量 1 3 int i,s; // 计算 s=2^log(n-1) L[1] L[2] L[3] L[4] for (s = 1; 2*s <= n-1; s+=s); LowExt = 2*(n-s); offset = 2*s-1; 10 9 20 6 for (i = 2; i <= LowExt; i+=2) // 底层外部 // 剩余外部结点的比赛 Play((i-LowExt+n-1)/2, i-1, i, winner, loser); 22 张铭 数据结构与算法 B[3] B[4] B[5] L[5] L[6] 8 6 12
Play 比赛 template<class T> void LoserTree<T>::Play(int p, int lc, int rc, int(* winner)(t A[], int b, int c), int(* loser)(t A[], int b, int c)){ B[p] = loser(l, lc, rc); // 败者索引放在 B[p] int temp1, temp2; temp1 = winner(l, lc, rc);// p 处的胜者索引 while(p>1 && p%2) { // 内部右, 要沿路向上比赛 temp2 = winner(l, temp1, B[p/2]); B[p/2] = loser(l, temp1, B[p/2]); temp1 = temp2; p/=2; } // B[p] 是左孩子, 或者 B[1] B[p/2] = temp1; } L[1] B[0] B[1] B[2] L[2] B[3] B[4] B[5] L[5] L[6] 1 2 3 8 12 L[3] L[4] 10 9 20 6 4 5 6 23 张铭 数据结构与算法
RePlay 重构 template<class T> void LoserTree<T>::RePlay(int i, int (*winner)(t A[], int b, int c), int (*loser)(t A[], int b, int c)){ if (i <= 0 i > n) { cout<<"out of Bounds!"<<endl<<endl; return; } if (i <= LowExt) // 确定父结点的位置 int p = (i+offset)/2; else p = (i-lowext+n-1)/2; B[0] = winner(l, i, B[p]); B[p] = loser(l, i, B[p]); for(; (p/2)>=1; p/=2) { // 沿路径向上比赛 int temp = winner(l,b[p/2], B[0]); B[p/2] = loser(l,b[p/2], B[0]); B[0] = temp; } } 24 张铭 数据结构与算法 L[1] B[2] L[2] B[1] B[3] B[4] B[5] L[5] L[6] 1 2 L[3] B[0] 3 10 9 20 6 4 L[4] 5 8 6 12
外排序效率考虑 对同一个文件而言, 进行外排序所需读写外存的次数与归并趟数有关系 假设有 m 个初始顺串, 每次对 k 个顺串进行归并, 归并趟数为 log k m 为了减少归并趟数, 可以从两个方面着手 : 减少初始顺串的个数 m 增加归并的顺串数量 k 25 张铭 数据结构与算法
假设对 k 个顺串进行归并, 归并后长 n 原始方法 (k n), 找到每一个最小值的时间是 (k) 败方树方法总时间为 (k+n log k) 初始化包含 k 个选手的败方树需要 (k) 的时间 读入一个新值并重构败方树的时间为 (log k) 26 张铭 数据结构与算法
最佳归并树 2 6 7 6 13 25 8 9 2 14 7 10 13 14 15 8 9 10 44 19 31 42 27 25 94 94 (a) 一棵普通的归并树 (b) 最佳归并树 读写总次数次 376 读写总次数次 356 27 张铭 数据结构与算法
思考 是否可以用赢者树或败方树形成 初始顺串? 是否可以用堆进行多路归并? 28 张铭 数据结构与算法
张铭 数据结构与算法 数据结构与算法 谢谢聆听 国家精品课 数据结构与算法 http://wwwjpkpkueducn/pkujpk/course/sjjg/ 张铭, 王腾蛟, 赵海燕高等教育出版社,2008 6 十一五 国家级规划教材