TOPK 问题

TOPK 问题

描述

如从海量数字中寻找最大的 k 个,这类问题我们称为 TOPK 问题,通常使用堆来解决:

  • 求前 k 大,用最小堆
  • 求前 k 小,用最大堆

例子

现有列表 [1, 2, 0, 3, 5], 求前 2 个大的元素。

如传入列表和 k = 2,输出 [3, 5]

思路

  1. 先放入元素前 k 个建立一个最小堆
  2. 迭代剩余元素: 如果当前元素小于堆顶元素,跳过该元素(肯定不是前 k 大) 否则替换堆顶元素为当前元素,并重新调整堆
  3. 最后获取 最小堆 中的值,即为 topk

代码如下

import heapq

class Topk:
    """获取大量元素 topk 大个元素,固定内存
    思路:
    1. 先放入元素前 k 个建立一个最小堆
    2. 迭代剩余元素:
        如果当前元素小于堆顶元素,跳过该元素(肯定不是前 k 大)
        否则替换堆顶元素为当前元素,并重新调整堆
    """
    def __init__(self, iterable, k):
        self.minheap = []
        self.capacity = k
        self.iterable = iterable

    def push(self, val):
        if len(self.minheap) >= self.capacity:
            min_val = self.minheap[0]
            if val < min_val:       # 当然你可以直接 if val > min_val 操作,这里我只是显示指出跳过这个元素
                pass
            else:
                heapq.heapreplace(self.minheap, val)    # 返回并且 pop 堆顶最小值,推出新的 val 值并调整堆
        else:
            heapq.heappush(self.minheap, val)           # 前面 k 个元素直接放入 minheap

    def get_topk(self):
        for val in self.iterable:
            self.push(val)
        return self.minheap

def test():
    import random
    i = list(range(1000))   # 这里可以是一个可迭代元素,节省内存
    random.shuffle(i)
    _ = Topk(i, 10)
    print(_.get_topk())     # [990, 992, 991, 993, 996, 997, 998, 994, 995, 999]

test()

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 利用 Scrapy 爬取知乎用户信息

    希希里之海
  • leecode刷题(30)-- 二叉树的后序遍历

    希希里之海
  • leecode刷题(28)-- 二叉树的前序遍历

    这道题我们用递归的思想很容易就能解出来。前序遍历,我们先处理根,之后是左子树,然后是右子树。

    希希里之海
  • 近期遇到的问题总结20190111

    所有表单内容都在<form></form>中,用户点击了button元素(type默认为submit,也可以用type=button的input元素)后,浏览器...

    gojam
  • Colours–颜色库,包含100种预定义的颜色和方法

    简介 Colours–颜色库,包含各种100种预定义的颜色和方法,可以简化颜色相关的开发工作. 最新示例: 点击下载 快速入门 安装 通过Cocoapods安装...

    ios122
  • ios5开发-UITableView开启编辑功能

    该例子添加UITableView编辑功能 具体功能如下 ? 功能很简单但很实用  @implementation AppDelegate @synthesiz...

    阿新
  • 学习笔记TF060:图像语音结合,看图说话

    实现人工智能3要素:语法(syntax)、语义(semantics)、推理(inference)。语言、视觉。通过语法(语言语法解析、视觉三维结构解析)和语义(...

    利炳根
  • AMD上线Linux专版驱动17.10:支持最新API接口

    近日AMD发布了Linux专用驱动AMDGPU-PRO 17.10,服务于Linux平台。这是距离上一版AMDGPU-PRO 16.60发布之后近两个月又推出的...

    BestSDK
  • Funny Kind

    事实上我们编写的 config.yaml,在文末的命令行中并没有引用,所以其中的快速安装的结果完全是 Kind 的功劳,和之前的证书操作、镜像操作没有一毛钱的关...

    崔秀龙
  • 经典面试题-如何给tomcat指定大小的内存

    版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。 ...

    cwl_java

扫码关注云+社区

领取腾讯云代金券