认识达内从这里开始

认真做教育专心促就业

如何高效的处理亿万级数据？（7）

发布：青岛达内
来源：青岛达内
时间：2019-03-20 14:05

青岛达内的小编总结，海量数据分布在10台电脑中，想个办法高效统计出这批数据的TOP10,如果每个数据元素只出现一次，而且只出现在某一台机器中，那么可以采取以下步骤统计出现次数TOP10的数据元素：
堆排序
在每台电脑上求出TOP10,可以采用包含10个元素的堆完成（TOP10小，用最大堆，TOP10大，用最小堆，比如求TOP10大，我们首先取前10个元素调整成最小堆，如果发现，然后扫描后面的数据，并与堆顶元素比较，如果比堆顶元素大，那么用该元素替换堆顶，然后再调整为最小堆。最后堆中的元素就是TOP10大）。
求出每台电脑上的TOP10后，然后把这100台电脑上的TOP10组合起来，共1000个数据，再利用上面类似的方法求出TOP10就可以了。
如果同一个元素重复出现在不同的电脑中呢
这个时候，你可以有两种方法
遍历所有数据，重新hash取模，使同一个元素只出现在单独的一台电脑中，然后采用上面所说的方法，统计每台电脑中各个元素的出现次数找出TOP10,继而组合100台电脑上的TOP10,找出最终的TOP10
暴力求解：直接统计每台电脑中各个元素的出现次数，然后把同一个元素在不同机器中的出现次数相加，最终从所有数据中找出TOP10

10个文件，每个1G,每个文件的每一行存放的都是用户的query,每个文件的query都可能重复。要求按照query的频度排序

青岛达内

方案1
Hash映射
顺读10个文件，按照hash（query）%10将query写到另外10个文件（记为a0,a1,a9）中
这样新生成的文件每个的大小大约也1G）（假设hash函数较好）
HashMap统计
找一台内存在2G左右机器，依次用HashMap（query, query_count）统计每个query频度
注：HashMap（query,query_count）是统计每个query的出现次数，不是存储他们的值，出现一次，则count+1
堆/快速/归并排序
利用快速/堆/归并排序按频率排序，将排序好的query和对应的query_cout输出到文件，就得到了10个排好序的文件
最后，对这10个文件进行归并排序（内/外排相结合）
方案2
一般query的总量是有限的，只是重复的次数比较多而已，可能对于所有的query,一次性就可以加入到内存了。这样，我们就可以采用trie树/HashMap等直接统计每个query出现的次数，然后按次数做快速/堆/归并排序
方案3
与方案1类似，但在做完hash,分成多个文件后，可以交给多个文件来处理，采用分布式的架构来处理（比如MapReduce），最后再进行合并
以上就是青岛达内给大家做的内容详解，更多关于UI的学习，请继续关注青岛达内

< 上一篇：如何高效的处理亿万级数据？（6）

下一篇：如何高效的处理亿万级数据？（8） >