题目描述
给定a、b两个文件,各存放100亿个url,每个url各占64字节,内存限制是4G,让你找出a、b文件共同的url?
解决方案是分而治之:
将文件a按照hash分为10000份,
hash(url)%10000
然后去b文件逐个判断是否在a文件中。
这里有一个优化的地方,就是使用布隆过滤器,如果判断不存在不再去b文件判断,这样可以有效挡住大部分无效的判断。
题目描述
给定a、b两个文件,各存放100亿个url,每个url各占64字节,内存限制是4G,让你找出a、b文件共同的url?
解决方案是分而治之:
将文件a按照hash分为10000份,
hash(url)%10000
然后去b文件逐个判断是否在a文件中。
这里有一个优化的地方,就是使用布隆过滤器,如果判断不存在不再去b文件判断,这样可以有效挡住大部分无效的判断。
本文标题:两个大文件中找出共同记录: 分而治之+布隆过滤器
本文链接:https://www.haomeiwen.com/subject/sdrivctx.html
网友评论