当前位置:首页 > 模式算法 > 正文内容

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

phpmianshi7年前 (2015-04-14)模式算法480

题目:在一个文件中有 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
然后第二次扫描再统计在该区间内每个数出现的次数,就可以了


版权声明:本文由PHP面试资料网发布,如需转载请注明出处。
分享给朋友:

相关文章

php中的桥接模式

概念桥接模式 (Bridge Pattern):将抽象与实现解耦,使得两者可以独立的变化1,如果一个系统需要在构件的抽象化角色和具体化角色之间增加更多的灵活性,避免在两个层次之间建立静态的继承联系,通...

php中责任链模式

概念又叫职责链模式。包含了一些命令对象和一些处理对象,每个处理对象决定它能处理那些命令对象,它也知道应该把自己不能处理的命令对象交下一个处理对象,该模式还描述了往该链添加新的处理对象的方法。示例情景一...

适配器模式与装饰器模式的区别

概念适配器与装饰器模式的别名都是包装模式(Wrapper)。区别适配器模式的意义将一个接口转变成另一个接口,目的是通过改变接口来达到重复使用的目的。装饰器模式的意义不改变被装饰对象的接口,而是保持原有...

在Laravel中正确地应用 Repository设计模式

在Laravel中正确地应用 Repository设计模式

概念在本文中,我会向你展示如何在 Laravel 中从头开始实现 repository 设计模式。repository 设计模式允许你使用对象,而不需要了解这些对象是如何持久化的。本质上,它是数据层的...

Laravel神奇的IoC容器

Laravel 的核心就是一个 IoC 容器,根据文档,称其为“服务容器”通过举例来让读者去理解什么是 IoC(控制反转) 和 DI(依赖注入)超人和超能力,依...

php中的状态模式

概念状态模式当一个对象的内在状态改变时允许改变其行为,这个对象看起来像是改变了其类。状态模式主要解决的是当控制一个对象状态的条件表达式过于复杂时的情况。把状态的判断逻辑转移到表示不同状态的一系列类中,...

发表评论

访客

◎欢迎参与讨论,请在这里发表您的看法、交流您的观点。