大数据查找中位数

淩亂°似流年 2022-10-09 06:26 91阅读 0赞

需要遍历所有数据

## 2. 基本知识 ##

*  b --> bit 比特，位（二进制中的位）
 *  B --> Byte 字节，1个字节=8位，1B=8bit
 *  K --> KB 千字节，1KB = 1024B
 *  M --> MB 兆字节，1M = 1024KB = 1024\*1024B
 *  G --> GB 1GB = 1024MB、

问题分析：

**100亿个32位整数，那么占用内存为：**

*  100亿\*32 b = 100亿\*32/8 B = 100亿\*32/8/1024 KB = 100亿\*32/8/1024/1024 MB = 38146.9727 MB > 512M
 *  所以肯定不能一次全部载入内存。

**那么512M可以装多少个32位整数呢？**

*  512M=512\*1024K=512\*1024\*1024B=512\*1024\*1024\*8b=4294967296b
 *  可存储32位整数：4294967296b/32b=134217728个，是1亿多个。

## 3. 设计思路 ##

（1）我们要划分映射区域，一个有符号的32位整数的取值范围是\[-2^31, 2^31-1\]，总共有4294967296个取值，因此我们将它划分成100000组，即43000个数映射到一个组，将a1的区间\[-2^31，-2^31+43000)，a2的区间\[-2^31+43000，-2^31+86000)......一直到a100000的区间；（这是组数与项数的一个平衡问题）；

（2.1）我们首先装载第一个1亿个数，遍历这些数，比较大小，看他落入a1至a100000的哪个区间，落入的对应区间统计计数增1；这次是对这里面的数区间的组映射；

（2.2）重复步骤（2.1），装载100次，这样我们就得到了a1至a100000的区间统计计数的取值；

（2.3）内存分析：1亿个数用来装载，100000个区间统计计数耗费400000个字节，足够使用；剩余内存（128M-1亿-100000）\*4B;

（3.1）使用sum依次累加a1至a100000的区间统计计数，直到累加某区间ai后sum大于50亿了；那么第50亿个数就在该区间中，用sum减去该区间ai的统计数的到first；即前面的区间统计总数位置为第first个（其中first < 50亿）;

（3.2）那么我就在ai区间找到第50亿-first个数，或第50亿-first+1个数（第50亿-first+1个数这个数可能在ai后面的区间，但是概率很小，但是找到的原理类似）；

（3.3）内存分析：每一个区间分割比较要花费100000个区间比较数，耗费400000个字节，足够使用；剩余内存（128M-1亿-100000-100000-2）\*4B;

（4.1）再次遍历这100亿个数，还是每组1亿个数，一共100组；对于若在ai区间的43000个数的每一个都开一个统计计数器 ，跟上面类似，这次是对这里面的数单个映射；

（4.2）同样使用sum依次累加这1至43000的的统计计数，直到累加某区间后sum大于50亿-first；那么我们可以得到第（50亿-first）个数就在对应的位置；而且第（50亿-first+1）个数位置也有可能在，或在下一个统计计数大于0的位置；当然也有可能不在ai区间；（但原理类似）；

（4.3）得到了第（50亿-first）个数值；而且第（50亿-first+1）个数值，可算出中位数了；

（4.4）内存分析：上述的100000个比较数，此时我们只需要两个比较数；100000个区间统计计数全部释放掉，但增加了43000位置统计计数；剩余内存（128M-1亿-43000-2-2）\*4B；还是足够使用的；

（5）总共遍历两遍100亿数据；

## 4. 总结 ##