29 | 堆的应用：如何快速获取到Top 10最热门的搜索关键词？

精选留言(134)

• 

  feifei

  有一个访问量非常大的新闻网站，我们希望将点击量排名 Top 10 的新闻摘要，滚动显示在网站首页 banner 上，并且每隔 1 小时更新一次。如果你是负责开发这个功能的工程师，你会如何来实现呢？
  
  我的思路是这样子，
  1，对每篇新闻摘要计算一个hashcode，并建立摘要与hashcode的关联关系，使用map存储，以hashCode为key，新闻摘要为值
  2，按每小时一个文件的方式记录下被点击的摘要的hashCode
  3，当一个小时结果后，上一个小时的文件被关闭，开始计算上一个小时的点击top10
  4，将hashcode分片到多个文件中，通过对hashCode取模运算，即可将相同的hashCode分片到相同的文件中
  5，针对每个文件取top10的hashCode，使用Map<hashCode,int>的方式，统计出所有的摘要点击次数，然后再使用小顶堆（大小为10）计算top10,
  6，再针对所有分片计算一个总的top10,最后合并的逻辑也是使用小顶堆，计算top10
  7，如果仅展示前一个小时的top10,计算结束
  8，如果需要展示全天，需要与上一次的计算按hashCode进行合并，然后在这合并的数据中取top10
  9，在展示时，将计算得到的top10的hashcode，转化为新闻摘要显示即可
  
  老师，你讲的这些例子，我觉得对我的工作和学习很有帮助，于是我花了一个周末将这一章节，将你所讲的堆的应用示例，全部翻译成了代码，并做了相关的验证，感觉自己收获很多，我也将这块代码上传了github，欢迎老师你的指正，需要的同学，也可以一起交流，
  
  1，合并有序小文件
  https://github.com/kkzfl22/datastruct/tree/master/src/main/java/com/liujun/datastruct/heap/solution/margeSmailFile
  2，高性能定时器的应用
  https://github.com/kkzfl22/datastruct/tree/master/src/main/java/com/liujun/datastruct/heap/solution/highTimeSchedule
  3，求topk
  https://github.com/kkzfl22/datastruct/tree/master/src/main/java/com/liujun/datastruct/heap/solution/topK
  4，求中位数
  https://github.com/kkzfl22/datastruct/tree/master/src/main/java/com/liujun/datastruct/heap/solution/midnum
  5 ,大文件的关键字的统计
  https://github.com/kkzfl22/datastruct/tree/master/src/main/java/com/liujun/datastruct/heap/solution/bigFileTopN
  
  

  2018-12-02

   8

   364
• 

  Miletos

  “如果新加入的数据小于等于大顶堆的堆顶元素，我们就将这个新数据插入到大顶堆；如果新加入的数据大于等于小顶堆的堆顶元素，我们就将这个新数据插入到小顶堆。”
  
  1. 这里不太对劲，前文中说到，小顶堆的堆顶大于大顶堆的堆顶。
  
  如果新进元素在小顶堆堆顶和大顶堆堆顶元素值之间，没有规定插入哪个堆。
  
  我觉得，是不是只要判断一次就可以了。新进元素值大于等于小顶堆堆顶元素的，插入小顶堆，否则插入大顶堆。
  当某一个堆数据过多时再重新移动堆顶元素。
  
  2. 求中位数的源数据中，是否允许重复数据？

  作者回复: 1 你说的对 我改下 多谢指正
  2 可以重复

  2018-11-28

   2

   57
• 

  蔷薇骑士

  定时任务这个例子感觉有问题吧，定时任务是动态加入的，假设当前堆顶的任务是一个小时后的，难道这一个小时都不做扫描吗，随时可能会加入需要更早执行的任务

  2018-12-14

   8

   48
• 

  守着云开

  10亿关键词分片之后 每个文件并不一定有1亿的关键词吧 老师

  2018-11-28

   3

   33
• 

  oatlmy

  老师，请问为什么评价算法性能是根据时间和空间复杂度，而不是别的参数？是因为计算机结构是冯诺依曼体系，除了输入输出设备和控制器，就剩下运算器和存储器了吗？

  作者回复: 你理解的没错

  2018-11-28

  

   24
• 

  想当上帝的司机

  堆求topK的静态数据 应该是先把堆填满 再拿数组中的元素跟堆顶比较吧

  2018-12-23

   2

   20
• 

  辉哥

  思考题：1，维护两个散列表，一个是一小时新增的点击量的散列表，以新闻id为键，点击次数为值。一个是全部点击量的散列表。每隔一小时把新增的散列表的数据同步到全部点击量的散列表。然后把这小时内有变化的全部点击量的散列表的数据（即此小时有新增点击量的新闻数据）和我们维护的10个元素小顶堆堆顶进行比较，比堆顶的点击量大的，则使用该元素替换堆顶，再进行堆化。比堆顶点击量小的则不做处理。然后比较完，根据堆顶的10个元素的id，从数据库读取相应的新闻摘要显示在banner上。除此之外，还要把变化后的全部点击量散列表同步到数据库。因为保存的是新闻id，所以散列表长度不会很大，所占用的内存也不会很大。而每个小时新增的访问量的新闻id数也不会很多，毕竟很多人只会阅读热门消息。所以新增的点击量的新闻数据假设为k,则每小时同步小顶堆的时间负责度为o(klg 10);

  2018-12-02

  

   16
• 

  豪华

  老师，分片求取前十是不是有bug，如果有一个关键词在每一组分片中都是前第十一位，在整个十亿中个数总和是第一位，是不是用分片求出了错误的结果呢？

  作者回复: 不会的 相同的关键词经过哈希之后只会到一台机器

  2018-11-28

  

   16
• 

  Aaaaaaaaaaayou

  topK 是不是应该先要填满堆，后面插入的时候再做删除操作

  作者回复: 是的。

  2019-02-20

   1

   12
• 

  ZX

  看了这一章，发现堆删除任意元素这个方法毫无意义啊。只有删除堆顶元素才有意义

  作者回复: 是的啊 没有说过删除任意元素呢

  2018-12-02

  

   8
• 

  ALAN

  1:建一个散射列表，key为点击网址，value为点击次数。散射列表通过从log中计算得来。
  2:建一个10个数据的小顶堆，数据值为点击次数，扫描散射列表，新元素次数比堆顶元素大则删除堆顶元素，插入新元素，小则继续扫描散射列表。
  3:扫描完整个散射列表后，即得到top 10点击量，将点击网址存储在数组A中。数组A一个小时更新一次。
  4:散射列表实时更新，小顶堆也实时更新，以一小时为间隔，将小顶堆结果更新到数组A中。

  2018-11-28

  

   8
• 

  happiness_xcy

  方案前提，所有数据都保存在一台服务器的内存中，不考虑HA、数据更新冲突等情况。我们假设每条新闻都有一个全局唯一的新闻ID，使用hashmap(map_a)来保存每篇新闻的访问量，key为新闻ID，value为当前访问总次数。使用另一个hashmap(map_b)来保存一个周期内map_a中value值发生变化的key。
  
  整个方案分为三个阶段，堆的初始化、hashmap实时变更、堆更新。
  初始化阶段：建立一个大小为10的小顶堆，遍历此时的hashmap，完成堆的初始化。
  hashmap实时变更阶段：保存在当前周期内，将map_a中value产生变化的key到map_b中。
  堆更新阶段：在一个周期结束后，遍历map_b，并将map_a中保存的value与当前堆顶进行比较，如果大于堆顶，则删除堆顶，并插入该value，如果小于堆顶则不做处理。遍历完map_b之后，该堆保有了上个周期访问量top10的新闻id和value。最后清空map_b，为下一个周期作准备。最坏时间复杂度为O(nlog10)，其中n为map_b中key的数量。
  

  2018-12-22

  

   6
• 

  CathyLin

  还在继续赶大部队 LOL 但是不会放弃的！加油！
  边做 Leetcode 边学习老师的课程有了更深刻的理解！
  老师说的利用堆求 Top K 的应用对应于 Leetcode 973，大家有兴趣的可以去试一下！

  2019-07-14

  

   5
• 

  小新是也

  如果我要1%到99%响应时间，这样建的堆就有点多了

  作者回复: 这需求...具体问题具体分析吧

  2018-12-09

  

   5
• 

  竹林清风

  思考题：
  1、实时建立散列表，key是新闻的摘要，value是点击量；
  2、建立一个10的小顶堆，每隔一个小时扫描一次散列表，根据点击量大小放入到小顶堆中，扫描完散列表后即出现Top10 的新闻点击量。

  2018-12-05

  

   4
• 

  Jerry银银

  早起的鸟儿读算法。
  
  
  原理上跟统计热门搜索关键词类似。后台起一个定时任务，从最新被新点击的新闻日志文件中统计出每条新闻的点击量(也得类似于老师那样使用散列表)，然后建立和维护内存中大小为10的最大堆，这样网站点击次数Top10的新闻就被统计出来了。
  
  这题也可以使用MapReduce算法

  2018-11-28

   1

   4
• 

  小花小黑的铲屎官

  我们遍历这 10 亿个关键词，并且通过某个哈希算法对其求哈希值，然后哈希值同 10 取模，得到的结果就是这个搜索关键词应该被分到的文件编号。
  这样并不能保证每个文件都是一亿条数据吧？可能多也可能少吧？

  作者回复: 是的 你说的没错

  2018-12-14

  

   3
• 

  小美

  王老师 第一点合并有序小文件 为什么要用到优先级队列 和 堆还是不理解。两个比最小取出合并，只要两个数组是有序就可以了，快排成有序，从小到大比较合并，不可以吗，为什么要用到优先级队列，方便老师解答下吗

  作者回复: 没太看懂你说的 用优先级是为了效率

  2018-11-28

   2

   3
• 

  AF

  Hadoop、Spark入门demo——wordcount了解下

  2018-11-28

  

   3
• 

  Jerry银银

  早起的鸟儿读算法。
  
  文章中『解答开篇』部分，说是扫描1亿个热门关键词，这应该是错别字吧，应该是10亿个吧。看了好几遍，我应该没理解错吧😄
  
  老师说使用散列表统计10亿个搜索关键词的频率，但是这里的约束条件是10亿个关键词中确实有很多重复，而且去重之后的数据，内存中是能够放得下的。如果单机内存放不下，应该就不能这么做了
  
  ---------------------------------------------------------
  
  以上是我早上本来要留言的，但是并没有一字不漏的看完文章。我回头一想不对，文章中肯定会考虑到这个情况。当我看完，我就把以上留言删了。
  
  唉，阅读时，犯了一个低级错误，记录在此，提醒自己

  作者回复: 是我写错了 不好意思 马上修改

  2018-11-28

  

   3