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

2024-02-15 16:36:41 +08:00
 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 中都存在,但有差异的数据。


可以有什么办法吗?或者给我一些算法关键字,比如我现在使用的是类哈希分页对比。
6736 次点击
所在节点    程序员
74 条回复
luyifei
2024-02-15 21:28:45 +08:00
建议重点复习一下数据库 sort merge join 和 hash join 的实现,你说的这些问题在数据库领域是已知问题
ashong
2024-02-15 21:45:41 +08:00
1 、导入 sqlite 处理再导出
2 、内存映射
tool2d
2024-02-15 21:51:32 +08:00
排序挺方便的,但我觉得内存也不贵,买个 64G 内存,足够处理两个 10G 文件了。
SuperXX
2024-02-15 22:02:39 +08:00
DuckDB 试试看
cybort
2024-02-15 22:32:25 +08:00
可以对每条数据做一个 hash ,hash 后的数据量小于原始数据,这样相当于对两个较小的文件进行操作,找到了再去原文件校验一下。
cybort
2024-02-15 22:35:58 +08:00
数据库可能楼主没有权限去访问。机器也不一定在他手里。
clorischan
2024-02-15 23:09:36 +08:00
全部读取到内存中.
数据结构可以用前缀树进行存储 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
2024-02-15 23:42:35 +08:00
你这不直接放数据库里。。。。
lance6716
2024-02-16 00:34:39 +08:00
可以找一下数据库各种 join 算法,自己造轮子。不过有这功夫直接安装导入跑 SQL 都跑完了。别满脑子都是技术,怎么解决问题怎么来
yangyaofei
2024-02-16 00:42:10 +08:00
读一遍,形成一个类似索引的缓存.

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

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

当然再写下去就变成数据库了.
ccde8259
2024-02-16 01:50:55 +08:00
Flink CDC -> Hive -> HSQL……
写代码的成本不如直接租云服务直接跑完了
shuimugan
2024-02-16 02:39:25 +08:00
你这个不叫本地文件过大,这个叫本地内存太小。我以前都是在公司丢一台 128G 内存台式机干点数据处理的脏活累活,你这个场景分分钟就搞定了
XiaoFaye
2024-02-16 04:02:51 +08:00
现在的年轻人都不知道 MMP 了?
XiaoFaye
2024-02-16 04:03:11 +08:00
修正:现在的年轻人都不知道 MMF 了?
ryd994
2024-02-16 04:39:26 +08:00
不许排序是什么奇葩要求?

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

坚持要处理无序数据,On^2 慢慢对呗,呵呵
MetroWind
2024-02-16 05:34:42 +08:00
调试屎山啊,加内存是最快且最便宜的方法。
hyperbin
2024-02-16 06:29:45 +08:00
建个 SQlite 数据库文件,用完就删
xy629
2024-02-16 07:48:27 +08:00
你面临的问题是处理两个非常大的数据集,并且需要找出它们之间的差异。这里有几个关键点需要考虑:

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

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

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

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

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

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

关键词和概念
外部排序:处理无法全部放入内存的大数据集的排序方法。
MapReduce:一种分布式数据处理模型,适用于大规模数据集的处理。
数据库操作:使用 SQL 和数据库管理系统进行高效的数据查询和比较。
流处理:实时处理数据流的方法,适用于连续的数据输入。
根据你的资源和环境,可以选择最适合你情况的方法。如果你正在使用的环境(如特定的编程语言或框架)有限制,请告诉我,这样我可以提供更具体的建议。 -- from chatGPT
levelworm
2024-02-16 07:52:40 +08:00
我琢磨着用命令行工具行不行。。。
bluekz
2024-02-16 10:20:19 +08:00
AWK 应该就行把,几个 G 的我是整过的

这是一个专为移动设备优化的页面(即为了让你能够在 Google 搜索结果里秒开这个页面),如果你希望参与 V2EX 社区的讨论,你可以继续到 V2EX 上打开本讨论主题的完整版本。

https://yangjunhui.monster/t/1015733

V2EX 是创意工作者们的社区,是一个分享自己正在做的有趣事物、交流想法,可以遇见新朋友甚至新机会的地方。

V2EX is a community of developers, designers and creative people.

© 2021 V2EX