10亿条ip访问数据,从中查找访问次数最多的10条 topk问题

题目分析

  1. 10亿条数据:大数据处理方面-分治
  2. 访问次数最多,topk问题-排序算法方面

解题思路

  1. 直接排序,数据量太大,肯定不行
  2. 必须先进行分治:hash方法(相同数据会被汇总到一起)
  3. 分治后,对每个小块应该如何排序查找前k个,最后将各分治块得出的topk汇总到一起再得出topk即是结果
    1. hashmap:时间复杂度为O(n),空间复杂度为O(n)
    2. 堆排序:topk问题使用最小堆,时间复杂度为O(nmlogm),n为总数量,m为topk中的k
    堆排序堆排序示例

参考资料

  1. 海量数据中找出前k大数(topk问题)
  2. 算法入门:堆排序

未经允许不得转载:开心猿社区 » 10亿条ip访问数据,从中查找访问次数最多的10条 topk问题

赞 (0)

评论 0

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址