geelaw
2024-02-15 17:10:29 +08:00
第一个问题就是你是否有足够的磁盘空间,如果有的话,完全可以先排完序再说。
假设你使用 64 位操作系统,先分别排序两个 csv ,这样做:
1. 把 x.csv 映射到虚拟内存。
2. 扫描一次,计算行数 n 。
3. 建立一个长度是 8n 字节的文件 x.dat ,映射到内存,把它看成长度是 n 的 uint64 数组 index 。
4. 扫描 x.csv ,在 index[i] 放置第 (i-1) 行开始的位移。
5. 对 index 的元素 z 按 x.csv 从 z 处提取出的字符串升序排序。
6. 保存 x-sorted.csv 。
上述操作需要 O(n log n) 的时间。
然后同时把 a.csv, a.dat, b.csv, b.dat 映射到虚拟内存,并用有序合并算法计算需要的三个结果,这需要 O(n) 的时间。
额外的磁盘空间复杂度是 O(n),具体来说,显然不会超过 20 GB 。