海量数据找中位数

xiaozhu2007

在一个文件中有 10G 个整数，乱序排列，要求找出中位数。内存限制为 2G。只写出思路即可。

下面说说我的思路,欢迎拍转:
假设每个整数用一个bit表示,10G个整数就需要10G个bit=10G/8=1.25G个字节 < 2G的内存限制.
所以在内存中定义一个1.25G的大数组,定义一个整数n = 0;
然后从文件中读入整数,每读入一个整数就把大数组中相应bit位置为1,同时n+1(如果相应bit已经置为1了,n就不用加1)
这样所有的整数读完以后,n就是大数组中bit为1的个数,也就是10G数字中去重的数字个数.
然后遍历大数组,第n/2个bit为1的数就是要求的中位数.

欢迎多给点建议,谢谢!


ps:如何有效给大数组的某个bit位置1???

[ 本帖最后由 xiaozhu2007 于 2008-9-22 13:17 编辑 ]

wilbur512

没有说整数范围是0到10*2^30吧..

wilbur512

中位数是什么意思

2,2,100的中位数是 (2+2+100)/3还是  (2+100)/2 ?

xiaozhu2007

原帖由 wilbur512 于 2008-9-21 19:59 发表
中位数是什么意思

2,2,100的中位数是 (2+2+100)/3还是  (2+100)/2 ?

这个问题不是关键,不重要.

xiaozhu2007

原帖由 wilbur512 于 2008-9-21 19:57 发表
没有说整数范围是0到10*2^30吧..

???没明白你的意思.
我没有考虑整数是负数的情况.

wilbur512

unsigned int 的范围是 0-4G
4G个bit就可以了吧

wilbur512

如何有效给大数组的某个bit位置1


char*  array =  (char*)malloc(512*1024*1024);

数字为m的话

*(array+m/8-1) | = 0x1<<(m%;

乱写的 .

cugb_cat

原帖由 wilbur512 于 2008-9-21 19:59 发表
中位数是什么意思

2,2,100的中位数是 (2+2+100)/3还是  (2+100)/2 ?

排序后中间的那个数。。

xiaozhu2007

原帖由 wilbur512 于 2008-9-21 20:54 发表
unsigned int 的范围是 0-4G
4G个bit就可以了吧

对对对，不用10G个bit，我没想清楚！

xiaozhu2007

原帖由 wilbur512 于 2008-9-21 21:06 发表
如何有效给大数组的某个bit位置1


char*  array =  (char*)malloc(512*1024*1024);

数字为m的话

*(array+m/8-1) | = 0x1

这样不对吧...