Nine freshmen's project which can sort 120G data of strings.
Created By D22小组
欢迎大家自己实验，可以自己创建一个新文件，用来存放自己代码做实验，也欢迎修改代码进行补充（记得做好备份）
- 全流程代码由Java编写，无其他语言调用，代码总量968行，我们还尝试了其他语言的代码实现
- 单台主机24G数据读入耗时130秒、分段排序20秒、归并排序30秒，单台主机总耗时3分钟
- 多主机协同处理120G数据传输归并输出同时进行共8分钟，项目总耗时11分钟
- 内存占用：客户端平均占用16G，峰值占用20G；服务端平均占用20G，峰值占用28G
- 总数据交换机传输总量48G（可继续优化至36.12G），传输速度跑满带宽1000Mbps
- 120G数据全流程完成完整测试4遍，平均测试耗时11分钟
- 通过对4G有序数据的分割打乱后，经多主机协同归并测试后与源文件校验值相同，多次更换方式校验测试了系统正确性
该项目使用多线程方式对数据进行排序。具体实现步骤如下：
- 首先多线程读取文件，并将数据分块分桶读入内存，每块读取的数据存储在一个二维列表中。
- 对每个数据块中的数据进行排序，使用Java内置的sort排序算法。
- 将排序后的数据块进行多线程两路归并排序，反复归并至只剩下一个数据块。
- 4台客户端将归并得到的数据块发送给指定的服务器端口。
- 1台服务端接收数据，并将接收到的数据存储到对应的桶中。
- 服务器端同时将本地数据从线程数据块中转移到桶数据块内存区域中。
- 对桶数据块进行多路归并排序，直到所有桶的数据都归并完成。
- 在归并的同时将归并得到的数据按要求保存到文件中，同时释放已保存区域堆内存。
[√]请教学长：有机会或者资源的建议问一下上一届他们这个正确率方面和时间方面是怎么会有如此奇怪的结果的 （结果不是大数据大一小学期，sad（）[√]代码优化：目前实现的效果还是只能说差强人意，大家有能力的希望尝试将 std 里面的 stable_sort 以及 tim_sort 尝试用结构体复现出来，这样应该会大大提速项目效率[√]查阅案例：咱们根据最终的环境，找出一种实现效率最高的总体统筹算法，包括但不限于多线程、多台主机进行归并的方法等，比较重要的是数据怎么存储、怎么切分、怎么传输，查完可以写在文档中或者发在群里[√]语言转换：老师重新申明题目要求，将数据整体转换为Java语言，并完成jvm与GC优化[√]架构优化：目前效果还不错，但是可以优化架构继续减小时间、传输量
- 传输开销小才是真的节省时间！传输开销大概占到程序总时间的 80%，所以降低传输量是关键！
- TimSort 这种排序算法可以查一下网上的解释，大概就是采用希尔排序与归并排序进行融合，我目前采用的 timsort 函数方法据说要再编译器中开
-O3编译优化才能很快，实验发现，对于存在少部分有序的数据，timsort 效率较 stablesort 高。 - 使用自己实现的结构体可以加快排序的操作速度，（应该是减小了内存的复制量与内存地址不对齐的问题）
目前我们的排序是使用 .\JavaSort\MainClientSender.java与MainClientServer.java，并且打开-Xms24G -Xmx28G的Jvm参数，速度是相对来说比较快的，包含压缩包解压总时长13分钟
| 文件名 | 简介/速度/性能 | 描述 |
|---|---|---|
| ./src/ | 该文档资源文件夹 | 一些图片等样例 |
| ./JavaSort/MainClientSender.java | 4台服务端主机代码 | 原理同MuiltySortModify.cpp，调用了定义的long线性表类LongArray，增加了sendData方法 |
| ./JavaSort/MainClientServer.java | 1台服务端主机代码 | 原理同上，调用了定义的long线性表类LongArray，同时还增加了收发、归并、保存等方法 |
| ./generate.cpp | 随机字符串生成 | 用来生成随机字符串，成功实现了多线程输出，能够跑满硬盘读写速度 |
| ./SplitAndShuffle.cpp | 顺序数据打乱并分割小文件 | 用来将顺序文件数据读入、打乱、分割为5个数据段，多线程保存，用来实现数据的分割检验 |
关于过往的排序算法我们主要是使用Cpp完成单台数据的排序，而经过项目要求调整后，我们将Cpp项目转换为了Java语言进行编写，但是单台排序算法仍然思路与MuiltySortModify.cpp基本不变
| 文件名 | 简介/速度/性能 | 描述 |
|---|---|---|
| ./MagicCUDA/ | 显卡 CUDA 排序程序 | 它有点逆天的快（ ,基于显卡的排序算法，有点高端我这种凡人难以修改 |
| ./UDPTransport/ | UDP 通讯的测试 | 存放着 UDP 通讯的测试，本地电脑测试的结果是，每秒钟传输 150M/s，错误率为 0%（也就是传输数据一般直接 UDP 传输应该不需要校验位进行校验） |
| ./Python/ | Python简单实现的算法 | 存放着 Python数据（以及帮助其他组调试用的数据（D22组内鬼hhh） |
| ./tim/ | TimSort 支持库 | TimSort 排序的支持库，大致原理是把希尔排序与归并排序结合起来，需要使用-O3 编译优化 |
| ./MuiltySortModify.cpp | 232M/s总共，内存占用最小 |
基于 STL vector 将数据根据前两个字母分块存储在 long long 中 使用 vector 容器 与 tim_sort，同时将数据分块多线程读取，最后归并处理，速度大约为单个 CPU232M/s，24G/87s，打开-O3 优化 |
| ./MuiltySort.cpp | 133M/s总共，很快 |
基于 STL vector 自定义数据类型 容器实现的 stable_sort 与 tim_sort，同时将数据分块多线程读取，最后归并处理，速度大约为单个 CPU133M/s，1.6G/12s，打开-O3 优化 |
| ./SortString.java | 32M/s单线程，较慢 |
基于 Java String 列表调用官方默认的 TimSort 方法，速度大约为多线程 160M/5s（暂时弃用） |
| ./SortStr.cpp | 64M/s单线程，可以 |
基于 STL vector 自定义数据类型 容器实现的 stable_sort 与 tim_sort，速度大约为单线程 64M/1s，1.6G/25s，打开-O3 优化 |
| ./SortString.cpp | 26M/s单线程，最慢 |
基于 STL vectorstd::string 容器实现的 stable_sort 与 tim_sort，速度大约为单线程 26M/s，160M/6s，打开-O3 优化（暂时弃用） |
欢迎大家积极尝试（可以直接 GPT 生成代码自己调试）:
[√]实现多线程操作，从而完整调用多核性能，并可以想一下归并的思路[√]想出新的排序架构，让多台电脑尽可能减少 120G 数据的传输量，同时不要让内存占用过高[√]利用那位学长的思路，修改结构体，压缩传输数据量（修改为1 个 short + 1 个 long） short 2 字节 (26 * 26 = 676) + long 8 字节 (26 ^ 13 = 2.48e+18 < LONG_MAX)[√]将 STL 的 vector 容器改为直接的结构体数组操作，这样可以加快排序迭代与内存分配的效率（效果可能不大）[ ]使用特征传输的功能，将最后的传输大小优化为36.12G(详见PPT)
./数学实践D22.pptx汇报PPT./CodeDocs.md代码说明文档