C++-海量数据找中位数

Question

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

Answer 1

多线程

分段排序

迭代

Answer 2

一种可行的方法是使用堆排序。
假设数总数目是N，依据现有内存能够构建的堆容纳的元素的数目是M。
扫描所有数据一次，构建出一个包含N个数中最小的M 个数的堆，时间复杂度O(NlgM)。然后记录下其中最大的书heapMaxVal。接下来将堆清空，再次扫描所有的数据一次，构建出包含大于heapMaxVal的最小的M个数。然后将heapMaxVal更新为堆中的最大的数，然后重复之前的操作直到累计构造堆所表示的数的数量大于N/2,。然后在当前堆中即可找出中位数。构造的次数为N/(2 * M);

只不过时间复杂度比较高：O(NNlgM)*N/(2 * M)。

期待大神给出牛掰的解答~

Answer 3

1，10G个int，总量已经大于内存限制，所以这些数据肯定要在持久层面解决问题
2，我的想法的是把数据读入到数据库里，如果数据库调校的好的话，这个操作应该不会太费劲。毕竟距离T级，还很遥远。

Answer 4

可不可以这样
我将这些数据分成4KB大小一个块，共10GB/4KB个块。然后按快速排序求出各块的中位数。将这些中位数存储在一个文件中。如果该文件还是比较大，那就再按上述思想分块取中位数...以此方法找出10GB数据中的中位数。

Answer 5

分段计数，先找出中位数所在的数据区域，然后集中查找。具体算法如下：

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)

Answer 6

任意选取一个数 将这些数据分成 2部分
这2部分存放在 文件中

然后中位数 肯定在 数据多的那一部分中

然后在数据多的那个文件中 做同样的处理
直到找到中位数