在大规模数据处理中,经常会遇到的一类问题:在海量数据中找出出现频率最好的前k个数,或者从海量数据中找出最大的前k个数,这类问题通常被称为top K问题。例如,在搜索引擎中,统计搜索最热门的10个查询词;在歌曲库中统计下载最高的前10首歌等。
- 最容易想到的方法是将数据全部排序。该方法并不高效,因为题目的目的是寻找出最大的10000个数即可,而排序却是将所有的元素都排序了,做了很多的无用功。
- a、将100亿个数据分为1000个大分区,每个区1000万个数据
- b、每个大分区再细分成100个小分区。总共就有1000*100=10万个分区
- c、计算每个小分区上最大的1000个数。
为什么要找出每个分区上最大的1000个数?举个例子说明,全校高一有100个班,我想找出全校前10名的同学,很傻的办法就是,把高一100个班的同学成绩都取出来,作比较,这个比较数据量太大了。应该很容易想到,班里的第11名,不可能是全校的前10名。也就是说,不是班里的前10名,就不可能是全校的前10名。因此,只需要把每个班里的前10取出来,作比较就行了,这样比较的数据量就大大地减少了。我们要找的是100亿中的最大1000个数,所以每个分区中的第1001个数一定不可能是所有数据中的前1000个。
- d、合并每个大分区细分出来的小分区。每个大分区有100个小分区,我们已经找出了每个小分区的前1000个数。将这100个分区的1000*100个数合并,找出每个大分区的前1000个数。
- e、合并大分区。我们有1000个大分区,上一步已找出每个大分区的前1000个数。我们将这1000*1000个数合并,找出前1000.这1000个数就是所有数据中最大的1000个数。(a、b、c为map阶段,d、e为reduce阶段)