PowerPoint 演示文稿

Size: px

Start display at page:

Download "PowerPoint 演示文稿"

称武
5 years ago
Views:

张铭数据结构与算法数据结构与算法 ( 九 ) 张铭主讲采用教材 : 张铭, 王腾蛟, 赵海燕编写高等教育出版社,2008.

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

2 第 9 章 9.1 主存储器和外存储器 9.2 文件的组织和管理文件组织 C++ 的流文件 9.3 外排序 2 张铭数据结构与算法

3 主存储器和外存储器计算机存储器主要有两种 : 主存储器 ( primary memory 或者 main memory, 简称内存, 或者主存 ) 随机访问存储器 ( Random Access Memory, 即 RAM ) 高速缓存 ( cache ) 视频存储器 ( video memory ) 外存储器 ( peripheral storage 或者 secondary storage, 简称外存 ) 硬盘 ( 几百 G - 几百 T, B ) 磁带 ( 几个 P, B ) 9.1 主存储器和外存储器 3 张铭数据结构与算法

4 9.1 主存储器和外存储器物理存储介质概览基本存储辅助存储 ( 联机存储 ) 三级存储 ( 脱机存储 ) 高速缓冲存储器主存储器快闪存储器磁盘光盘磁带 4 张铭数据结构与算法易失性非易失性存储

5 9.1 主存储器和外存储器磁盘的物理结构主轴盘片磁道活动臂 ( 回转臂 ) 柱面读写磁头 5 张铭数据结构与算法

6 9.1 主存储器和外存储器磁盘盘片的组织扇区扇区间间隙位数据 (bit) 6 张铭数据结构与算法

7 9.1 主存储器和外存储器磁盘磁道的组织 ( 交错法 ) 每页 512 字节或 1024 字节磁头磁头旋转 (a) 没有扇区交错 ; 旋转 (b) 以 3 为交错因子 7 张铭数据结构与算法

8 9.1 主存储器和外存储器内存的优缺点优点 : 访问速度快缺点 : 造价高, 存储容量小, 断电丢数据 CPU 直接与主存沟通, 对存储在内存地址的数据进行访问时, 所需要的时间可以看作是一个很小的常数 8 张铭数据结构与算法

9 9.1 主存储器和外存储器外存的优缺点优点 : 价格低信息不易失便携性缺点 : 存取速度慢一般的内存访问存取时间的单位是纳秒 (1 纳秒 = 10-9 秒 ) 外存一次访问时间则以毫秒 (1 毫秒 = 10-3 秒 ) 或秒为数量级牵扯到外存的计算机程序应当尽量减少外存的访问次数, 从而减少程序执行的时间 9 张铭数据结构与算法

10 9.1 主存储器和外存储器 KB (kilo byte) 10 3 B ( 页块 ) MB (mega byte) 10 6 B ( 高速缓存 ) GB (giga) 10 9 B ( 内存硬盘 ) TB (tera) B ( 磁盘阵列 ) PB (peta) B ( 磁带库 ) EB = B;ZB = B;YB = B Googol 是 10 的 100 次方 10 张铭数据结构与算法

11 9.2 文件的组织和管理文件的逻辑结构文件是记录的汇集一个文件的各个记录按照某种次序排列起来, 各纪录间就自然地形成了一种线性关系因而, 文件可看成是一种线性结构 11 张铭数据结构与算法

12 9.2 文件的组织和管理文件的组织和管理逻辑文件 ( logical file ) 对高级程序语言的编程人员而言连续的字节构成记录, 记录构成逻辑文件物理文件 ( physical file ) 成块地分布在整个磁盘中文件管理器操作系统或数据库系统的一部分文件的记录无结构, 数据库文件是结构型记录把逻辑位置映射为磁盘中具体的物理位置 12 张铭数据结构与算法

13 文件组织文件逻辑组织有三种形式 : 顺序结构的定长记录顺序结构的变长记录按关键码存取的记录常见的物理组织结构 : 顺序结构顺序文件计算寻址结构散列文件带索引的结构带索引文件倒排是一种特殊的索引 9.2 文件的组织和管理 13 张铭数据结构与算法

14 9.2 文件的组织和管理文件上的操作检索 : 在文件中寻找满足一定条件的记录修改 : 是指对记录中某些数据值进行修改若对关键码值进行修改, 这相当于删除加插入插入 : 向文件中增加一个新记录删除 : 从文件中删去一个记录排序 : 对指定好的数据项, 按其值的大小把文件中的记录排成序列, 较常用的是按关键码值的排序 14 张铭数据结构与算法

15 9.2 文件的组织和管理 C++ 的标准输入输出流类标准输入输出流类 istream 是通用输入流和其它输入流的基类, 支持输入 ostream 是通用输出流和其它输出流的基类, 支持输出 iostream 是通用输入输出流和其它输入输出流的基类, 支持输入输出 3 个用于文件操作的文件类 ifstream 类, 从 istream 类派生, 支持从磁盘文件的输入 ofstream 类, 从 ostream 类派生, 支持向磁盘文件的输出 fstream 类, 从 iostream 类派生, 支持对磁盘文件的输入和输出 15 张铭数据结构与算法

16 9.2 文件的组织和管理 fstream 类的主要成员函数文件指针定位 ; 在当前文件指针位置读取 ; 向当前文件指针位置写入 #include <fstream.h> // fstream = ifstream + ofstream void fstream::open(char*name, openmode mode); // 打开文件 fstream::read(char*ptr, int numbytes); // 从文件当前位置读入字节 fstream::write(char*ptr, int numbtyes); // 向文件当前位置写入字节 // seekg 和 seekp: 在文件中移动当前位置 // 以便在文件中的任何位置读出或写入字节 fstream::seekg(int pos); // 输入时用于设置读取位置 fstream::seekg(int pos, ios::curr); fstream::seekp(int pos); // 设置输出时的写入位置 fstream::seekp(int pos, ios::end); void fstream::close(); // 处理结束后关闭文件 16 张铭数据结构与算法

17 9.2 文件的组织和管理缓冲区和缓冲池目的 : 减少磁盘访问次数的方法 : 缓冲 ( buffering ) 或缓存 ( caching ) 在内存中保留尽可能多的块可以增加待访问的块已经在内存中的机会存储在一个缓冲区中的信息经常称为一页 ( page ), 往往是一次 I/O 的量缓冲区合起来称为缓冲池 ( buffer pool ) 17 张铭数据结构与算法

18 9.2 文件的组织和管理替换缓冲区块的策略新的页块申请缓冲区时, 把最近最不可能被再次引用的缓冲区释放来存放新页先进先出 ( FIFO ) 最不频繁使用 ( LFU ) 最近最少使用 ( LRU ) 18 张铭数据结构与算法

19 9.2 文件的组织和管理思考 1. 查询内存硬盘磁带高速缓存等设备每字节的价格 2. 查询当前主流硬盘的性能指标容量 (G) 磁盘旋转速度 ( rpm ) 交错因子寻道时间旋转延迟时间 19 张铭数据结构与算法

20 第 9 章 9.1 主存储器和外存储器 9.2 文件的组织和管理 9.3 外排序置换选择排序二路外排序多路归并选择树 20 张铭数据结构与算法

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

22 9.3 外排序置换选择排序 22 张铭数据结构与算法

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

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

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

26 for(int last = (n-1); last >= 0;){ mval = H.heapArray[0]; sendtooutputbuffer(input, output, inputfile, outputfile, mval); input.read(r); if (!less(r, mval)) H.heapArray[0] = r; else { H.heapArray[0] = H.heapArray[last]; H.heapArray[last] = r; H.setSize(last--); } H.SiftDown(0); // 最小值 } // for endup(output, inputfile, outputfile); } 9.3 外排序 // 从输入缓冲区读入一个记录 // r 放到根结点 26 张铭数据结构与算法 // last 记录代替根结点,r 放到 last 位置 // 调整根结点

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

28 9.3 外排序扫雪机模型 28 张铭数据结构与算法

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

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

31 9.3 外排序多路归并 31 张铭数据结构与算法

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

33 赢者树与数组的对应关系 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 33 张铭数据结构与算法 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.

34 赢者树的示例第九章 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] 该记录即为下一个要输出的记录到根结点的路径重新进行比赛 34 张铭数据结构与算法

35 B[2] B[1] 9.3 外排序 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 35 张铭数据结构与算法

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

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

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

38 9.3 外排序败方树 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)); 38 张铭数据结构与算法

39 9.3 外排序败方树 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; } 39 张铭数据结构与算法

40 }} 第九章 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) 9.3 外排序 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); 40 张铭数据结构与算法 B[3] B[4] B[5] L[5] L[6]

41 9.3 外排序 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] 张铭数据结构与算法

42 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) { 9.3 外排序 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; } } 42 张铭数据结构与算法 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]

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

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

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

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

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

PowerPoint 演示文稿

PowerPoint 演示文稿张铭数据结构与算法数据结构与算法 ( 九 ) 张铭主讲采用教材 : 张铭, 王腾蛟, 赵海燕编写高等教育出版社,2008 6 ( 十一五国家级规划教材 ) http://wwwjpkpkueducn/pkujpk/course/sjjg 第 9 章 91 主存储器和外存储器 92 文件的组织和管理 931 置换选择排序 932 二路外排序 933 多路归并选择树 2 张铭数据结构与算法