两个50亿url文件找出共同的url的个人思考解法

最近听到了一个以前的算法题，题目大概是这样的

给A，B两个文件，各存放50亿条URL，每条URL占用64个字节，内存限制为4G，找出A，B中相同的URL。

一看题干，算都不用算，肯定一次性内存加载不起来，必须想其他办法

看了一下网上主要有这两种解决方案：

第一种方法是用布隆过滤器，利用布隆过滤器的特性来获得相同URL，其实我第一次看到这个题目的时候的第一个想法也是布隆过滤器，但这种方法有个问题，布隆过滤器是有效果误差的，会将一部分不同的也当时相同的识别进来，虽然通过设置长度控制函数个数能够降低这个误差，但依然有误差，一旦题目变成了找出不同的URL，就歇菜了，而且布隆过滤器也要求一次性申请全部长度的内存，如果内存限制更小，比如1G，512M，或者数据量更大，那布隆过滤器也无法满足

第二种方法是分而治之的思想，按照同一种哈希算法把两个50亿的文件都分割成若干小文件，每个小文件都让他能够4G内存加载起来，小文件之间对比，再把对比结果整合。这个方案弥补了布隆过滤器的问题，如果分布能够均匀的话，利用更小的内存都能够做这个事情，无非就是更多的文件么，但这带来了一个新的问题，选择什么样的哈希算法能够分布均匀，无论什么哈希算法都有分布不均匀的可能性，那么就又不稳定的可能性

这里简单描述一下我的解决方法

第一步，将每个文件等距拆分成若干小文件，这里不需要算法，目的只是获得各自的一堆小文件，距离不同都行。时间复杂度：O(n)

第二步，每个小文件内部排序（排序算法随意，排序方法和方向相同）。时间复杂度：随排序算法

第三步，将排序好的小文件还原回大文件，保证大文件排好序。时间复杂度：O(n*logn)

第四步，对比两个排好序的文件就简单啦，几乎不会耗费内存。时间复杂度：O(n)

这个过程基本可以适应任意大的数据和任意小的内存，同时是稳定的

当然缺点也是有的，就是第三步的还原通常需要同时打开这些文件，那么如果文件太多，比如超过65535个，那如果在linux下面即使改了ulimit也无法支持，这部分会增加一定的复杂度

最后

以上就是敏感枫叶为你收集整理的两个50亿url文件找出共同的url的个人思考解法的全部内容，希望文章能够帮你解决两个50亿url文件找出共同的url的个人思考解法所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。