数据结构与算法课件第8章

1、A Practical Introduction toData Structures and Algorithm Analysis n外排序：因数据量太大，不能将它们同时放在主存中。因此需要将全部数据放入磁盘，每次选择部分数据到主存进行处理。8.1 主存储器和辅助存储器 主存储器：随机访问存储器（RAM）。 辅助存储器：硬盘、软盘和磁带等。 主存储器和辅助存储器的比较主存储器和辅助存储器的比较主存储器辅助存储器价格昂贵（高两个数量级）便宜存储时间易失长期便携性不具备具备读写速度快（10100万倍）慢容量小大尽可能减小对磁盘的访问次数原则尽可能少（最好一次）的访问次数得到所需数据。u 每次磁盘访

2、问得到更多的数据，减少将来的访问需要。一种实用的方法：压缩存储存储在磁盘中的信息。 原理： 用增加的CPU时间（压缩和解压数据）换 取缩短的磁盘访问时间。 问题：不允许随机访问被压缩文件的一部分。磁盘：直接访问存储设备。磁带：顺序访问存储设备。盘片、磁道、柱面、扇区盘片以恒定速率转动u每个磁道分为多个扇区。u每个扇区有相同的数据量。一个扇区是一次读出或写入的最小数据量。寻道：移动硬盘的I/O磁头，定位到包含数据的磁道。（慢，占据读写数据的大部分时间）u 等待包含数据的扇区旋转到磁头下面。u 读取或写入一个扇区的数据。安排扇区的交错法：引用的局部性：如果读出文件的一个扇区，很可能就要读出文件的下

3、一个扇区。（假设）簇：多个扇区组成，为文件分配的最小单位，大小由操作系统所定。文件分配表：记录哪些簇（扇区）属于哪一个文件。范围：一组物理上相连的簇。内部碎片：由于数据没有填满一个扇区或一个簇而浪费的存储空间。访问磁盘中信息的主要代价一般是寻道时间。寻道时间依赖于磁头当前所在的磁道与将要访问的目标磁道之间的距离，因此实际寻道时间差别很大。寻道时间可参考的两个参数：磁道磁道代价：磁头从一个磁道移到相邻磁道的最短时间。一次随机访问的平均寻道时间。其它磁盘访问代价：等待目标扇区旋转到磁头下的时间。 数据读/写时间。 例8.1，读取数据的时间代价： 一个磁道（256个扇区）： 一个扇区（512个字节）

4、：9.5+11.1/2+(1/256)11.1=15.1ms 一个字节： 9.5+11.1/2 = 15.05ms读取的数据量对读取时间影响不大。因此磁盘驱动器每次都是读入或写入整个扇区的数据。数据暂放在主存中，称缓冲或缓存。缓冲：从磁盘中取出多余数据，以满足将来的请求。缓冲技术可以减少数据从磁盘中读取的次数。主存中通常建有多个输入缓冲区和输出缓冲区，缓冲区合起来称为缓冲池。39.5+11.1/2311.148.4ms9.5+11.1/211.126.2ms交错因子为扇区不交错当缓冲池填满后，替换缓冲区的方法： 先进先出法。 最不频繁使用法。 最近最少使用法。虚拟存储技术：将磁盘扩展为主存的一

5、部分。处理磁盘文件中记录的方式： 随机访问。 顺序访问。外部排序的特点： 只能先将一些记录从磁盘中读出，进行排序，再将记录写回磁盘。 主要目标：尽量减少磁盘访问。 在主存内的内部排序比读写磁盘的时间少。顺序访问磁盘中数据块比随机访问更有效。但高效率的顺序访问要求： 文件应填充到连续的磁道中。 顺序访问过程中，磁盘的I/O磁头要始终在这个文件上，因此不同时处理两个文件。 只对关键码排序，建立索引文件，而不是对整个记录排序。内部排序算法通常不适用于外部排序，如快速排序。一种较好的外部排序算法：改进的归并算法将被排序的子序列称为顺串（run） 排序过程（P181） 对有n条记录的文件，外部归并排序需

6、要logn趟扫描，即每条记录进行logn次磁盘读写。对外部归并排序算法的改进：对小的顺串不做归并排序。即对读入主存的数据做内部排序，并读入尽可能多的数据，减小归并排序的趟数。 每一趟扫描归并多个顺串，即多路归并技术。 所有好的外部排序算法都是基于： 把文件分成大的初始顺串（读入更多记录到主存，执行内部排序）。 把所有顺串归并在一起，形成一个已排序的文件。堆排序算法的一个微小变体。如果分配给供内部排序数组的可用主存大小是m条记录，可创建2m条记录的顺串。置换选择排序的过程：在可利用的内存中构建一个数组（堆）、一个输入缓冲区和一个输出缓冲区。 从磁盘上读取记录填充数组。 构建一个最小值堆。设Last = m-1，m为数组大小，Last标识堆