以下文章来源于程序员大彬 ,作者大彬
非科班转码,校招拿了京东、携程等多家大厂offer,专注分享编程学习、求职面试~面试网站:topjavaer.cn
大家好,我是陌溪
今天分享一道面试常考的海量数据面试题。
假如有一个1G大小的文件,文件里每一行是一个词,每个词的大小不超过16byte,要求返回出现频率最高的100个词。内存大小限制是10M
由于内存限制,我们无法直接将大文件的所有词一次性读到内存中。
可以使用分治策略,把一个大文件分解成多个小文件,保证每个文件的大小小于10M,进而直接将单个小文件读取到内存中处理。
第一步,首先遍历大文件,对遍历到的每个词x,执行 hash(x) % 500
,将结果为i的词存放到文件f(i)中,遍历结束后,可以得到500个小文件,每个小文件的大小为2M左右;
第二步,接着统计每个小文件中出现频数最高的100个词。可以使用HashMap来实现,其中key是词,value是该词出现的频率。
对于遍历到的词x,如果在map中不存在,则执行 map.put(x, 1)。
若存在,则执行 map.put(x, map.get(x)+1)
,将该词出现的次数加1。
第三步,在第二步中找出了每个文件出现频率最高的100个词之后,通过维护一个小顶堆来找出所有小文件中出现频率最高的100词。
具体方法是,遍历第一个文件,把第一个文件中出现频率最高的100个词构造成小顶堆。
如果第一个文件中词的个数小于100,可以继续遍历第二个文件,直到构造好有100个结点的小顶堆为止。
继续遍历其他小文件,如果遍历到的词的出现次数大于堆顶上词的出现次数,可以用新遍历到的词替换堆顶的词,然后重新调整此堆为小顶堆。
当遍历完所有小文件后,这个小顶堆中的词就是出现频率最高的100词。
总结一下,这种解法的主要思路如下:
但是很容易可以发现问题,在第二步中,如果这个1G的大文件中有某个词词频过高,可能导致小文件大小超过10m。这种情况下该怎么处理呢?
接下来看另外一种解法。
第一步:使用多路归并排序对大文件进行排序,这样相同的单词肯定是紧挨着的
多路归并排序对大文件进行排序的步骤如下:
① 将文件按照顺序切分成大小不超过2m的小文件,总共500个小文件
② 使用10MB内存分别对 500 个小文件中的单词进行排序
③ 使用一个大小为500大小的堆,对500个小文件进行多路排序,结果写到一个大文件中
其中第三步,对500个小文件进行多路排序的思路如下:
第二步:
① 初始化一个100个节点的小顶堆,用于保存100个出现频率最多的单词
② 遍历整个文件,一个单词一个单词的从文件中取出来,并计数
③ 等到遍历的单词和上一个单词不同的话,那么上一个单词及其频率如果大于堆顶的词的频率,那么放在堆中,否则不放
最终,小顶堆中就是出现频率前100的单词了。
解法2相对解法1,更加严谨,如果某个词词频过高或者整个文件都是同一个词的话,解法1不适用。
(完)
我是大彬,非科班转码,大三开始自学Java,校招斩获京东、携程等offer。作为一名转码选手,深感这一路的不易。
希望我的分享可以帮助更多的小伙伴,我踩过的坑你们不要再踩!
想与我交流的话,可以到公众号后台获取我的个人微信号~