美文网首页
System-Design高频:Top K 问题

System-Design高频:Top K 问题

作者: 98Future | 来源:发表于2017-11-04 08:35 被阅读0次

普通版寻找Top-K问题

用HashMap+priorityQueue

HashMap<key, 次数>

然后根据HashMap的每个Key 创建Node,Node里面包含data和frequency信息。

然后把Node放入PriorityQueue里,comparator按照frequency来存储。

进阶版:如果Input的data很大,Single Machine的内存装不下

Naive做法就是直接分成好几个部分分配个多台机器

但是这里错误很明显!

假设Google被分到各个机器了。然后每个机器算出每台的Top K。Google虽然总次数排名第一,但是分散到了每个机器在每个机器都不是第一,这样我们的结果就是错的!

所以应该:

这里其实是不对的,NBA总次数有30呢!而且NBA其实也没用group到一台机器。

Divide-rehash:

进阶:

如果是实时计算Top-K

空间大部分会留给那些热搜度很低的词,很浪费。所以用Approx Top K

之前是每个单词有一个空间。现在是按hash来分空间。同一个Hash的都去一个地方。

这样有可能会有一些error 比如说单词A出现99次,单词B没出现过 但是由于hash一样,它直接你能够算作出现了99+1次

Solution:

别的方法:

Map-reduce的word count

还是会用到treeMap. 当mapreduce每算出一个key的结果,先存在Map里,如果有更高的结果,再把之前的kick out。

相关文章

网友评论

      本文标题:System-Design高频:Top K 问题

      本文链接:https://www.haomeiwen.com/subject/fncfmxtx.html