前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >一日一技:小内存使用最小堆从大量数据中寻找最小的N个数

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

作者头像
青南
发布2019-07-10 15:04:28
1.5K1
发布2019-07-10 15:04:28
举报
文章被收录于专栏:未闻Code

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

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

代码语言:javascript
复制
19930021-913287607653......

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

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

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

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

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

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

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

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

那么代码如下:

代码语言:javascript
复制
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个数了。

本文参与 腾讯云自媒体同步曝光计划,分享自微信公众号。
原始发表:2019-07-05,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 未闻Code 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档