問題描述
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類型數(shù)據(jù)永毅，每一個占8字節(jié)蜕窿。在限制8GB內(nèi)存魏宽，不多于2遍遍歷文件的條件下萨螺，求準確的中位數(shù)。假設(shè)有奇數(shù)個double吃衅。
詢問補充
無
思路分析
這屬于大數(shù)據(jù)問題往踢。
首先是做一些基本的計算。
1T=1024G=2^40B徘层，因為1個Double有8B峻呕，因此總共是2^37個Double數(shù)據(jù)。
假如沒有限制
這類帶限制的問題的一個套路就是惑灵，先思考沒有限制的解法山上。
就和普通算法題思考暴力破解方法類似。當(dāng)然不能花太多時間英支。
最直白的就是排序佩憾，然后選中間那個就是中位數(shù)了。當(dāng)然在這里不太現(xiàn)實，因為要容下所有Double的話妄帘，需要1T內(nèi)存楞黄。
另一個常見的求中位數(shù)的方法也需要大量內(nèi)存，就是維持min heap和max heap抡驼，把數(shù)據(jù)分成兩份鬼廓，中位數(shù)就在堆頂。不過這個方法同樣對內(nèi)存沒有優(yōu)化致盟。
不用內(nèi)存的方法：每次只處理1位碎税，知道中位數(shù)在哪里，然后繼續(xù)馏锡，直至找到雷蹂。例如第一次計數(shù)最高位為0的和為1的，然后知道中位數(shù)在哪一堆杯道，之后重復(fù)即可匪煌。缺點是需要遍歷足足64次。
優(yōu)化一點內(nèi)存的方法：8B=64bit党巾，直接二分萎庭，也就是用高32位作為桶的標簽來做桶。那么就有2^32個桶齿拂。然后就可以找到中位數(shù)在哪個桶驳规，之后繼續(xù)重復(fù)以低32位作為桶的標簽再來。因為每個桶最多有2^37個Double署海，也就是說每個桶需要37位來表示這個桶里面有多少Double达舒，第一次分32位，也就是說需要37*2^32bit的內(nèi)存叹侄，約20Gb。這種方法2次遍歷昨登，符合題目條件趾代。
有限制
因為只有8G內(nèi)存，而上面提到的優(yōu)化內(nèi)存之后的方法仍舊需要20G丰辣，因此還得再繼續(xù)考慮優(yōu)化撒强。
解法
這個思路點破了也就沒什么了，就是取模的意思笙什。當(dāng)然還是比較巧妙的飘哨。
首先對半分桶的思路是沒有問題的。大部分大數(shù)據(jù)問題都有類似的思路琐凭。而很明顯第一次遍歷的時候內(nèi)存壓力是最大的芽隆，因此只要能cover第一次，后面的都沒有問題。
因為有2^32個桶胚吁，那么造2^32的字節(jié)數(shù)組牙躺，也就是說每個容量是1byte，那么需要4GB腕扶。
此外孽拷，創(chuàng)造一個32bit的整型數(shù)組。
對于字節(jié)數(shù)組半抱，因為1byte=8bit脓恕，2^8=256，也就是說只能計數(shù)255次窿侈，當(dāng)超過次數(shù)的時候即溢出炼幔，從0開始，那么最多可以溢出2^37/2^8=2^29次棉磨，每次溢出時把對應(yīng)的前綴加入到整型數(shù)組當(dāng)中江掩，也就是最多有2^29*32/8=2GB。
當(dāng)?shù)谝槐楸闅v結(jié)束時乘瓤，因為每次溢出都會把前綴加入到整型數(shù)組环形，因此可以對整型數(shù)組從小到大排序，前綴出現(xiàn)的次數(shù)也就代表著溢出次數(shù)衙傀，一個前綴實際存在的次數(shù)就是桶里面剩余的次數(shù)+整型數(shù)組里面出現(xiàn)的次數(shù)x256抬吟。這樣就做到了對前綴的計數(shù)。
之后找到中位數(shù)所在的前綴之后统抬，再對低32位進行一次即可火本。
該方法僅僅使用了6G內(nèi)存，還有2G剩余聪建。
總結(jié)
非常典型的Big Data問題钙畔，很有代表性。難度：medium~hard金麸。
