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

[FeifeiJin]

有两个本地文件，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 中都存在，但有差异的数据。


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

1 ，附加条件，不允许排序。（附加这个条件是因为，其实使用外部排序+归并算法可以解决上述问题）


但已经写了巨多的代码，不想去外部排序用新的文件进行比较了。

换而言之，现在只能屎上雕花，自己的💩自己雕。呜呜呜

[FlytoSirius]

我的第一感觉是, 这个事情应该导入的数据库表里再进行相关操作,
写程序对比不是最佳方案.

10GB 单表在数据库里也不算多大.

你要的那三个比较结果在 SQL 里都是很容易得到的.

[hefish]

我觉着 ls 的大佬说的对，放 mysql 里就完事了。

[FeifeiJin]

@FlytoSirius
@hefish
宝，很感激你们的回复。

因为现在的目的就是用外部程序去验证两个数据库中的数据是否完全一致，且有种种条条框框加成下，只能用程序去读 CSV 去验证哈。

[min]

买内存条啊

[FlytoSirius]

@FeifeiJin
那能不能程序直接连接 两端数据库进行对比呢? 毕竟导出这样的两个数 GB 的大表是个容易出问题的过程.

但, 如果就得用程序去对比文件, 那确实要花点时间研究下具体实现.

[FeifeiJin]

@FlytoSirius 真的不能。

[FeifeiJin]

@min 谢谢您的回复。

[Nosub]

如果是 Java 可以试试阿里的 easyexcel ，https://github.com/alibaba/easyexcel

[me1onsoda]

允许误差的情况下，布隆过滤器可以满足 12

[ck65]

前阵子有个 1 billion row 挑战，OP 可以参考一下看有没有帮助

- https://1brc.dev
- https://mrkaran.dev/posts/1brc/

[leonshaw]

那就用 sqlite

[FeifeiJin]

@Nosub
@me1onsoda
谢谢，但是这边用的是 C#。

布隆过滤器我正在看，大概率是不允许误差。

[FeifeiJin]

@ck65
我觉得有帮助，我看一看。

就算不能解决我的问题，也能从里面看到很多思路。

[FeifeiJin]

@leonshaw 宝，谢谢。但不能。

[ipwx]

大概有多少条数据。

数据条数不多（千万级别）但是每一行的列多的话，可以考虑先扫一遍两个 csv ，记录一下每一个 csv 里面 name 和 file byte offset 的对应关系。然后在内存里面根据 name 进行你的几个操作，最后根据记录下来的 offset 从 csv 里面重新读出来对应的 Person 。

[leonshaw]

@FeifeiJin 为什么不能？

[geelaw]

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

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

[Nosub]

@FeifeiJin 即便如此，我觉得 c#程序员去用这个库，也没有问题，建议你试试看，写个命令行程序就可以了，不试试怎么知道行不行，这个库肯定解决了你的读取问题了。

[lrjia]

可以把 name 分组，比如先把两个文件中所有 a 开头的行读入内存比较，然后再比较 b 、c 。分组粒度大小按照内存大小来。

[FeifeiJin]

@geelaw
谢谢您， 这个方法是行得通的。目前不想外部排序，实在走不通，再走这条路。

[matrix1010]

用不了数据库但你可以参考数据库的做法： https://dev.mysql.com/blog-archive/hash-join-in-mysql-8/

[laike9m]

@FeifeiJin 没看出为什么不能

[mayli]

@laike9m 因为就故意想要吃屎，有靠谱的简单解法不错，非得要屎上雕花。
这玩意随便弄个数据库建个索引就跑就完事，还用费这劲。而且，才 10GB 的文件，也不算大啊。实在不行租台 r3.xlarge 一小时 $0.350 ， 一下子就出来了。
实在没钱，放 sqlite 里，做个 index, page_cache 有多少给多少，就硬算就完事.

[dswyzx]

感觉你还是要把思路打开.db 用 sqllite 也不重.但只要数据脱离 csv 到 db 里.想怎么玩不就都好说了,与其在一个旧代码里想办法优化,不如开个新的项目吧.如果说是开发流程或者规范不允许再 csv 写入其他地方,那你首先要做的是找领导反馈协调.而不是在这里屎山雕花

[rocmax]

先用 A 做一个字典树，然后遍历 b 去查？

[rocmax]

@rocmax 这样找不到 a 里有但 b 里没有的，除非反过来再来一次

[testFor]

@rocmax 感觉你的回答最靠谱也相对简单,名字应该重复的概率很高,内存占用不多,把年龄挂在最后一个节点就完事了.然后每天跑一次,存缓存结果,存不下就数据分段

[testFor]

@rocmax 找一次就可以拿到三个结果

[rocmax]

如果做两棵字典树，然后各自用一个指针同步遍历可不可以同时找出两个树缺失的部分？毕竟可以按字母序遍历，一边缺了另一边就等着，赶上来了再同步走，同时记录差异

[rocmax]

@testFor 可以吗？ a 并没有遍历过啊

[rocmax]

@testFor 标记叶子节点然后统计没有查过的叶子？

[testFor]

@rocmax en,搜索过程给点反馈就能一次遍历产生三个结果. 1.有没有完全匹配 2.完全匹配年龄是否相同

[testFor]

@rocmax 或者就是两个文件进行外部排序,然后在进行头对比,就是你上面的那种等待,不过名字应该重复率挺高的,应该不如字典树省内存和效率高

[antipro]

@testFor 对，给 person 加个 Mark 属性，默认为 0 ，从 A 中分块并发到 B 中比对，一次出两个结果，对上了 mark=1,全结束后从 B 中取出 mark=0 的，就是 B 有 A 没有的。

[nbndco]

这件事的正解就是排序，无非是你自己拍，还是数据库帮你排的区别。

当然你有特殊癖好那就不在考虑范围了

[fairytale]

要么排序，要么分组。sum(name)%8 每个余数过一遍。

[fairytale]

其实 hashmap 也是一种排序，你不允许任何形式排序那就只能(10^10)∧3

[kisick]

做过一模一样的事情，解法是把两个数据库里的数据都抽取一份到第三个数据库里，在第三个数据库里通过 sql 比较

[67373net]

能不能说下为什么不能用 sqlite ？爬完了也没看明白。。

[wangritian]

兄弟，看一眼内存的价格

[luyifei]

建议重点复习一下数据库 sort merge join 和 hash join 的实现，你说的这些问题在数据库领域是已知问题

[ashong]

1 、导入 sqlite 处理再导出
2 、内存映射

[tool2d]

排序挺方便的，但我觉得内存也不贵，买个 64G 内存，足够处理两个 10G 文件了。

[SuperXX]

DuckDB 试试看

[cybort]

可以对每条数据做一个 hash ，hash 后的数据量小于原始数据，这样相当于对两个较小的文件进行操作，找到了再去原文件校验一下。

[cybort]

数据库可能楼主没有权限去访问。机器也不一定在他手里。

[clorischan]

全部读取到内存中.
数据结构可以用前缀树进行存储 Name 属性.
Tree Node 值就是 Age,
2 个 10G 文件使用前缀树全部载入内存使用应该不会超过 4G.

要是内存还有空余可以给 Node 在多加个 bool 属性标识是否已比较过.
这样在 A in B 遍历查找时, 在 B 中标记已比较过的数据,
再进行 B in A 反向查找时跳过已标记数据.

还可以进一步优化, 只载入 A 文件到内存.
B 文件直接用异步文件流一条条读取.
读取一条立即在 A 中查找, 并标记该条数据.
这样 B 文件读完一遍直接就的得出 在 B 不在 A, 以及差异数据.
然后再遍历 A, 没有标记的数据就是 在 A 不在 B 中的数据

[Soras]

你这不直接放数据库里。。。。

[lance6716]

可以找一下数据库各种 join 算法，自己造轮子。不过有这功夫直接安装导入跑 SQL 都跑完了。别满脑子都是技术，怎么解决问题怎么来

[yangyaofei]

读一遍,形成一个类似索引的缓存.

缓存内容类似于 B+树, 用 1K(1M 也行)的 hash, 所有的数据都可以用类似于 取模(取余) 1K 的方式映射到下层节点里面, 递归去做直到下层节点为 1. 这样, 每个数据都可以对应到一个节点上. 然后就是比拼读取速度的时候了.

前几层应该可以放在内存里面, 甚至除了最后两层都可以放进去.

当然再写下去就变成数据库了.

[ccde8259]

Flink CDC -> Hive -> HSQL……
写代码的成本不如直接租云服务直接跑完了

[shuimugan]

你这个不叫本地文件过大，这个叫本地内存太小。我以前都是在公司丢一台 128G 内存台式机干点数据处理的脏活累活，你这个场景分分钟就搞定了

[XiaoFaye]

现在的年轻人都不知道 MMP 了？

[XiaoFaye]

修正：现在的年轻人都不知道 MMF 了？

[ryd994]

不许排序是什么奇葩要求？

那就不能导入数据库啊，数据库索引不算排序？
那就不能用 hashmap 啊，hashmap 对数据计算 hash ，hashmap 本身就是对 hash 的排序啊

坚持要处理无序数据，On^2 慢慢对呗，呵呵

[MetroWind]

调试屎山啊，加内存是最快且最便宜的方法。

[hyperbin]

建个 SQlite 数据库文件，用完就删

[xy629]

你面临的问题是处理两个非常大的数据集，并且需要找出它们之间的差异。这里有几个关键点需要考虑：

数据集过大，无法一次性加载到内存。
数据是无序的。
你需要比较两个数据集并找出存在于一个数据集而不在另一个中的元素，以及两个数据集中存在差异的元素。
你目前的方法是将数据分成多个小块（每块 10 条记录），然后使用类似哈希表的结构来进行比较。这种方法是可行的，但是效率较低，因为你需要多次读取和比较数据。

为了改进这一过程，可以考虑以下几种算法或方法：

1. 外部排序和合并
考虑到数据量大且无序，可以使用外部排序算法先对两个文件分别进行排序，然后再进行比较。外部排序是一种用于处理大量数据的排序算法，它会将数据分成多个块，分别排序后再合并。排序可以基于主键（这里是 Name ）。排序后，你可以逐个比较两个文件的记录，以找到差异。

2. MapReduce
如果你有权限使用像 Hadoop 这样的分布式处理系统，MapReduce 可能是一个好方法。MapReduce 能够处理大量数据，通过将任务分发到多个节点来并行处理，从而提高效率。在 MapReduce 中，你可以在 Map 阶段读取和标记来自两个不同文件的数据，在 Reduce 阶段进行聚合和比较。

3. 数据库导入和查询
鉴于数据源来自 Oracle 和 PostgreSQL ，另一个方法是将这些数据导入一个数据库，然后使用 SQL 查询来找出差异。数据库对于处理大量数据以及提供高效的查询和比较操作非常有效。你可以使用 JOIN 查询或者 EXCEPT 查询来找出差异。

4. 流处理
如果你能流式地处理数据（逐行读取而不是分块），可以在读取的同时进行比较。这可以通过使用类似哈希表的结构来实现，但是需要对内存管理进行更精细的控制。

关键词和概念
外部排序：处理无法全部放入内存的大数据集的排序方法。
MapReduce：一种分布式数据处理模型，适用于大规模数据集的处理。
数据库操作：使用 SQL 和数据库管理系统进行高效的数据查询和比较。
流处理：实时处理数据流的方法，适用于连续的数据输入。
根据你的资源和环境，可以选择最适合你情况的方法。如果你正在使用的环境（如特定的编程语言或框架）有限制，请告诉我，这样我可以提供更具体的建议。 -- from chatGPT

[levelworm]

我琢磨着用命令行工具行不行。。。

[bluekz]

AWK 应该就行把，几个 G 的我是整过的

[HanMeiM]

其实不需要这么麻烦，先对两个文件进行排序，产生两个新的文件
新文件的排序规则是：把相同名字的人放在同一行，这样两个文件相当于变成了两个 map ，再逐行遍历 A 、B 两个文件并读取当行数据做比较
我说的比较笼统，希望你能明白这个思路

[HanMeiM]

哦，没看到不能用排序。但是我说的方案时间复杂度基本上是 O(n)，空间复杂度也不会增加多少，可以考虑下

[ychost]

内存条很便宜，2*32G 才 500 块

[FeifeiJin]

@matrix1010 谢谢，我目前采用的是这个思路，不过我是从磁盘每次加载到内存里，它是暂存到磁盘。不过读完还是颇有收获。

@SuperXX ashong @laike9m @dswyzx @mayli @kisick @67373net 总是有特殊条件影响下不能用第三方数据库，或者说本身做的事情就是去验证数据从 Oracle 里导入 PostgreSQL 是否一致，这个验证的意思是一个字节都不差的一致，空格半角全角都得一致，如果再倒入其他数据库，也解决不了我根本想要验证的问题。

@ychost @wangritian @tool2d 这不是内存价格问题，我还可以直接辞职呢，no defence

@luyifei 谢谢，兄弟。说到底其实我就是自己类实现了这部分东西。

[AItsuki]

保持原来方案，但是思路换一换，10 组数据两两剔除相同元素。后续需要处理的数据量会越来越小。这样可行不。

[noparking188]

你们没有数据开发吧，这思路太后端了

OP 的最终需求就是校验 Oracle 迁移到 PostgreSQL 的数据，给了两个 CSV 是不能连数据库？

考虑以下点：
1. CSV 作为两边数据源的中间缓存，两边库导出的 CSV 就是错的，特殊字符转义等问题，这点就已经导致不一样；
2. 校验任务执行频率和执行时间要求；
3. 能否直连两边库；
4. 中间缓存对两边库数据类型的兼容统一，只能 CSV 跳过这点；

一次性比较我直接 cut sort comm ，写代码浪费生命。
经常跑、对比文件就直接 导入 DuckDB FULL OUTER JOIN 。

比较专业的方案 https://github.com/datafold/data-diff ，可以参考它的思路

[litguy]

两个文件 mmap 看看 ？

[laminux29]

最讨厌这种，一开始不把事情说清楚，非得搞一些奇葩方案，再三逼问下，到了 64 楼才解释原始需求。

导致一开始，此事就成为 X-Y 问题，浪费大家精力与时间。

你这事，从软件工程角度来说，正确的解法，并不是找数据库去帮你排序，也不是自己写代码去处理，而是使用业界现有的数据验证工具。据我所知，数据治理领域，就存在不少的数据库互转与验证软件。你自己代码写得再正确，也不通用，不如学会使用这样的现成工具，减少浪费时间重复造轮子的事情。

[bianhui]

姓排个序，分批比较

[blankmiss]

@xy629 V2EX 不允许 gpt 回复 会被 ban 号

[pzhdfy]

这不是大数据经典处理方法吗

将 PersonListA.csv 通过 name hash 拆分为 10 个，PersonListA_1.csv,PersonListA_2.csv...,PersonListA_10.csv （或者更多，每个文件能载入内存就行）
规则是每行数据通过 hash(name)%10 来确定放到哪个文件

将 PersonListB.csv 也是一样的原理，生成 PersonListB_1.csv,PersonListB_2.csv...,PersonListB_10.csv

这样 PersonListA_1.csv 只会根 PersonListB_1.csv 有相同 name 的数据，
所以只需要 10 组文件对比就行

[fregie]

mysql 不能用就是说网络不能用
sqlite 不能用意味着硬盘也不能用
内存不够，硬盘也不能用，根据需求确实也需要多次全部遍历
可以用 hash 来加快但是你已经用了
所以我认为是无解

[bashbot]

针对数据内容实现 hash 算法，对 FileA 生成索引保存到磁盘上，然后再读 FileB 去查索引就有结果了。

[tslearn]

看看这种方法行不 （假设 Name 支持任意字符）

将文件分片
1 ） 选取一个质数作为分片的值 （例如 977 ）
2 ） 将 A 文件和 B 文件分片， 要保证相同的名字在相同的分片号， 且分片尽可能均匀
我帮你想到的一个合理的办法： 取 Name 的 UTF8 。 如果 UTF8 长度不能被 4 整除，则添 0 将数组长度补成 4 的倍数。
每四个字节映射为一个 int32 类型， 然后把这些 int32 加起来。 然后%977 （一个比较大的指数）。 这样会得到 0-966 中的一个值。
3 ） 你的问题化简成了在分片内的问题 （因为相同的名字对应相同的分片）