System-Design高频:Top K 问题

普通版寻找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。

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • 背景 一年多以前我在知乎上答了有关LeetCode的问题, 分享了一些自己做题目的经验。 张土汪:刷leetcod...
    土汪阅读 12,768评论 0 33
  • 一、基本数据类型 注释 单行注释:// 区域注释:/* */ 文档注释:/** */ 数值 对于byte类型而言...
    龙猫小爷阅读 4,288评论 0 16
  • 教你如何迅速秒杀掉:99%的海量数据处理面试题 本文经过大量细致的优化后,收录于我的新书《编程之法》第六章中,新书...
    Helen_Cat阅读 7,455评论 1 39
  • 进藏第五天,林芝不愧为藏区的小江南,随着海拨的降低,终于拥有了一个入藏以来最舒服的睡眠。 然而人总是有惰性的,随着...
    墨莫0801阅读 309评论 0 1
  • 新加的读书群,要求昵称用实名不用网名。我告诉他们说,我用的是我的字,不是网名。但是字这种事物,现在是不普及的,要求...
    金明啊阅读 153评论 0 0