1. 云栖社区>
  2. >
  3. 正文

[面试题]海量数据处理-从10亿个数中找频率最高的1000个数

作者:用户 来源:互联网 时间:2018-08-27 10:13:47

[面试题]海量数据处理-从10亿个数中找频率最高的1000个数 - 摘要: 本文讲的是[面试题]海量数据处理-从10亿个数中找频率最高的1000个数, 方法一:分治思想 通常比较好的方案是分治+Trie树/hash+小顶堆(就是上面提到的最小堆),即先将数据集按照Hash方法分解成多个小数据集,然后使用Trie树或者Hash统计每个小数据集中的query词频,之后用

方法一:分治思想

通常比较好的方案是分治+Trie树/hash+小顶堆(就是上面提到的最小堆),即先将数据集按照Hash方法分解成多个小数据集,然后使用Trie树或者Hash统计每个小数据集中的query词频,之后用小顶堆求出每个数据集中出现频率最高的前K个数,最后在所有top K中求出最终的top K。

方法二:hadoop的map,reduce

top K问题很适合采用MapReduce框架解决,用户只需编写一个Map函数和两个Reduce 函数,然后提交到Hadoop(采用Mapchain和Reducechain)上即可解决该问题。具体而言,就是首先根据数据值或者把数据hash(MD5)后的值按照范围划分到不同的机器上,最好可以让数据划分后一次读入内存,这样不同的机器负责处理不同的数值范围,实际上就是Map。得到结果后,各个机器只需拿出各自出现次数最多的前N个数据,然后汇总,选出所有的数据中出现次数最多的前N个数据,这实际上就是Reduce过程。对于Map函数,采用Hash算法,将Hash值相同的数据交给同一个Reduce task;对于第一个Reduce函数,采用HashMap统计出每个词出现的频率,对于第二个Reduce 函数,统计所有Reduce task,输出数据中的top K即可。

方法三:利用hadoop hive中的sort by 和 limti n:

Hive提供了limit关键字,再配合orderby可以很容易地实现SELECT TOPN。
但是在Hive中orderby只能使用1个reduce,如果表的数据量很大,那么orderby就会力不从心。
例如我们执行SQL:select a from ljntest01order by a limit 10;
控制台会打印出:Number of reducetasks determined at compile time: 1
说明启动的reduce数量是编译时确定的。
查看该SQL的执行计划,该SQL只启动1个JOB。 

假设数据表有1亿条数据,而我们只想取TOP10,那对1亿条数据在1个reduce中做全排序是非常不合理的。
幸好有sortby,使用sortby替换orderby就可以解决这个问题:
select a from ljntest01 sort by a limit10;
首先执行该 SQL 控制台打印出: Number of reducetasks not specified. Estimated from input data size:1
说明reduce数不是编译时确定的,而是根据输入文件大小动态确定的。

sort by可以启动多个reduce,每个reduce做局部排序,但是这对于sort bylimit N已经够用了。从执行计划中可以看出sort bylimit N启动了两个JOB。第一个JOB是在每个reduce中做局部排序,然后分别取TOPN。假设启动了M个reduce,第二个JOB再对M个reduce分别局部排好序的总计M *N条数据做全局排序,取TOPN,从而得到想要的结果。这样就可以大大提高SELECT TOPN的效率

方法四:基于spark RDD的方法:

性能要比hadoop的map,reduce性能有显著提升。
详细代码及说明见 这里

实例: 有一个1G大小的一个文件,里面每一行是一个词,词的大小不超过16字节,内存限制大小是1M。返回频数最高的100个词。 
解决方案:顺序读文件中,对于每个词x,取 ,然后按照该值存到5000个小文件(记为 ) 中。这样每个文件大概是200k左右。如果其中的有的文件超过了1M大小,还可以按照类似的方法继续往下分,知道分解得到的小文件的大小都不超过1M。对 每个小文件,统计每个文件中出现的词以及相应的频率(可以采用trie树/hash_map等),并取出出现频率最大的100个词(可以用含100个结点 的最小堆),并把100词及相应的频率存入文件,这样又得到了5000个文件。下一步就是把这5000个文件进行归并(类似与归并排序)的过程了。

以上是云栖社区小编为您精心准备的的内容,在云栖社区的博客、问答、公众号、人物、课程等栏目也有的相关内容,欢迎继续使用右上角搜索按钮进行搜索,以便于您获取更多的相关知识。