一、问题描述
分组问题，即将原始数据按照某种标准划分成不同的组别，分组后的的数据称
为分组数据。分组问题最常见的应用是 SQL 查询的 Group-By 操作。其中，常见
的解决方法主要有三种：1、基于归并排序的分组。2、基于分段计数分组法的分
组。3、基于哈希表法的分组。传统串行的解决方案已经无法满足日益增大的数
据量的需求，因此并行化解决分组问题是目前需要研究的对象，其中对传统方法
进行并行化就显得尤为关键。
二、求解方法
本次大作业采用之前实现的 PSRS 算法解决分组问题。分组问题可以用排序的
方式进行解决，虽然分组问题并不要求分组后的数据是有序的状态（如哈希实现
方式），但是排序方法却能够解决分组问题，因为排好序之后数据相当于已经按
照大小值划分好了组别，因此能够解决分组问题。
本次作业首先使用 PSRS 算法对大规模数据进行排序，由于内存无法装下如此
大量的数据，因此只能使用外部排序的方式，每排序好一个顺串就产生一个中间
文件，最后对所有数据进行排序后使用归并的操作记录每个数据的分组号以及数
据的数量即可。
这种求解方案依赖于排序操作，依据相关文献的说明，理论上来说并行化的基
于哈希表的分组应该是最快的操作，因为它不要求全局有序，并且只要依据哈希
函数找到数据相应的位置即可完成分组。
三、实验结果截图及性能分析
(1) 实验环境说明：
本次在天河二号上进行的实验，经验证，天河二号节点的运行内存为 64G 左
右，可以使用的硬盘空间为 1000G，由下图所示可以查到天河二号支持的线程总
数为 64，核心数量为 8，物理 CPU 个数为 4 个。
(2)采用串行方式实现的运行时间
测试数据集说明：本次使用的数据集为 64 位的 int 类型数，数据个数为 2G 个数，
总大小为 16GB 大小。
在使用单进程、单线程(即假设只有一个主机)，使用排序算法实现分组问题的解
