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

点击上方 "Python人工智能技术" 关注，星标或者置顶

22点24分准时推送，第一时间送达

后台回复“大礼包”，送你特别福利

编辑：乐乐 | 来自：advanced-java

链接：doocs.github.io/advanced-java/

上一篇：用Python构建API的八大流行框架

正文

大家好，我是Python人工智能技术

• 题目描述

• 解答思路

• 方法总结

---

题目描述

给定 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 保存到一个单独的文件中。

方法总结

• 分而治之，进行哈希取余；

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

你还有什么想要补充的吗？

免责声明：本文内容来源于网络，文章版权归原作者所有，意在传播相关技术知识&行业趋势，供大家学习交流，若涉及作品版权问题，请联系删除或授权事宜。

技术君个人微信

添加技术君个人微信即送一份惊喜大礼包

→ 技术资料共享

→ 技术交流社群

--END--

往日热文：

Python程序员深度学习的“四大名著”：

这四本书着实很不错！我们都知道现在机器学习、深度学习的资料太多了，面对海量资源，往往陷入到“无从下手”的困惑出境。而且并非所有的书籍都是优质资源，浪费大量的时间是得不偿失的。给大家推荐这几本好书并做简单介绍。

获得方式：

1.扫码关注本公众号

2.后台回复关键词：名著

▲长按扫描关注，回复名著即可获取