大量数据 TOP-K

参考资料:https://www.cnblogs.com/qlky/p/7512199.html

• 小顶堆(最大n个数字)或者大顶堆(最小n个数字)

  参考资料:https://blog.csdn.net/cdnight/article/details/11650983 小顶堆 就是每个节点度比子节点小 大顶堆 每个节点比子节点大

  小顶堆思路(大顶堆和这个一样 就是建立的堆和比较的时候反着来):

  1. 建立总量中的n个数字的小顶堆
  2. 然后进行循环扫描
  3. 每次元素度和当前的堆顶节点比较 如果元素大于小顶堆的顶部节点 那么元素入堆 并且删除堆顶

• quick select 算法
  利用类似快排的思路 找任意一个数 x 比x大的放左边数组 小的放右边数组 一次递归下去

m条int数据 获取最大的n条数据

• 排序 就硬排序

• 淘汰法 创建前n个元素容器 迭代元素 如果元素比n个元素的最小元素大那么删除最小元素 把当前元素添加到容器中

• 分治法 m个元素拆分 k份
  每一份排序 获取最大的n条数据 那么最大的n条数据一定在 k*n的数据中 如果k*n 数据量合适了 就排序 获取前n条数据 如果k*n数据量还是很大 那么再次拆分 但是要保证 每一份的数据条数要大于n

• hash法 对m个元素做hash去重处理 如果重复数据很多 会极大的减少元素数量 然后看情况使用分治法或者直接排序

• 最小堆法 取前n个数据 建堆
  然后按照最小堆法 每次元素度和当前的堆顶节点比较 如果元素大于小顶堆的顶部节点 那么元素入堆 并且删除堆顶
  循环迭代 循环完毕 当前n个元素的堆就是最大的n个元素

m个元素中 获取重复数量最多的n个元素

也是属于top-k类型问题 只是计算维度变成统计出现次数最多的情况

• 直接hash统计
  直接建立m个元素的hash key为元素 value为出现次数 如果数据重复率比较高 这种方式是最直接的

• 分治+hash 数据量过大无法全部放进内存处理 而且重复率较低
  先拆分 hash(m中的元素)%k 这个公式能够将hash相同的元素、hash冲突的元素、 hash之后取余相等的元素拆分到一起
  k为一个合理的大小数据 例如总数据量 8g 内存只有4m 那么拆分大概拆分2048份 那么每个数据组是小于4m的 那么就可以加载到内存中计算
  然后对每一组数据 做hash统计 然后按照value大小 获取最大的前n个元素
  然后合并结果 k*n 然后计算k*n中的最大的n个元素即可 如果k*n 还是很大 继续拆分即可