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

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 条回复
matrix1010
2024-02-15 17:29:38 +08:00
用不了数据库但你可以参考数据库的做法: https://dev.mysql.com/blog-archive/hash-join-in-mysql-8/
laike9m
2024-02-15 17:45:44 +08:00
@FeifeiJin 没看出为什么不能
mayli
2024-02-15 18:14:13 +08:00
@laike9m 因为就故意想要吃屎,有靠谱的简单解法不错,非得要屎上雕花。
这玩意随便弄个数据库建个索引就跑就完事,还用费这劲。而且,才 10GB 的文件,也不算大啊。实在不行租台 r3.xlarge 一小时 $0.350 , 一下子就出来了。
实在没钱,放 sqlite 里,做个 index, page_cache 有多少给多少,就硬算就完事.
dswyzx
2024-02-15 18:18:46 +08:00
感觉你还是要把思路打开.db 用 sqllite 也不重.但只要数据脱离 csv 到 db 里.想怎么玩不就都好说了,与其在一个旧代码里想办法优化,不如开个新的项目吧.如果说是开发流程或者规范不允许再 csv 写入其他地方,那你首先要做的是找领导反馈协调.而不是在这里屎山雕花
rocmax
2024-02-15 18:26:58 +08:00
先用 A 做一个字典树,然后遍历 b 去查?
rocmax
2024-02-15 18:28:44 +08:00
@rocmax 这样找不到 a 里有但 b 里没有的,除非反过来再来一次
testFor
2024-02-15 18:32:15 +08:00
@rocmax 感觉你的回答最靠谱也相对简单,名字应该重复的概率很高,内存占用不多,把年龄挂在最后一个节点就完事了.然后每天跑一次,存缓存结果,存不下就数据分段
testFor
2024-02-15 18:35:24 +08:00
@rocmax 找一次就可以拿到三个结果
rocmax
2024-02-15 18:37:15 +08:00
如果做两棵字典树,然后各自用一个指针同步遍历可不可以同时找出两个树缺失的部分?毕竟可以按字母序遍历,一边缺了另一边就等着,赶上来了再同步走,同时记录差异
rocmax
2024-02-15 18:40:33 +08:00
@testFor 可以吗? a 并没有遍历过啊
rocmax
2024-02-15 18:41:49 +08:00
@testFor 标记叶子节点然后统计没有查过的叶子?
testFor
2024-02-15 18:43:36 +08:00
@rocmax en,搜索过程给点反馈就能一次遍历产生三个结果. 1.有没有完全匹配 2.完全匹配年龄是否相同
testFor
2024-02-15 18:51:30 +08:00
@rocmax 或者就是两个文件进行外部排序,然后在进行头对比,就是你上面的那种等待,不过名字应该重复率挺高的,应该不如字典树省内存和效率高
antipro
2024-02-15 18:58:46 +08:00
@testFor 对,给 person 加个 Mark 属性,默认为 0 ,从 A 中分块并发到 B 中比对,一次出两个结果,对上了 mark=1,全结束后从 B 中取出 mark=0 的,就是 B 有 A 没有的。
nbndco
2024-02-15 19:04:28 +08:00
这件事的正解就是排序,无非是你自己拍,还是数据库帮你排的区别。

当然你有特殊癖好那就不在考虑范围了
fairytale
2024-02-15 19:46:41 +08:00
要么排序,要么分组。sum(name)%8 每个余数过一遍。
fairytale
2024-02-15 19:51:38 +08:00
其实 hashmap 也是一种排序,你不允许任何形式排序那就只能(10^10)∧3
kisick
2024-02-15 20:08:46 +08:00
做过一模一样的事情,解法是把两个数据库里的数据都抽取一份到第三个数据库里,在第三个数据库里通过 sql 比较
67373net
2024-02-15 21:13:17 +08:00
能不能说下为什么不能用 sqlite ?爬完了也没看明白。。
wangritian
2024-02-15 21:22:29 +08:00
兄弟,看一眼内存的价格

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

https://yangjunhui.monster/t/1015733

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

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

© 2021 V2EX