超大型文件比较，内存不足，只能分页读区再匹配，但头都秃了，也没想到优化的方式，朋友们帮帮忙啊。

有两个本地文件，PersonListA.csv 和 PersonListB.csv ，文件过于巨大，我需要分批读取到内存里，变成 List<Person> A 和 List<Person> B ，我现在要把 A 和 B 进行对比，获得下面结果：

Person 有两个属性，一个 Name ，一个 Age ，Name 是唯一的，但两个列表中相同 Name 的人 Age 不一样

1 ，找出存在于 A 但不存在于 B 的元素。

2 ，找出存在于 B 但不存在于 A 的元素。

3 ，找出两个列表中不同的元素。

有以下限定条件：

1 ，本地文件过大，无法一次性读取到内存中，需要分页进行比较。

2 ，无法对两个列表进行排序，数据在列表中都是乱序的，需要用 Name 进行匹配。

如果要实现以上 function ，需要用到什么算法，请分析后给出算法的名称。

现在的策略是，把 A 中的数据分为 10 组 10 条，然后把 B 中的数据分为 10 组 10 条的数据，分别拿 A 中的每一组数据和 B 中的每一组数据进行比较，这个方法叫做 GetUniqueResult

1 ，在找到只存在 A 不存在 B 的元素调用一次 GetUniqueResult 。

2 ，在找到只存在 B 不存在 A 的元素调用一次 GetUniqueResult 。

3 ，在通过 FindDiffer 找到 A 和 B 中不同的元素。

相当于我需要循环 3*(10^10)次才能结束，其中也有使用 HashMap 来进行优化，使得实际执行次数小于 3*(10^10)次。（比如 A 中的第一组数据在和 B 的所有数据比较时，如果第一组的所有数据都找到了，就提前结束。）

我现在想问的是，有没有什么更好的算法能从 3*(10^10) 优化到 (10^10)，如果能跟优化到 N （ 1 ）

有没有什么方法能只对调用一次 GetUniqueResult ，获得全部结果。

-----------------------------------------------

浓缩版：

我有两个本地 FileA.csv 和 FileB.csv ，分别存储了从 Oracle 中和 PostgreSQL 导出的同一个表。

1 ，单个文件超过 10GB ，无法一次性读取到内存中。

2 ，两个导出的文件是乱序的，需要用主键在程序里进行数据匹配（文件无法修改）。

需要获取结果：

1 ，在 A 中存在，但 B 中不存在的数据。

2 ，在 B 中存在，但 A 中不存在的数据。

3 ，在 A 和 B 中都存在，但有差异的数据。

可以有什么办法吗？或者给我一些算法关键字，比如我现在使用的是类哈希分页对比。

geelaw

350 天前

第一个问题就是你是否有足够的磁盘空间，如果有的话，完全可以先排完序再说。

假设你使用 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 。