如何从 100 亿 URL 中找出相同的 URL？
2024-09-07 19:56:49
题目描述
给定 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 统计
最新文章
- time step和采样频率的关系
- TypeScript 素描-基础类型
- wifi强度数据采集器(android)
- Zookeeper开源客户端框架Curator简介[转]
- WampServer 在 httpd.conf 中配置多站点 (IP 配置法：不用每次修改 hosts 文件 + 域名配置法 )
- Android--HTTP协议
- JS框架整理
- 正则表达式：根据逗号解析CSV并忽略引号内的逗号
- MySQL数据库配置主从服务器实现双机热备
- shell脚本一键同步集群时间
- C#中函数的功能和类型
- Itext中 根据html生成Word文件,包含图片
- Cypher查询语言--Neo4j-WHERE(三)
- Pycharm 中You are using pip version 10.0.1, however version 18.1 is available. You should consider upgrading via the 'python -m pip install --upgrade pip' command.
- [MySQL]多表关联查询技巧
- 【Linux】【Jenkins】配置过程中，立即构建时，maven找不到的问题解决方案
- shell脚本--函数
- Django的restframework的序列化组件之对单条数据的处理
- Basic Router Architecture
- AJPFX外汇的常见形态