• feifei
    2018-12-02
    有一个访问量非常大的新闻网站,我们希望将点击量排名 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

    展开
     14
     423
  • Miletos
    2018-11-28
    “如果新加入的数据小于等于大顶堆的堆顶元素,我们就将这个新数据插入到大顶堆;如果新加入的数据大于等于小顶堆的堆顶元素,我们就将这个新数据插入到小顶堆。”

    1. 这里不太对劲,前文中说到,小顶堆的堆顶大于大顶堆的堆顶。

    如果新进元素在小顶堆堆顶和大顶堆堆顶元素值之间,没有规定插入哪个堆。

    我觉得,是不是只要判断一次就可以了。新进元素值大于等于小顶堆堆顶元素的,插入小顶堆,否则插入大顶堆。
    当某一个堆数据过多时再重新移动堆顶元素。

    2. 求中位数的源数据中,是否允许重复数据?
    展开

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

     2
     63
  • 蔷薇骑士
    2018-12-14
    定时任务这个例子感觉有问题吧,定时任务是动态加入的,假设当前堆顶的任务是一个小时后的,难道这一个小时都不做扫描吗,随时可能会加入需要更早执行的任务
     8
     50
  • 守着云开
    2018-11-28
    10亿关键词分片之后 每个文件并不一定有1亿的关键词吧 老师
     3
     34
  • oatlmy
    2018-11-28
    老师,请问为什么评价算法性能是根据时间和空间复杂度,而不是别的参数?是因为计算机结构是冯诺依曼体系,除了输入输出设备和控制器,就剩下运算器和存储器了吗?

    作者回复: 你理解的没错

    
     30
  • 想当上帝的司机
    2018-12-23
    堆求topK的静态数据 应该是先把堆填满 再拿数组中的元素跟堆顶比较吧
     2
     22
  • 辉哥
    2018-12-02
    思考题:1,维护两个散列表,一个是一小时新增的点击量的散列表,以新闻id为键,点击次数为值。一个是全部点击量的散列表。每隔一小时把新增的散列表的数据同步到全部点击量的散列表。然后把这小时内有变化的全部点击量的散列表的数据(即此小时有新增点击量的新闻数据)和我们维护的10个元素小顶堆堆顶进行比较,比堆顶的点击量大的,则使用该元素替换堆顶,再进行堆化。比堆顶点击量小的则不做处理。然后比较完,根据堆顶的10个元素的id,从数据库读取相应的新闻摘要显示在banner上。除此之外,还要把变化后的全部点击量散列表同步到数据库。因为保存的是新闻id,所以散列表长度不会很大,所占用的内存也不会很大。而每个小时新增的访问量的新闻id数也不会很多,毕竟很多人只会阅读热门消息。所以新增的点击量的新闻数据假设为k,则每小时同步小顶堆的时间负责度为o(klg 10);
    
     19
  • 豪华
    2018-11-28
    老师,分片求取前十是不是有bug,如果有一个关键词在每一组分片中都是前第十一位,在整个十亿中个数总和是第一位,是不是用分片求出了错误的结果呢?

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

     1
     18
  • Aaaaaaaaaaayou
    2019-02-20
    topK 是不是应该先要填满堆,后面插入的时候再做删除操作

    作者回复: 是的。

     1
     14
  • ZX
    2018-12-02
    看了这一章,发现堆删除任意元素这个方法毫无意义啊。只有删除堆顶元素才有意义

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

    
     9
  • ALAN
    2018-11-28
    1:建一个散射列表,key为点击网址,value为点击次数。散射列表通过从log中计算得来。
    2:建一个10个数据的小顶堆,数据值为点击次数,扫描散射列表,新元素次数比堆顶元素大则删除堆顶元素,插入新元素,小则继续扫描散射列表。
    3:扫描完整个散射列表后,即得到top 10点击量,将点击网址存储在数组A中。数组A一个小时更新一次。
    4:散射列表实时更新,小顶堆也实时更新,以一小时为间隔,将小顶堆结果更新到数组A中。
    
     8
  • happiness_xcy
    2018-12-22
    方案前提,所有数据都保存在一台服务器的内存中,不考虑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的数量。
    展开
    
     6
  • 攻城拔寨
    2018-12-09
    如果我要1%到99%响应时间,这样建的堆就有点多了

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

    
     6
  • Jerry银银
    2018-11-28
    早起的鸟儿读算法。


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

    这题也可以使用MapReduce算法
    展开
     1
     6
  • CathyLin
    2019-07-14
    还在继续赶大部队 LOL 但是不会放弃的!加油!
    边做 Leetcode 边学习老师的课程有了更深刻的理解!
    老师说的利用堆求 Top K 的应用对应于 Leetcode 973,大家有兴趣的可以去试一下!
    
     5
  • 丁丁历险记
    2019-09-29
    人生也需要维护一个优先级队列
    
     4
  • gxlemon
    2018-12-18
    高性能定时器,使用堆数据结构不一定是最优解,“环形队列”也许更好一点

    作者回复: 👍 各有利弊吧

    
     4
  • 竹林清风
    2018-12-05
    思考题:
    1、实时建立散列表,key是新闻的摘要,value是点击量;
    2、建立一个10的小顶堆,每隔一个小时扫描一次散列表,根据点击量大小放入到小顶堆中,扫描完散列表后即出现Top10 的新闻点击量。
    
     4
  • Paul Shan
    2019-07-19
    对于百分数的问题,我个人更倾向于用红黑树加计数来实现,可以在log n的复杂度内求出任意百分位的元素,虽然红黑树本身比较复杂,但是有现成的实现,这种方法比较灵活。
    
     3
  • 小花小黑的铲屎官
    2018-12-14
    我们遍历这 10 亿个关键词,并且通过某个哈希算法对其求哈希值,然后哈希值同 10 取模,得到的结果就是这个搜索关键词应该被分到的文件编号。
    这样并不能保证每个文件都是一亿条数据吧?可能多也可能少吧?

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

    
     3
我们在线,来聊聊吧