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

时间:2022-03-07 11:51:01

一、梳理审题

一、看清题目:

注意这个题目的量词,这个文件中有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