Neo's Blog

不抽象就无法深入思考
不还原就看不到本来面目!

0%

常见系统设计题系列-大文件整数找中位数

在一个文件中有10G个整数,乱序排列,要求找出中位数。内存限制为2G。

回答:

不妨假设10G个整数是64bit的。2G内存可以存放256M个64bit整数。

我们可以将64bit的整数空间平均分成256M个取值范围,用2G的内存对每个取值范围内出现整数个数进行统计。这样遍历一边10G整数后,我们便知道中数在那个范围内出现,以及这个范围内总共出现了多少个整数。

如果中数所在范围出现的整数比较少,我们就可以对这个范围内的整数进行排序,找到中数。

如果这个范围内出现的整数比较多,我们还可以采用同样的方法将此范围再次分成多个更小的范围(256M=2^28,所以最多需要3次就可以将此范围缩小到1,也就找到了中数)。

注解:先按取值范围将数据保存到对应文件,并统计每个文件有多少数值,然后计算第5G和5G+1个数在哪个文件,继续对该文件重复上述步骤

你的支持是我坚持的最大动力!