海量数据去重

2022-08-02  本文已影响0人  水中的蓝天

一个文件中有40亿条数据,每条数据是一个32位的数字串,设计算法对其去重,相同的数字串仅保留一个,内存限制1G.

方法一:排序

对所有数字串进行排序,重复的数据传必然相邻,保留第一个,去除后面重复的数字串即可。

缺点是排序时间复杂度太高,并且显然是需要内排序+外排序一起的。优化的方法有扫雪机模型。

方法二:哈希表 + 文件分割

当然还有一种方法,取32位的前n位做一个哈希,然后把哈希值一样的数据串放到一个文件里面。然后每次将一个文件load到内存中,然后对这个文件中的数据做个排序 or 哈希去重即可。

这样的缺点是磁盘IO较多。

方法三:位图

用512MB的unsigned int数组来记录文件中数字串的存在与否,形成一个bitmap。

然后从0到2^32-1开始遍历,如果flag为1,表明该数存在。这样就自动实现了去重。

这个思路很好了。

上一篇下一篇

猜你喜欢

热点阅读