如何从 100 亿 URL 中找出相同的 URL?

编程帮

共 1248字,需浏览 3分钟

 ·

2021-01-25 11:49


点击上方 蓝字 关注我们!



Java,Python,C/C++,Linux,PHP,Go,C#,QT,大数据,算法,软件教程,前端,简历,毕业设计等分类,资源在不断更新中... 点击领取

每天 11 点更新文章,饿了点外卖,点击 👉《无门槛外卖优惠券,每天免费领!》


  • 题目描述

  • 解答思路

  • 方法总结


题目描述

给定 a、b 两个文件,各存放 50 亿个 URL,每个 URL 各占 64B,内存限制是 4G。请找出 a、b 两个文件共同的 URL。

解答思路

每个 URL 占 64B,那么 50 亿个 URL占用的空间大小约为 320GB。

5, 000, 000, 000 * 64B ≈ 5GB * 64 = 320GB

由于内存大小只有 4G,因此,我们不可能一次性把所有 URL 加载到内存中处理。对于这种类型的题目,一般采用分治策略 ,即:把一个文件中的 URL 按照某个特征划分为多个小文件,使得每个小文件大小不超过 4G,这样就可以把这个小文件读到内存中进行处理了。

思路如下 :

首先遍历文件 a,对遍历到的 URL 求 hash(URL) % 1000 ,根据计算结果把遍历到的 URL 存储到 a0, a1, a2, ..., a999,这样每个大小约为 300MB。使用同样的方法遍历文件 b,把文件 b 中的 URL 分别存储到文件 b0, b1, b2, ..., b999 中。这样处理过后,所有可能相同的 URL 都在对应的小文件中,即 a0 对应 b0, ..., a999 对应 b999,不对应的小文件不可能有相同的 URL。那么接下来,我们只需要求出这 1000 对小文件中相同的 URL 就好了。

接着遍历 ai( i∈[0,999] ),把 URL 存储到一个 HashSet 集合中。然后遍历 bi 中每个 URL,看在 HashSet 集合中是否存在,若存在,说明这就是共同的 URL,可以把这个 URL 保存到一个单独的文件中。

方法总结

  1. 分而治之,进行哈希取余;

  2. 对每个子文件进行 HashSet 统计。

END

看完文章,饿了点外卖,点击 👉《无门槛外卖优惠券,每天免费领!》


若觉得文章对你有帮助,随手转发分享,也是我们继续更新的动力。


长按二维码,扫扫关注哦

「C语言中文网」官方公众号,关注手机阅读教程 


必备编程学习资料


目前收集的资料包括: Java,Python,C/C++,Linux,PHP,go,C#,QT,git/svn,人工智能,大数据,单片机,算法,小程序,易语言,安卓,ios,PPT,软件教程,前端,软件测试,简历,毕业设计,公开课 等分类,资源在不断更新中...


点击“阅读原文”,立即免费领取最新资料!
👇👇👇
浏览 22
点赞
评论
收藏
分享

手机扫一扫分享

分享
举报
评论
图片
表情
推荐
点赞
评论
收藏
分享

手机扫一扫分享

分享
举报