| English
第一次使用 Rust 写相对完整的程序，可能还有很多可改进的地方（求建议qwq）~
为了方便，本次实现处理 unsigned int64 而非 int64。
给定 k 个满足下述条件的有序 unsigned int64 数据块（可看作数组）：
- 所有数值服从 均匀分布；
- 总数据量大致为 1TiB；
需要设计并实现一个将所有有序数据块合并的算法，同时应当尽可能利用多核处理器这一特性，并使用不超过 16GiB 内存。
在当前实现里，k 个数据块被分别存放在文件 0.in, 1.in, ... (k - 1).in 中。为了使观察更加容易，每一个数都以字符串的形式被存储并且以空格隔开。程序会产生结果文件 result.txt。
内存大小有限导致无法将所有数据放入内存处理，此时硬盘 I/O 性能可能成为瓶颈，故需要在理论复杂度与 I/O 次数间做妥协。注意到数据值域相对较小 (0 ~ 2^64 - 1)，因此考虑依据值域进行分段处理。
- 将值域
[0 .. 2^64 - 1]切分成 512 (2^9) 长度相等的段。第i段记作p[i]，且p[i] = [i * 2^55 .. i * 2^56 - 1]； - 对于每一段
p[i]：- 遍历每一个数据块，筛选出所有大小坐落于
p[i]中的数值，将它们存放于数组a[i]中； - 数据服从均匀分布，因此数组
a[i]之间大小相对接近，不太可能超出内存限制； - 采用多线程排序算法对
a[i]进行排序，并插入结果文件末尾；
- 遍历每一个数据块，筛选出所有大小坐落于
- 对于较早的 commit 采用
perf进行性能分析后，发现瓶颈在于筛选时大量的文件 I/O:- 采用
BufReader以带缓冲区的方式读取数据块，以减少所需系统调用次数从而提升读取性能； - 对于每个数据块，读取到大小超出当前段的值时即停止读取（因此会将第一个大于当前段的值缓存在内存里），下一次读取该数据段时会从该位置继续读取，从而保证在筛选这一步每个值只会被读 O(1) 次。
- 采用
- 对于筛选步骤，另一个等价的做法是首先为每一个段在硬盘上创建一个文件。接下来遍历每一个数据块，对于每一个数据计算其应当位于那一段，并将其写入对应的文件。
- 优点：相比当前做法，不需要将每一数据段的候选值缓存于内存里。因此能更好应对数据段数量极大（甚至以至于候选值无法被放入内存），而每一个数据段大小极小的情况；
- 缺点：当数据量较小时可能引入大量随机写（相比随机读可能带来更大开销），但是数据量较大时由于均匀分布，可能多个连续的值都会属于同一段，如果再辅以
BufWriter以带缓冲区的方式进行文件写入可能不会带来太大影响。 - 实现：若数据段数量较小则采用前文所述方案，若数据段数量较大则采用本节所述方案。
- 如果数据不满足均匀分布？
- 算法一：若依然采用与前面类似的想法，可考虑借助二分确定每一段的大小。但这会对每一个值带来 O(klogn) 次额外读取操作，可能会较显著影响性能；
- 算法二：将合并两有序数组的双指针算法进行推广。
- 步骤：
- 选取块大小
s； - 在内存中维护一个大小为
k * s的小根堆； - 将每个数据块的前
s个元素读入并放入小根堆； - 记录
num[i]代表第i个数据块目前有多少元素处于小根堆内，故此时对于所有 i 都有num[i] = s； - 每次从小根堆堆顶取元素写入答案文件。记该元素来自数据块
i，若发现num[i] == 0，则应从该数据块中调入接下来的s个元素放入小根堆； - 循环操作直至小根堆为空。
- 选取块大小
- 分析：
- 选取合理的
s主要是为了避免过度碎片化的读取，但若数据块数量极大，s将不得不取非常小的直（可以以 O(logn) 的额外代价分治解决）； - 采用小根堆处理的过程难以使用多线程加速（可能会涉及复杂的互锁问题）。
- 选取合理的
- 步骤：
采用如下指令进行编译：
cargo build --release接下来在项目根目录下创建数据块。将他们命名为 0.in, 1.in, ..., (k - 1).in。每一个文件包含以空格隔开的若干 unsigned int64 数字。采用如下指令运行程序：
cargo run <数据块数量>结果将会被存放在位于项目根目录的 result.txt 文件里。