问题描述
Given a packed file with 1Tb of 64-bit doubles (first 8 bytes are first double, next 8 bytes are next, etc), find the exact value of median. For simplicity assume the number of doubles is odd. You cannot modify the file and you have only 8Gb of free memory. You may use no more than 2 passes through file and your algorithm should work in all cases.
给1Tb的64比特double类型数据，每一个占8字节。在限制8GB内存，不多于2遍遍历文件的条件下，求准确的中位数。假设有奇数个double。
询问补充
无
思路分析
这属于大数据问题。
首先是做一些基本的计算。
1T=1024G=2^40B，因为1个Double有8B，因此总共是2^37个Double数据。
假如没有限制
这类带限制的问题的一个套路就是，先思考没有限制的解法。
就和普通算法题思考暴力破解方法类似。当然不能花太多时间。
最直白的就是排序，然后选中间那个就是中位数了。当然在这里不太现实，因为要容下所有Double的话，需要1T内存。
另一个常见的求中位数的方法也需要大量内存，就是维持min heap和max heap，把数据分成两份，中位数就在堆顶。不过这个方法同样对内存没有优化。
不用内存的方法：每次只处理1位，知道中位数在哪里，然后继续，直至找到。例如第一次计数最高位为0的和为1的，然后知道中位数在哪一堆，之后重复即可。缺点是需要遍历足足64次。
优化一点内存的方法：8B=64bit，直接二分，也就是用高32位作为桶的标签来做桶。那么就有2^32个桶。然后就可以找到中位数在哪个桶，之后继续重复以低32位作为桶的标签再来。因为每个桶最多有2^37个Double，也就是说每个桶需要37位来表示这个桶里面有多少Double，第一次分32位，也就是说需要37*2^32bit的内存，约20Gb。这种方法2次遍历，符合题目条件。
有限制
因为只有8G内存，而上面提到的优化内存之后的方法仍旧需要20G，因此还得再继续考虑优化。
解法
这个思路点破了也就没什么了，就是取模的意思。当然还是比较巧妙的。
首先对半分桶的思路是没有问题的。大部分大数据问题都有类似的思路。而很明显第一次遍历的时候内存压力是最大的，因此只要能cover第一次，后面的都没有问题。
因为有2^32个桶，那么造2^32的字节数组，也就是说每个容量是1byte，那么需要4GB。
此外，创造一个32bit的整型数组。
对于字节数组，因为1byte=8bit，2^8=256，也就是说只能计数255次，当超过次数的时候即溢出，从0开始，那么最多可以溢出2^37/2^8=2^29次，每次溢出时把对应的前缀加入到整型数组当中，也就是最多有2^29*32/8=2GB。
当第一遍遍历结束时，因为每次溢出都会把前缀加入到整型数组，因此可以对整型数组从小到大排序，前缀出现的次数也就代表着溢出次数，一个前缀实际存在的次数就是桶里面剩余的次数+整型数组里面出现的次数x256。这样就做到了对前缀的计数。
之后找到中位数所在的前缀之后，再对低32位进行一次即可。
该方法仅仅使用了6G内存，还有2G剩余。
总结
非常典型的Big Data问题，很有代表性。难度：medium~hard。
网友评论