前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >一个很大的文件,存放了10G个整数的乱序数列,如何用程序找出中位数。

一个很大的文件,存放了10G个整数的乱序数列,如何用程序找出中位数。

作者头像
翎野君
发布2023-05-12 19:57:45
2900
发布2023-05-12 19:57:45
举报
文章被收录于专栏:翎野君翎野君

一、梳理审题

一、看清题目:

注意这个题目的量词,这个文件中有10G个整数,而不是这个文件占了10G的内存空间。

二、一些疑问:

在计算机中我们讲的G、M等都是存储容量的概念,但是一般都会在会面加上B,即Byte字节的意思,如1GB=1024MB,而在计算机中G默认为是GB的缩写。 所以这个题目我认为出的不严谨,因为10G个,”个“字作为一个量词,前面应该是个单纯的数字,但是这里却说的是10G,存储容量?所以搞的人有些云里雾里,包括网络上的一些博客,对于这一点都是一笔带过,没有做过多的讨论或思索。

三、自己假设:

我在这里姑且揣测题目作者所认为的10G个等同于10*1024*1024*1024个,但明显题目中的这个表述是有问题的。

二、分析问题

一个文件中有10G个!个!数,一共2G内存,求中位数,10G是偶数,那也就第n/2个数和第(n+1)/2个数相加除以二。

10G=10*1024*1024*1024,1024=2^10

10G=10*2^30=5*2^31

第一步:在计算机中如何表示10G个这个数字?

因为5*2^31 > 2^32,所以要表示10G这个数量(假如文件中有10G个1),32位是存不下的,我们要用64位进行存储。

第二步:分区间

一共有2G内存,那么一次性读入内存的数的个数是 2G / 64bit(按byte和bit去除得到的只是一个比例) = 2^31 /2^3= 2^28个,单位就是个,不是M等等,网上的很多文章中256M的表述是错的,因为M在计算机中是MB的缩写是空间单位,而在数学中M=兆=一百万。

第三步:求区间的表示范围

区间段有限,取值范围较大,一共有2^32个数(0 ~ 2^31-1),但是只有2^28个区间段(区间段可以理解为容器或者桶) 则一个桶里面要容纳 2^32/2^28=2^4=16,每个区间段要放16个数。

即第一个桶放0-15的数,而16-31则放在第二个桶里面...以此类推

第四步:第一次遍历

然后我们开始遍历,将10G个数中的每一个数都放到对应的桶里面,如当前读到数字为18则放到第二个桶里面,第二个桶中所含有的数字总个数+1。 遍历完,我们将10G个数中的每一个数都放在,他们应在的那个区间段(桶)里面了,这个2^28个桶是在内存中的,每个桶64位,恰好装满2G内存。

第五步:确定中位数所在的区间

那么然后,我们对于这个区间段队列中的每个段的总个数进行累加,当加到第5G个!个!数时,停止,那么第!第!5G个数所在的区间段就是中位数所在的区间段,将此区间段表示为[a,a+15],在此区间段之前的所有区间段所包含数字的总个数为m。

释放掉内存后...

第六步:确定最终的位置

再次遍历10G个数,统计出现在[a,a+15]这个区间段中的,每个值,所出现的个数,最多有可能有16个数字,当然也有可能只有一个,按照a..a+15进行排序,设为n0,n1...n15。

当m+n0+n1...+nx 首次大于5G时,此时的 a+x 就是所求的中位数(当总数为奇数时),为偶数时则是(a+x+a+x-1)/2,当然有可能a+x和a+x-1在两个区间中。

这里有一个极端情况,就是所有10G个数都落在同一个桶里面,那么在第二次遍历的时候就需要对全部10G个数进行遍历。

参考文章:http://blog.sina.com.cn/s/blog_8e9c63c70101f5pl.html

本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2018-08-16,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

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

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

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 一、梳理审题
    • 一、看清题目:
      • 二、一些疑问:
        • 三、自己假设:
        • 二、分析问题
          • 第一步:在计算机中如何表示10G个这个数字?
            • 第二步:分区间
              • 第三步:求区间的表示范围
                • 第四步:第一次遍历
                  • 第五步:确定中位数所在的区间
                    • 第六步:确定最终的位置
                    相关产品与服务
                    容器服务
                    腾讯云容器服务(Tencent Kubernetes Engine, TKE)基于原生 kubernetes 提供以容器为核心的、高度可扩展的高性能容器管理服务,覆盖 Serverless、边缘计算、分布式云等多种业务部署场景,业内首创单个集群兼容多种计算节点的容器资源管理模式。同时产品作为云原生 Finops 领先布道者,主导开源项目Crane,全面助力客户实现资源优化、成本控制。
                    领券
                    问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档