还剩15页未读,继续阅读
本资源只提供10页预览,全部文档请下载后查看!喜欢就下载吧,查找使用更方便
文本内容:
数据分析面试题及答案1.问题描述在大规模数据处理中,常遇到的一类问题是,在海量数据中找出出现频率最高的前K个数,或者从海量数据中找出最大的前K个数,这类问题通常称为“topK”问题,如在搜索引擎中,统计搜索最热门的10个查询词;在歌曲库中统计下载率最高的前10首歌等等2.当前解决方案针对topk类问题,通常比较好的方案是【分治+trie树/hash+小顶堆】,即先将数据集按照hash方法分解成多个小数据集,然后使用trie树或者hash统计每个小数据集中的query词频,之后用小顶堆求出每个数据集中出频率最高的前K个数,最后在所有topK中求出最终的topK实际上,最优的解决方案应该是最符合实际设计需求的方案,在实际应用中,可能有足够大的内存,那么直接将数据扔到内存中一次性处理即可,也可能机器有多个核,这样可以采用多线程处理整个数据集本文针对不同的应用场景,介绍了适合相应应用场景的解决方案3.解决方案
3.1单机+单核+足够大内存设每个查询词平均占8Byte,则10亿个查询词所需的内存大约是10^9*8=8G内存如果你有这么大的内存,直接在内存中对查询词进行排序,顺序遍历找出10个出现频率最大的10个即可这种方法简单快速,更加实用当然,也可以先用HashMap求出每个词出现的频率,然后求出出现频率最大的10个词
3.2单机+多核+足够大内存这时可以直接在内存中实用hash方法将数据划分成n个partition,每个partition交给一个线程处理,线程的处理逻辑是同
3.1节类似,最后一个线程将结果归并该方法存在一个瓶颈会明显影响效率,即数据倾斜,每个线程的处理速度可能不同,快的线程需要等待慢的线程,最终的处理速度取决于慢的线程解决方法是,将数据划分成c*n个partition(c1),每个线程处理完当前partition后主动取下一个partition继续处理,直到所有数据处理完毕,最后由一个线程进行归并
3.3单机+单核+受限内存这种情况下,需要将原数据文件切割成一个一个小文件,如,采用hashx%M,将原文件中的数据切割成M小文件,如果小文件仍大于内存大小,继续采用hash的方法对数据文件进行切割,直到每个小文件小于内存大小,这样,每个文件可放到内存中处理采用
3.1节的方法依次处理每个小...。