基于External merge-sort的大文件字典合并高效算法咨询

你当前的暴力扫键合并方式效率低是因为每个键都要遍历所有临时文件，完全是做无用功。直接用排序+多路归并的思路，这是处理这类大文件合并的标准解法，落地起来也不难：

第一步：先给每个Partial Dict做排序预处理 #

每个Partial Dict本身是控制在1MB以内的，完全能塞进内存：

• 把单个Partial Dict读进内存，按键的整数大小从小到大排序
• 把排序后的键值对存成新的临时文件，比如sorted_part_0.txt，每行格式就用键\t行号列表（比如456\t2,7,11），方便后续逐行读取

第二步：用多路归并把所有有序文件合并成最终字典 #

核心是用最小堆来跟踪每个有序文件的当前最小键，避免重复扫描：

1. 给每个排序后的临时文件开一个逐行读取的“指针”，先读第一行，把(当前键, 文件指针, 当前行号列表)放进最小堆里（堆按键的大小排序）
2. 循环到堆空为止：
   • 弹出堆顶的最小键条目
   • 检查堆里有没有其他相同键的条目，全部弹出来把行号列表合并到一起
   • 把合并后的键值对写入最终结果
   • 从弹出条目对应的文件指针里读下一行，如果还有内容，就把新的(键, 文件指针, 行号列表)再放进堆里

额外提几个能提速的小技巧 #

• 分桶并行跑：如果知道整数键的范围（比如都是0到1e9），可以提前把每个Partial Dict里的键按区间分桶（比如每10万个键一个桶），每个桶单独存成子临时文件。之后可以同时合并多个桶的文件，榨干多核CPU的性能。
• 行号列表压缩：存临时文件的时候，把连续的行号用差分方式存（比如1,2,3存成1,3，意思是从1开始连续3个），能大幅减少磁盘读写的数据量，速度会更快。

效率对比 #

原来的方法是O(N*M)（N为总键数，M为临时文件数），每个键都要扫一遍所有文件；优化后是O(K log K + K log M)（K是所有Partial Dict的总条目数），速度提升不是一点半点，数据量越大差距越明显。

内容的提问来源于stack exchange，提问作者ealione