一日一技:小内存使用最小堆从大量数据中寻找最小的N个数

如今,我们的硬盘空间远远大于内存。所以很容易出现硬盘中放得下的数据,在内存中放不下的情况。

现在我们有一个100GB的文本文件,它的内容如下:

19930021-913287607653......

每一行是一个数字。这些数字是没有顺序的。

现在我需要从这个100GB的文件里面,找到最大的100个数字。电脑内存为1GB。

由于内存非常小,因此不可能把全部数据读入内存,先排序再取最大的100个数。那么我们就需要边读文件边排序,并始终保留最大的100个数字。

肯定有同学会想到使用列表来解决这个问题。维护一个长度为100的列表,如果列表不满100,就把新来的数字加入进去;如果列表已经满了100,那么如果这个新来的数字小于列表里面的最小值,就直接丢弃;如果大于列表里面的最小值,那么就把原来的最小值丢弃,把新的数字插入进去。

这篇文章里面,我们将会使用上一篇文章讲到的 heapq来实现这个目的。

Python的 heapq实现的是一个最小堆,最小堆有如下性质:

  1. 根节点始终是最小的
  2. 最小堆是完全二叉树
  3. 每个节点的两个子节点都不会比它小

所以,我们只需要维护一个有100个节点的最小堆即可。

那么代码如下:

import heapq
with open('100GBfile.txt', encoding='utf-8') as f:    heap = []    for num_str in f:        num = int(num_str)        if len(heap) < 100:            heapq.heappush(heap, num)        else:            if num > heap[0]:                heapq.heapreplace(heap, num)print(f'最大的100个数为:{heap}')

在Python 3里面,文件句柄f是一个生成器,对它使用for循环迭代,可以一行一行读取文件的内容。文本文件读出来的内容一定是字符串,所以需要使用 int(num)转换为数字。如果堆的节点数不够100,那么直接把数字插入堆里即可,heapq会自动决定这个数字在堆里面的位置。

由于最小堆的根节点一定是最小值,所以只需要比较新来的数字与根节点的大小即可,当新来的数字比根节点大时,就移除根节点,把它加入堆里面,然后heapq会自动跳转堆的结果,使这个堆仍然是最小堆。

当循环把大文件全部读完以后,堆里面的100个数字就是最大的100个数了。

原文发布于微信公众号 - 未闻Code(itskingname)

原文发表时间:2019-07-05

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

发表于

我来说两句

0 条评论
登录 后参与评论

扫码关注云+社区

领取腾讯云代金券