【腾讯】10G整数文件中寻找中位数

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

 

 

分析： 既然要找中位数，很简单就是排序的想法。那么基于字节的桶排序是一个可行的方法 （请见《桶排序 》）：

思想：将整形的每1byte作为一个关键字，也就是说一个整形可以拆成4个keys，而且最高位的keys越大，整数越大。如果高位keys相同，则比较次高位的keys。整个比较过程类似于字符串的字典序。

第一步:把10G整数每2G读入一次内存，然后一次遍历这536,870,912个数据。每个数据用位运算">>"取出最高8位(31-24)。这8bits(0-255)最多表示255个桶，那么可以根据8bit的值来确定丢入第几个桶。最后把每个桶写入一个磁盘文件中，同时在内存中统计每个桶内数据的数量，自然这个数量只需要255个整形空间即可。

代价：(1) 10G数据依次读入内存的IO代价(这个是无法避免的，CPU不能直接在磁盘上运算)。(2)在内存中遍历536,870,912个数据，这是一个O(n)的线性时间复杂度。(3)把255个桶写会到255个磁盘文件空间中，这个代价是额外的，也就是多付出一倍的10G数据转移的时间。

第二步：根据内存中255个桶内的数量，计算中位数在第几个桶中。很显然，2,684,354,560个数中位数是第1,342,177,280个。假设前127个桶的数据量相加，发现少于1,342,177,280，把第128个桶数据量加上，大于1,342,177,280。说明，中位数必在磁盘的第128个桶中。而且在这个桶的第1,342,177,280-N(0-127)个数位上。N(0-127)表示前127个桶的数据量之和。然后把第128个文件中的整数读入内存。(平均而言，每个文件的大小估计在10G/128=80M左右，当然也不一定，但是超过2G的可能性很小)。

代价：(1)循环计算255个桶中的数据量累加，需要O(M)的代价，其中m<255。(2)读入一个大概80M左右文件大小的IO代价。

注意，变态的情况下，这个需要读入的第128号文件仍然大于2G，那么整个读入仍然可以按照第一步分批来进行读取。

第三步：继续以内存中的整数的次高8bit进行桶排序(23-16)。过程和第一步相同，也是255个桶。

第四步：一直下去，直到最低字节(7-0bit)的桶排序结束。我相信这个时候完全可以在内存中使用一次快排就可以了。

 

 

整个过程的时间复杂度在O(n)的线性级别上(没有任何循环嵌套)。但主要时间消耗在第一步的第二次内存-磁盘数据交换上，即10G数据分255个文件写回磁盘上。一般而言，如果第二步过后，内存可以容纳下存在中位数的某一个文件的话，直接快排就可以了。关于快排的效率，可以看看我博客中的数据《基于比较的内部排序总结 》。

评论

8 楼 荆棘鸟崽崽 2012-09-07  

blackdog1987 写道

bingjing12345 写道

futrueboy 写道

这题我怎么觉得用位图就可以做的

位图做不了
整数总范围是2^32，占4g内存，如果是正整数的话，应该可以。

位图是可以做的
2^32  =  4g
考虑二分法

读入所有的整数（当然分批次，这种细节我就不再说了）
所有整数转换为2进制  有   0 XXXX     1 XXXX
将0开头的输出到文件A，1开头的输出到文件B
用一个变量n记录0开头的数据个数

1、n>4G/2  则表示较小的数据更多，中位数未于A文件中。A文件读入，采用位图法（已经去掉第一位了，内存只需要2G了），从而找到所有数的详细情况。然后减去B中的数量的个数（从大到小减，保证最大的X个数和最小的X个数成对）剩下的再来找，简单了吧
2、n<4g/2  同上，不赘述
3、n==4g/2  这是最简单的情况了，说明大数，小数的数量均匀分布在两边，从A文件中找出最大的一个数（及其个数），从B文件中，找出最小的一个数，两个数，谁多，中位数就是谁，如果一样多，那么中位数就是两个

你这解法完全不对。。。n>4G/2,是错的，应该是n>5G，A文件只需2G是错的，你2G全用来做位图（只能记录0/1，只有1bit.）失去了个数的统计。相互抵消怎么处理？
你的思路其实和楼主差不多，你10G的文件分成两份显然还是处理不了的，分成255分则好些，实在不行分成1024份，单个文件的大小就难超过2G了。

7 楼 blackdog1987 2012-08-16  

bingjing12345 写道

futrueboy 写道

这题我怎么觉得用位图就可以做的

位图做不了
整数总范围是2^32，占4g内存，如果是正整数的话，应该可以。

位图是可以做的
2^32  =  4g
考虑二分法

读入所有的整数（当然分批次，这种细节我就不再说了）
所有整数转换为2进制  有   0 XXXX     1 XXXX
将0开头的输出到文件A，1开头的输出到文件B
用一个变量n记录0开头的数据个数

1、n>4G/2  则表示较小的数据更多，中位数未于A文件中。A文件读入，采用位图法（已经去掉第一位了，内存只需要2G了），从而找到所有数的详细情况。然后减去B中的数量的个数（从大到小减，保证最大的X个数和最小的X个数成对）剩下的再来找，简单了吧
2、n<4g/2  同上，不赘述
3、n==4g/2  这是最简单的情况了，说明大数，小数的数量均匀分布在两边，从A文件中找出最大的一个数（及其个数），从B文件中，找出最小的一个数，两个数，谁多，中位数就是谁，如果一样多，那么中位数就是两个

6 楼 bingjing12345 2012-08-04  

首先， 你没有审对题。 题目是10G个  int型数， 你做的是10G整数。
其次，即使你做的是对的，也应该选16bit。
再次，这些数据没说是均匀分布的，用桶排序时，桶的大小不确定。有链式存储，影响效率。并且你没有考虑桶排序的空间复杂度，将2G数据读到内存后，内存已经用完了，辅助空间没地方分了。

5 楼 bingjing12345 2012-08-04  

futrueboy 写道

这题我怎么觉得用位图就可以做的

位图做不了
整数总范围是2^32，占4g内存，如果是正整数的话，应该可以。

4 楼 explore 2012-05-29  

两个地方比较困惑：1，为什么8bits（-128到127）最多只能表示255个桶，不是256？2.10G/128=80M 是怎么得出来的哪

3 楼 futrueboy 2011-10-12  

这题我怎么觉得用位图就可以做的

2 楼 liuxinglanyue 2010-12-23  

(平均而言，每个文件的大小估计在10G/128=80M左右，当然也不一定，但是超过2G的可能性很小)

一开始以为是除以255，原来作者用的是概率来做的呀。
学习了。

1 楼 frankwan 2010-04-27  

排序算法与查找算法都写的很好，比教科书容易理解多了