1. 问题描述
在大规模数据处理中,常遇到的一类问题是,在海量数据中找出出现频率最高的前K个数,或者从海量数据中找出最大的前K个数,这类问题通常称为“top K”问题,如:在搜索引擎中,统计搜索最热门的10个查询词;在歌曲库中统计下载率最高的前10首歌等等。
2. 当前解决方案
针对top k类问题,通常比较好的方案是【分治+trie树/hash+小顶堆】,即先将数据集按照hash方法分解成多个小数据集,然后使用trie树或者hash统计每个小数据集中的query词频,之后用小顶堆求出每个数据集中出频率最高的前K个数,最后在所有top K中求出最终的top K。
实际上,最优的解决方案应该是最符合实际设计需求的方案,在实际应用中,可能有足够大的内存,那么直接将数据扔到内存中一次性处理即可,也可能机器有多个核,这样可以采用多线程处理整个数据集。
本文针对不同的应用场景,介绍了适合相应应用场景的解决方案。
3. 解决方案
3.1 单机+单核+足够大内存
设每个查询词平均占8Byte,则10亿个查询词所需的内存大约是10^9*8=8G内存。如果你有这么大的内存,直接在内存中对查询词进行排序,顺序遍历找出10个出现频率最大的10个即可。这种方法简单快速,更加实用。当然,也可以先用HashMap求出每个词出现的频率,然后求出出现频率最大的10个词。
3.2 单机+多核+足够大内存
这时可以直接在内存中实用hash方法将数据划分成n个partition,每个partition交给一个线程处理,线程的处理逻辑是同3.1节类似,最后一个线程将结果归并。
该方法存在一个瓶颈会明显影响效率,即数据倾斜,每个线程的处理速度可能不同,快的线程需要等待慢的线程,最终的处理速度取决于慢的线程。解决方法是,将数据划分成c*n个partition(c>1),每个线程处理完当前partition后主动取下一个partition继续处理,直到所有数据处理完毕,最后由一个线程进行归并。
3.3 单机+单核+受限内存
这种情况下,需要将原数据文件切割成一个一个小文件,如,采用hash(x)%M,将原文件中的数据切割成M小文件,如果小文件仍大于内存大小,继续采用hash的方法对数据文件进行切割,直到每个小文件小于内存大小,这样,每个文件可放到内存中处理。采用3.1节的方法依次处理每个小文件。
3.4 多机+受限内存
这种情况下,为了合理利用多台机器的资源,可将数据分发到多台机器上,每台机器采用3.3节中的策略解决本地的数据。可采用hash+socket方法进行数据分发。
从实际应用的角度考虑,3.1~3.4节的方案并不可行,因为在大规模数据处理环境下,作业效率并不是首要考虑的问题,算法的扩展性和容错性才是首要考虑的。算法应该具有良好的扩展性,以便数据量进一步加大(随着业务的发展,数据量加大是必然的)时,在不修改算法框架的前提下,可达到近似的线性比;算法应该具有容错性,即当前某个文件处理失败后,能自动将其交给另外一个线程继续处理,而不是从头开始处理。
Top k问题很适合采用MapReduce框架解决,用户只需编写一个map函数和两个reduce 函数,然后提交到Hadoop(采用mapchain和reducechain)上即可解决该问题。对于map函数,采用hash算法,将hash值相同的数据交给同一个reduce task;对于第一个reduce函数,采用HashMap统计出每个词出现的频率,对于第二个reduce 函数,统计所有reduce task输出数据中的top k即可。
4. 总结
Top K问题是一个非常常见的问题,公司一般不会自己写个程序进行计算,而是提交到自己核心的数据处理平台上计算,该平台的计算效率可能不如直接写程序高,但它具有良好的扩展性和容错性,而这才是企业最看重的。
5. 参考资料
《十道海量数据处理面试题与十个方法大总结》:http://blog.csdn.net/v_JULY_v/archive/2011/03/26/6279498.aspx
分享到:
相关推荐
建立一个对象数组,内放5个学生的数据(学号、成绩),设立一个函数max,用指向对象数组的指针作为函数参数,在max函数中找出5个学生中成绩最高者,并输出其学号。
从一亿个数中找出最大的100个 或者n个 用了个堆
如何从1000000个数中找出出现次数最多的50个数
如从10亿个浮点数中找出最大的1万个网络搜索之类的题目
从1亿个整数中找出最大的1万个 http://blog.csdn.net/x642458/archive/2010/03/21/5400534.aspx 不成熟的优化是万恶之源。--Donald Knuth (引用Hoare的话) 另一方面,我们不能忽视效率。--Jon Bentley
通过jieba分词工具,载入自定义词典和停用词库,来获取词频高的关键词,本脚本只获取top10的关键词; 其中,停用词库是结合了目前很多常见停用库的合并;
频率测量范围为1-9999KHZ量程分别为10_100_1M三档的一个频率计频率测量范围为1-9999KHZ量程分别为10_100_1M三档的一个频率计频率测量范围为1-9999KHZ量程分别为10_100_1M三档的一个频率计频率测量范围为1-9999KHZ...
C语言程序设计-从键盘为一维整型数组输入10个整数,调用fun函数找出其中最小的数,并在main函数中输出;请编写fun函数;.c
C语言程序设计-从键盘为一维整型数组输入10个整数,调用fun函数找出其中最小的数,并在main函数中输出;本.cC语言程序设计-
可以用简单的图形界面显示文本所有英文单词的数目,并可以查询固定单词的个数
很基础的一维 数组操作,初学者可以看一下,毕竟也是我初学的时候编的
本课程将从无到有构建10亿级订单系统,彻底解决这么大的订单数据存储、查询、计算等问题,该课程将采用循序渐进方式一步一步带大家实现该系统,中间将穿插一些技术知识点讲解,让大家实现系统的同时,更深入理解其中...
对一基带频率进行10,2,100分频产生三个不同频率
项目名称: 简易频率计设计 * ******************************************** * 功能描述:1.测量信号的频率 (0.1-2MHz) * 2.测量信号周期 * 3.刷新时间可调节 (1-9S) * 4.显示单位可选择 ******...
EDA 8位10进制频率计数器【图形设计法+代码设计法】 基于quartus II 的八位10进制计数器,共一个顶层文件和两个底层文件,有图形设计法和代码设计法,解压后直接打开工程文件即可。
100HZ~10K频率测试音源,可用于各类音频测试,低通高通滤波等
分享视频教程——从无到有构建10亿级订单系统视频教程,网盘下载,配套有代码和课件,感兴趣的同学可以下载学习一下
主要介绍了PHP统计数值数组中出现频率最多的10个数字的方法,涉及php中array_count_values与arsort等方法的相关使用技巧,非常具有实用价值,需要的朋友可以参考下
实用的技术资料,可以帮助你解决一点频率计设计的阻碍
(1)提高测量频率范围,如10Hz~100KHz或更高、更低频率,...(3)测量响应时间小于等于10秒,将测量出的频率以十进制格式在实验板上的4个数码管上显示。 。 (4)若是方波能够测量方波的占空比,并通过数码管显示。