校招刷题群
高效刷题 迎战校招
校招精选试题
近年面笔经面经群内分享
Java刷题群 前端刷题群 产品运营群
首页 > 算法 > 大数据相关算法
题目

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

解答

思路:

先计算总的数据大小,看能不能一次性放到内存里

      ·50亿 = 5,000,000,000≈5G, 

      ·总大小为 5G * 64B = 32GB, 远大于4G内存 

找到共同的Url,需要每个值都比较,只能使用哈希将文件切分成小文件

      ·文件的数量怎么确定?

        切成小文件后,内存里需要同时存在a和b的两个小文件,才能进行比较。

        那一个小文件的最大大小为2G, 32/2 = 16, 但是机器运行还需要内存

        我们可以切分为20份,两个小文件占用内存3.2G

1.对a ,b hash(url)%20, 分为20个小文件里

hash映射函数可以有多样选择,

最简单的就是按首字母分类,可以分成26个小文件,但是不能保证每个文件大小相等, 也不符合20个小文件的设定(当然也可以改成切分成26个小文件)

可以取前4个字节的int和%20,分配到20个小文件中

2.因为使用同一个hash函数映射规则的原因,a,b切分后相同的Url存在于对应的小文件中,即a0只需要和b0比较, a1 和b1比较即可

3.然后,同时加载每一对小文件(如a0和b0),如果有相同的url, 则输出到文件中记录

  全部比较完成后,文件中就是所有相同的记录

  哈希切分成小文件,是解决大数据问题最常用的方法

C 2条回复 评论
周周

简直是我梦想中的offer,好想去上班

发表于 2021-09-09 12:45:00
0 0
青辰

感觉文章思路挺清晰的~

发表于 2021-09-08 16:45:01
0 0