如何从 100 亿 URL 中找出相同的 URL?
来源 | https://doocs.github.io/advanced-java/
题目描述
给定 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 统计。
往期推荐
CEO不当了,CTO也不做了!我要回去写代码,这才是我所热爱的!
喜欢本文欢迎转发,关注我订阅更多精彩
关注我回复「加群」,加入Spring技术交流群
相关文章
- Django如何处理URL请求
- win10 如何查看redis版本「建议收藏」
- CleanMyMac X2022许可证如何使用?
- 如何生成lib文件_bin文件和mcs文件
- 如何准备好一场vue面试
- 如何使用LiveTargetsFinder生成实时活动主机URL列表
- 如何使用Bypass-Url-Parser实现URL绕过并访问40X受保护页面
- 如何使用flask的 @app.url_defaults 装饰器
- 如何使用flask的 @app.url_value_preprocessor 装饰器
- nginx如何自动切割访问日志详解架构师
- 『MySQL连接URL:获取快速、安全连接』(连接mysql的url)
- Oracle 视图 V$SQL_MONITOR_STATNAME 官方解释,作用,如何使用详细说明
- Oracle 视图 V$TEMPSEG_USAGE 官方解释,作用,如何使用详细说明
- JSP JSTL <c:url>标签:生成URL地址标签
- 掌握MySQL URL写法,快速实现数据库连接(mysql的url怎么写)
- 如何使用Redis连接URL来提高数据传输效率?(redis连接url)
- Linux 如何快速转换 IP 地址?(linux转换ip地址)
- MySQL如何在URL中使用(mysql 中url)
- 如何使用MySQL不建立主键(mysql 不建立主键)
- 加速运行如何利用Redis提升业务执行效率(redis 配合业务)
- Oracle数据库快速找到正确的URL地址(oracle url地址)
- javascript静态的url如何传递
- 浅谈PHP解析URL函数parse_url和parse_str