PowerPoint 演示文稿

Size: px

Start display at page:

Download "PowerPoint 演示文稿"

楣植翟
5 years ago
Views:

1 张铭数据结构与算法数据结构与算法 ( 九 ) 张铭主讲采用教材 : 张铭, 王腾蛟, 赵海燕编写高等教育出版社, ( 十一五国家级规划教材 )

2 第 9 章 91 主存储器和外存储器 92 文件的组织和管理 931 置换选择排序 932 二路外排序 933 多路归并选择树 2 张铭数据结构与算法

3 磁盘文件的排序对外存设备上 ( 文件 ) 的排序技术通常由两个相对独立的阶段组成 : 文件形成尽可能长的初始顺串 (run ) 处理顺串, 最后形成对整个数据文件的排列文件 3 张铭数据结构与算法

4 置换选择排序 4 张铭数据结构与算法

5 输入第九章置换选择示例输出重新排列堆 16 插入 29 >16 存储输出 < <25<29 5 张铭数据结构与算法

6 输入置换选择示例 <19 输出重新排列堆插入 >21 < 存储输出 14 40>31>21 35>31> >31> >29>25 35>29 56>40> 张铭数据结构与算法

7 置换选择算法的实现 // 模板参数 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 张铭数据结构与算法

8 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 位置 // 调整根结点

9 置换选择算法的效果置换选择排序算法得到的顺串长度并不相等如果堆的大小是 M 一个顺串的最小长度就是 M 个记录至少原来在堆中的那些记录将成为顺串的一部分最好的情况下, 例如输入为正序, 有可能一次就把整个文件生成为一个顺串平均情况下, 置换选择排序算法可以形成长度为 2M 的顺串 9 张铭数据结构与算法

10 扫雪机模型 10 张铭数据结构与算法

11 二路外排序归并原理 : 把第一阶段所生成的顺串加以合并 ( 例如通过若干次二路合并 ), 直至变为一个顺串为止, 即形成一个已排序的文件为一个待排文件创建尽可能大的初始顺串, 可以大大减少扫描遍数和外存读写次数归并顺序的安排也能影响读写次数, 把初始顺串长度作为权, 其实质就是 Huffman 树最优化问题 11 张铭数据结构与算法

12 二路归并外排序每个顺串中每个顺串中的记的块数顺串 1 录数顺串顺串 1 顺串 2 顺串顺串 1 顺串 2 顺串 3 顺串 4 顺串 5 顺串读写各 :3*6 + 6*2 + (12 +6)= 48 次 12 张铭数据结构与算法

13 多路归并 13 张铭数据结构与算法

14 多路归并选择树 k 路归并是每次将 k 个顺串合并成一个排好序的顺串在 k 路归并中, 最直接的方法就是作 k-1 次比较来找出所要的记录, 但这样做花的代价较大我们采用选择树的方法来实现 k 路归并选择树是完全二叉树, 有两种类型 : 赢者树和败方树一般情况下, 对 m 个初始顺串进行 k 路归并时归并趟数为 log k m 增加每次归并的顺串数量 k 可以减少归并趟数 14 张铭数据结构与算法

15 赢者树与数组的对应关系 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

16 赢者树的示例第九章 B[2] 4 B[1] 4 B[3] B[4] B[5] B[6] B[7] 2 9<15 20> >8 L[1] L[2] L[3] L[4] L[5] L[6] L[7] L[8] 顺串 1 顺串 2 顺串 3 顺串 4 顺串 5 顺串 6 顺串 7 顺串 8 重构后的赢者树根结点所指向的, L[4] 改动的结点用较粗的框显示出来为了重构记录具有最小的关键码值 6, 它所指的这棵树记录是顺串, 只须沿着从结点 4 的当前记录, L[4] 该记录即为下一个要输出的记录到根结点的路径重新进行比赛 16 张铭数据结构与算法

17 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 张铭数据结构与算法

18 B[0] 外部结点数 n 为奇数 B[2] B[1] B[3] B[4] L[4] L[5] L[1] L[2] L[3] 18 张铭数据结构与算法

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

19 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] 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] 顺串 1 顺串 2 顺串 3 顺串 4 顺串 5 顺串 6 顺串 7 顺串 8 19 张铭数据结构与算法

20 败方树 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 张铭数据结构与算法

21 败方树 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 张铭数据结构与算法

22 }} 第九章 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; 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]

23 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] L[3] L[4] 张铭数据结构与算法

24 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] L[4]

25 外排序效率考虑对同一个文件而言, 进行外排序所需读写外存的次数与归并趟数有关系假设有 m 个初始顺串, 每次对 k 个顺串进行归并, 归并趟数为 log k m 为了减少归并趟数, 可以从两个方面着手 : 减少初始顺串的个数 m 增加归并的顺串数量 k 25 张铭数据结构与算法

26 假设对 k 个顺串进行归并, 归并后长 n 原始方法 (k n), 找到每一个最小值的时间是 (k) 败方树方法总时间为 (k+n log k) 初始化包含 k 个选手的败方树需要 (k) 的时间读入一个新值并重构败方树的时间为 (log k) 26 张铭数据结构与算法

27 最佳归并树 (a) 一棵普通的归并树 (b) 最佳归并树读写总次数次 376 读写总次数次张铭数据结构与算法

28 思考是否可以用赢者树或败方树形成初始顺串? 是否可以用堆进行多路归并? 28 张铭数据结构与算法

29 张铭数据结构与算法数据结构与算法谢谢聆听国家精品课数据结构与算法张铭, 王腾蛟, 赵海燕高等教育出版社, 十一五国家级规划教材

PowerPoint 演示文稿

PowerPoint 演示文稿张铭数据结构与算法数据结构与算法 ( 九 ) 张铭主讲采用教材 : 张铭, 王腾蛟, 赵海燕编写高等教育出版社,2008. 6 ( 十一五国家级规划教材 ) http://www.jpk.pku.edu.cn/pkujpk/course/sjjg 第 9 章 9.1 主存储器和外存储器 9.2 文件的组织和管理 9.2.1 文件组织 9.2.2 C++ 的流文件 9.3 外排序 2 张铭数据结构与算法