两阶段多路归并排序
Two-Phase Multiway Merge-Sort
实验报告
目 录
1 实验目的............................................................................................................................... 4
2 实验内容............................................................................................................................... 4
3 实验环境............................................................................................................................... 5
4 实验的设计和实现................................................................................................................5
4.1 算法描述........................................................................................................................ 5
4.2 设计思路........................................................................................................................ 6
4.3 数据结构........................................................................................................................ 7
4.4 具体实现........................................................................................................................ 8
4.4.1 Generate Record File 阶段.......................................................................................8
4.4.2 Phase1 阶段.............................................................................................................9
4.4.3 Phase2 阶段...........................................................................................................10
5 实验结果............................................................................................................................. 12
5.1 50MB 内存 TPMMS 实验结果......................................................................................12
5.2 10MB 内存 TPMMS 实验结果......................................................................................13
5.3 100MB 内存 TPMMS 实验结果....................................................................................14
5.4 三者的比较..................................................................................................................15
6 实验遇到的问题和解决方法..............................................................................................16
6.1 Phase2 阶段遇到的问题和解决方法...........................................................................16
6.1.1 读完某个子记录文件后，输入缓冲的填充方法.....................................................16
6.1.2 读完所有子记录文件后，处理最后一组输入缓冲数据的方法.............................17
6.2 生成子记录文件名的方法...........................................................................................18
7 代码附录............................................................................................................................. 19
1 实验目的
通过 merge-sort 算法的实现，掌握外存算法所基于的 I/O 模型与内存算法基
于的 RAM 模型的区别；理解不同的磁盘访问优化方法是如何提高数据访问性
能的。
2 实验内容
生成一个具有 10,000,000 个记录的文本文件，其中每个记录由 100 个字节组
成。实验只考虑记录的一个属性 A，假定 A 为整数类型。记录在 block 上封装
时，采用 non-spanned 方式，即块上小于一个记录的空间不使用。Block 的大小
可在自己的操作系统上查看，xp 一般为 4096 bytes。在内存分配 50M 字节的空
间用于外部 merge-sort。要求设计和实现程序完成下列功能：
1) 生成文本文件，其中属性 A 的值随机产生。
2) 按照 ppt 中的方法对文本文件中的记录，按照属性 A 进行排序，其中在
第二阶段的排序中每个子列表使用一个 block 大小的缓冲区缓冲数据。
3) 按照教材 cylinder-based buffers(1M bytes)的方法，修改第二阶段的算法。
4) 比较两种方法的时间性能，如果有更大的内存空间，算法性能还能提高
多少？
3 实验环境
1) Visual C++ 6.0
2) Windows 7 操作系统
4 实验的设计和实现
4.1 算法描述
Two-Phase Multiway Merge-Sort 算法的具体描述分为 2 个阶段，如下所示：
Phase 1
1) Fill main memory with records.
2) Sort with favorite main memory sorting algorithms.
3) Write sorted list to disk.
4) Repeat until all records have been put into one of the sorted lists.
Phase 2
1) Initially load input buffers with the first block of their respective sorted
lists.
2) Repeated run a competition among the first unchosen records of each of
the buffered blocks.
3) If an input block is exhausted, get the next block from the same file.
- 1
- 2
前往页