Python heapq:用固定容量保留数据流里最大的 K 个值
【摘要】 假设程序持续收到请求耗时,只想保留最大的三个值。不必存下所有记录,也不必每来一条就重新排序:只要知道当前候选里谁最小,就知道新值能不能进榜。 最小堆记录的是门槛当前候选为 10、12、15,门槛就是 10。新值 3 应被拒绝;新值 14 则淘汰 10。最小堆的 heap[0] 是最小值,但堆本身并不是排好序的列表。heappushpop 等价于先把新值纳入比较范围,再淘汰最小值。heapre...
假设程序持续收到请求耗时,只想保留最大的三个值。不必存下所有记录,也不必每来一条就重新排序:只要知道当前候选里谁最小,就知道新值能不能进榜。
最小堆记录的是门槛
当前候选为 10、12、15,门槛就是 10。新值 3 应被拒绝;新值 14 则淘汰 10。最小堆的 heap[0] 是最小值,但堆本身并不是排好序的列表。
heappushpop 等价于先把新值纳入比较范围,再淘汰最小值。heapreplace 则一定移除旧堆顶,再加入新值。无条件对初始堆执行 heapreplace(heap, 3) 会丢掉应该保留的 10。若用后者,需要先检查 heap[0] < value。
from heapq import heappush, heappushpop, heapreplace
heap = [10, 12, 15]
assert (heappushpop(heap, 3), sorted(heap)) == (3, [10, 12, 15])
assert (heappushpop(heap, 14), sorted(heap)) == (10, [12, 14, 15])
heap = [10, 12, 15]
assert (heapreplace(heap, 3), sorted(heap)) == (10, [3, 12, 15])
def top_k(values, k):
if k <= 0:
return []
heap = []
for value in values:
if len(heap) < k:
heappush(heap, value)
else:
heappushpop(heap, value)
return sorted(heap, reverse=True)
assert top_k(iter([10, 12, 15, 3, 14]), 3) == [15, 14, 12]
assert top_k(iter([7, 7, 4, 7]), 2) == [7, 7]
assert top_k(iter([2, 1]), 5) == [2, 1]
assert top_k(iter([1]), 0) == []
assert top_k(iter([]), 3) == []
堆没满时直接加入,堆满后才筛选,输入不足 K 条时就会保留全部。重复值按出现次数保留,不自动去重。候选只占 O(min(N, K)) 空间;每次堆更新最多 O(log K)(K ≥ 2),最后才对候选排序。一次性查询可以直接用 heapq.nlargest,持续维护时再考虑自己持有堆。上述断言已在 Python 中运行通过。
参考:Python 标准库文档 heapq 模块。
【声明】本内容来自华为云开发者社区博主,不代表华为云及华为云开发者社区的观点和立场。转载时必须标注文章的来源(华为云社区)、文章链接、文章作者等基本信息,否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱:
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论(0)