首页 > 模式算法 > 腾讯面试题:10G 个整数,乱序排列,要求找出中位数。内存限制为 2G。
2015
04-14

腾讯面试题:10G 个整数,乱序排列,要求找出中位数。内存限制为 2G。

题目:在一个文件中有 10G 个整数,乱序排列,要求找出中位数。内存限制为 2G。只写出思路即可(内存限制为 2G的意思就是,可以使用2G的空间来运行程序,而不考虑这台机器上的其他软件的占用内存)。

关于中位数:数据排序后,位置在最中间的数值。即将数据分 成两部分,一部分大于该数值,一部分小于该数值。中位数的位置:当样本数为奇数时,中位数=(N+1)/2 ; 当样本数为偶数时,中位数为N/2与1+N/2的均值(那么10G个数的中位数,就第5G大的数与第5G+1大的数的均值了)。

分析:明显是一道工程性很强的题目,和一般的查找中位数的题目有几点不同。
1. 原数据不能读进内存,不然可以用快速选择,如果数的范围合适的话还可以考虑桶排序或者计数排序,但这里假设是32位整数,仍有4G种取值,需要一个16G大小的数组来计数。

2. 若看成从N个数中找出第K大的数,如果K个数可以读进内存,可以利用最小或最大堆,但这里K=N/2,有5G个数,仍然不能读进内存。

3. 接上,对于N个数和K个数都不能一次读进内存的情况,《编程之美》里给出一个方案:设k<K,且k个数可以完全读进内存,那么先构建k个数的堆,先 找出第0到k大的数,再扫描一遍数组找出第k+1到2k的数,再扫描直到找出第K个数。虽然每次时间大约是nlog(k),但需要扫描ceil(K/k) 次,这里要扫描5次。

解法:首先假设是32位无符号整数。
1. 读一遍10G个整数,把整数映射到256M个区段中,用一个64位无符号整数给每个相应区段记数。
说 明:整数范围是0 - 2^32 - 1,一共有4G种取值,映射到256M个区段,则每个区段有16(4G/256M = 16)种值,每16个值算一段, 0~15是第1段,16~31是第2段,……2^32-16 ~2^32-1是第256M段。一个64位无符号整数最大值是0~8G-1,这里先不考虑溢出的情况。总共占用内存256M×8B=2GB。

2. 从前到后对每一段的计数累加,当累加的和超过5G时停止,找出这个区段(即累加停止时达到的区段,也是中位数所在的区段)的数值范围,设为[a,a+15],同时记录累加到前一个区段的总数,设为m。然后,释放除这个区段占用的内存。

3. 再读一遍10G个整数,把在[a,a+15]内的每个值计数,即有16个计数。

4. 对新的计数依次累加,每次的和设为n,当m+n的值超过5G时停止,此时的这个计数所对应的数就是中位数。

总结:
1.以上方法只要读两遍整数,对每个整数也只是常数时间的操作,总体来说是线性时间。

2. 考虑其他情况。
若是有符号的整数,只需改变 映射即可。若是64为整数,则增加每个区段的范围,那么在第二次读数时,要考虑更多的计数。若过某个计数溢出,那么可认定所在的区段或代表整数为所求,这 里只需做好相应的处理。噢,忘了还要找第5G+1大的数了,相信有了以上的成果,找到这个数也不难了吧。

3. 时空权衡。
花费256个区段也许只是恰好配合2GB的内存(其实也不是,呵呵)。可以增大区段范围,减少区段数目,节省一些内存,虽然增加第二部分的对单个数值的计数,但第一部分对每个区段的计数加快了(总体改变??待测)。

4. 映射时尽量用位操作,由于每个区段的起点都是2的整数幂,映射起来也很方便。

答案:

1, 把整数分成256M段,每段可以用64位整数保存该段数据个数,256M*8 = 2G内存,先清0 

2,读10G整数,把整数映射到256M段中,增加相应段的记数 

3,扫描256M段的记数,找到中位数的段和中位数的段前面所有段的记数,可以把其他段的内存释放 

4,因中位数段的可能整数取值已经比较小(如果是32bit整数,当然如果是64bit整数的话,可以再次分段),对每个整数做一个记数,再读一次10G整数,只读取中位数段对应的整数,并设置记数。 

5,对新的记数扫描一次,即可找到中位数。 

如果是32bit整数,读10G整数2次,扫描256M记数一次,后一次记数因数量很小,可以忽略不记
(设是32bit整数,按无符号整数处理 
整数分成256M段? 整数范围是0 - 2^32 - 1 一共有4G种取值,4G/256M = 16,每16个数算一段 0-15是1段,16-31是一段,... 
整数映射到256M段中? 如果整数是0-15,则增加第一段记数,如果整数是16-31,则增加第二段记数,... 
其实可以不用分256M段,可以分的段数少一写,这样在扫描记数段时会快一些,还能节省一些内存)

 

 

分段计数,先找出中位数所在的数据区域,然后集中查找。具体算法如下:

 

1.整数int型,按照32位计算机来说,占4Byte,可以表示4G个不同的值。原始数据总共有10G个数,需要8Byte才能保证能够完全计数。而内存是2G,所以共分成2G/8Byte=250M个不同的组,每组统计4G/250M=16个相邻数的个数。也就是构造一个双字数组(即每一个元素占8Byte)统计计数,数组包含250M个元素,总共占空间8Byte*250M=2G,恰好等于内存2G,即可以全部读入内存。第一个元素统计0-15区间中的数字出现的总个数,第二个元素统计16-31区间中的数字出现的总个数,最后一个元素统计(4G-16)到(4G-1)区间中的数字出现的总个数,这样遍历一遍10G的原始数据,得到这个数组值。

 

2.定义一个变量sum,初始化为0。从数组第一个元素开始遍历,并把元素值加入到sum。如果加入某个元素的值之前,sum<5G;而加入这个元素的值之后,sum>5G,则说明中位数位于这个元素所对应统计的16个相邻的数之中,并记录下加入这个元素的值之前的sum值(此时sum是小于5G的最大值)。如果这个元素是数组中第m个元素(m从0开始计算),则对应的这个区间就是[16m,16m+15]。

 

3.再次定义一个双字数组统计计数,数组包含16个元素,分别统计(16m)到(16m+15)区间中的每一个数字出现的个数,其他数字忽略。这样再次遍历一遍10G的原始数据,得到这个数组值。

 

4.定义一个变量sum2,sum2的初始值是sum(即上述第二步中记录的小于5G的最大值)。从新数组第一个元素开始遍历,并把元素值加入到sum2。如果加入某个元素的值之前,sum2<5G;而加入这个元素的值之后,sum2>5G,则说明中位数就是这个元素所对应的数字。如果这个元素是新数组中的第n个元素(n从0开始计算),则对应的数字就是16m+n,这就是这10G个数字中的中位数。

 

算法过程如上,需要遍历2遍原始数据,即O(2N),还需要遍历前后2个数组,O(k).总时间复杂度O(2N+k)

 

 

 

题目如下:
只有2G内存的pc机,在一个存有10G个整数的文件,从中找到中位数,写一个算法。
 
算法:
1.利用外排序的方法,进行排序 ,然后再去找中位数
 
2.另外还有个思路利用堆
先求第1G大,然后利用该元素求第2G大,然后利用第2G大,求第3G大...当然这样的话虽不需排序,但是磁盘操作会比较多,具体还需要分析下与外排序的效率哪个的磁盘IO会比较多
建立一个1g个整数的最大值堆,如果元素小于最大值则入堆,这样可以得到第1g大的那个元素然后利用这个元素,重新建一次堆,这次入堆的条件还要加上大于这个第1g大的元素,这样建完堆可以得到第2g大的那个 ...
 
3.借鉴基数排序思想
偶认为可以用位来判断计数,从最高位到最低位,为了方便表述我们假设为无符号整数,即0x00000000~0xFFFFFFFF依次递增,那么可以遍历所有数据,并记录最高位为0和1的个数(最高位为0的肯定是小于最高位为1的)记为N0、N1
那么根据N0和N1的大小就可以知道中位数的最高位是0还是1
假设N0>N1,那么再计算N00和N01,
如果N00>(N01+N1),则说明中位数的最高两位是00
再计算N000和N001.。。。依次计算就能找到中位数
 
如果改进一下,设定多个计数器
好像一次磁盘io也可以统计出N0,N00,....的数值
 
4.借鉴桶排序思想
一个整数假设是32位无符号数
第一次扫描把0~2^32-1分成2^16个区间,记录每个区间的整数数目
找出中位数具体所在区间65536*i~65536*(i+1)-1
第二次扫描则可找出具体中位数数值

第一次扫描已经找出中位数具体所在区间65536*i~65536*(i+1)-1
然后第二次扫描再统计在该区间内每个数出现的次数,就可以了


本文》有 0 条评论

留下一个回复