上传者: 26712065
|
上传时间: 2021-08-14 02:57:53
|
文件大小: 4.43MB
|
文件类型: PDF
同时,程序员编程艺术系列将重新开始创作,第十一章以后的部分题目来源将取自下文
中的 17 道海量数据处理的面试题。因为,我们觉得,下文的每一道面试题都值得重新思考,
重新深究与学习。再者,编程艺术系列的前十章也是这么来的。若您有任何问题或建议,欢
迎不吝指正。谢谢。
第一部分、十五道海量数据处理面试题
1. 给定 a、b 两个文件,各存放 50 亿个 url,每个 url 各占 64 字节,内存限制是 4G,让
你找出 a、b 文件共同的 url?
方案 1:可以估计每个文件安的大小为 50G×64=320G,远远大于内存限制的 4G。所
以不可能将其完全加载到内存中处理。考虑采取分而治之的方法。
1. 遍历文件 a,对每个 url 求取 1000)%(urlhash ,然后根据所取得的值将 url 分别存
储到 1000 个小文件(记为 99910 ,,, aaa )中。这样每个小文件的大约为 300M。
2. 遍历文件 b,采取和 a 相同的方式将 url 分别存储到 1000 小文件中(记为
99910
,,, bbb )。这样 处理 后,所 有可能 相同的 url 都在 对应的 小文件
( 9999991100 ,,, bvsabvsabvsa )中,不对应的小文件不可能有相同的 url。然后
我们只要求出 1000 对小文件中相同的 url 即可。
3. 求每对小文件中相同的 url 时,可以把其中一个小文件的 url 存储到 hash_set 中。
然后遍历另一个小文件的每个 url,看其是否在刚才构建的 hash_set 中,如果是,
那么就是共同的 url,存到文件里面就可以了。
方案 2:如果允许有一定的错误率,可以使用 Bloom filter,4G 内存大概可以表示 340
亿 bit。将其中一个文件中的 url 使用 Bloom filter 映射为这 340 亿 bit,然后挨个读取另外一
个文件的 url,检查是否与 Bloom filter,如果是,那么该 url 应该是共同的 url(注意会有一
定的错误率)。