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

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 条回复
HanMeiM
2024-02-16 10:45:19 +08:00
其实不需要这么麻烦,先对两个文件进行排序,产生两个新的文件
新文件的排序规则是:把相同名字的人放在同一行,这样两个文件相当于变成了两个 map ,再逐行遍历 A 、B 两个文件并读取当行数据做比较
我说的比较笼统,希望你能明白这个思路
HanMeiM
2024-02-16 10:50:49 +08:00
哦,没看到不能用排序。但是我说的方案时间复杂度基本上是 O(n),空间复杂度也不会增加多少,可以考虑下
ychost
2024-02-16 14:38:29 +08:00
内存条很便宜,2*32G 才 500 块
FeifeiJin
2024-02-16 16:54:45 +08:00
@matrix1010 谢谢,我目前采用的是这个思路,不过我是从磁盘每次加载到内存里,它是暂存到磁盘。不过读完还是颇有收获。

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

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

@luyifei 谢谢,兄弟。说到底其实我就是自己类实现了这部分东西。
AItsuki
2024-02-17 06:24:55 +08:00
保持原来方案,但是思路换一换,10 组数据两两剔除相同元素。后续需要处理的数据量会越来越小。这样可行不。
noparking188
2024-02-17 12:54:27 +08:00
你们没有数据开发吧,这思路太后端了

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
2024-02-17 22:00:29 +08:00
两个文件 mmap 看看 ?
laminux29
2024-02-18 08:11:02 +08:00
最讨厌这种,一开始不把事情说清楚,非得搞一些奇葩方案,再三逼问下,到了 64 楼才解释原始需求。

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

你这事,从软件工程角度来说,正确的解法,并不是找数据库去帮你排序,也不是自己写代码去处理,而是使用业界现有的数据验证工具。据我所知,数据治理领域,就存在不少的数据库互转与验证软件。你自己代码写得再正确,也不通用,不如学会使用这样的现成工具,减少浪费时间重复造轮子的事情。
bianhui
2024-02-18 08:18:05 +08:00
姓排个序,分批比较
blankmiss
2024-02-18 09:24:22 +08:00
@xy629 V2EX 不允许 gpt 回复 会被 ban 号
pzhdfy
2024-02-18 14:53:06 +08:00
这不是大数据经典处理方法吗

将 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
2024-02-18 17:06:06 +08:00
mysql 不能用就是说网络不能用
sqlite 不能用意味着硬盘也不能用
内存不够,硬盘也不能用,根据需求确实也需要多次全部遍历
可以用 hash 来加快但是你已经用了
所以我认为是无解
bashbot
2024-02-18 17:14:43 +08:00
针对数据内容实现 hash 算法,对 FileA 生成索引保存到磁盘上,然后再读 FileB 去查索引就有结果了。
tslearn
2024-02-20 03:38:32 +08:00
看看这种方法行不 (假设 Name 支持任意字符)

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

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

https://yangjunhui.monster/t/1015733

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

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

© 2021 V2EX