昨晚被一則新聞刷屏：北京時(shí)間 4 月 10 日今晚 9 點(diǎn)，人類首張黑洞照片正式發(fā)布。

看到這張圖片，小吳心里是極為震撼的：愛(ài)因斯坦太太太太太牛逼了！！！

同時(shí)，看新聞的時(shí)候小吳還注意到里面有個(gè)細(xì)節(jié)，給黑洞”拍照“的事件視界望遠(yuǎn)鏡從 2017 年就開(kāi)始為黑洞拍照了，但直到 2019 年才公布。

心里不禁納悶：為什么給黑洞拍照需要這么長(zhǎng)時(shí)間？

于是去更加詳細(xì)的搜索資料，果然發(fā)現(xiàn)了端倪，其中一個(gè)點(diǎn)就是 望遠(yuǎn)鏡觀測(cè)到的數(shù)據(jù)量非常龐大 ！

2017 年時(shí) 8 個(gè)望遠(yuǎn)鏡的數(shù)據(jù)量達(dá)到了 10PB（=10240TB），2018 年又增加了格陵蘭島望遠(yuǎn)鏡，數(shù)據(jù)量繼續(xù)增加。龐大的數(shù)據(jù)量為處理讓數(shù)據(jù)處理的難度不斷加大。

平時(shí)面試的時(shí)候老是說(shuō)海量數(shù)據(jù)，海量數(shù)據(jù)，這次的數(shù)據(jù)真的是海量數(shù)據(jù)了。

這次的數(shù)據(jù)流之大，導(dǎo)致每個(gè)射電望遠(yuǎn)鏡產(chǎn)生的數(shù)據(jù)，都只能用硬盤(pán)來(lái)儲(chǔ)存。

那么現(xiàn)在問(wèn)題來(lái)了，假設(shè)你作為給黑洞拍照的研發(fā)人員，給你一臺(tái)內(nèi)存有限的計(jì)算機(jī)，你如何找出這些數(shù)據(jù)的中位數(shù)或者判斷某個(gè)數(shù)字是否存在里面。

1. 海量數(shù)據(jù)查找中位數(shù)

題目描述

現(xiàn)在有 10 億個(gè) int 型的數(shù)字（ java 中 int 型占 4B），以及一臺(tái)可用內(nèi)存為 1GB 的機(jī)器，如何找出這 10 億個(gè)數(shù)字的中位數(shù)？

所謂中位數(shù)就是有序列表中間的數(shù)。如果列表長(zhǎng)度是偶數(shù)，中位數(shù)則是中間兩個(gè)數(shù)的平均值。

題目解析

題目中有 10 億個(gè)數(shù)字，每個(gè)數(shù)字在內(nèi)存中占 4B，那么這 10 億個(gè)數(shù)字完全加載到內(nèi)存中需要：10 * 10^8 * 4，大概需要 4GB 的存儲(chǔ)空間。根據(jù)題目的限制，顯然不能把所有的數(shù)字都裝入內(nèi)存中。

這里，可以采用基于 二進(jìn)制位比較 和 快速排序算法中的 分割思想 來(lái)尋找中位數(shù)，實(shí)際上這也是 桶排序 的一種應(yīng)用。

桶排序

假設(shè)將這 10 億個(gè)數(shù)字保存在一個(gè)大文件中，依次讀一部分文件到內(nèi)存(不超過(guò)內(nèi)存的限制： 1GB )，將每個(gè)數(shù)字用二進(jìn)制表示，比較二進(jìn)制的最高位(第 32 位)，如果數(shù)字的最高位為 0，則將這個(gè)數(shù)字寫(xiě)入 file_0 文件中；如果最高位為 1，則將該數(shù)字寫(xiě)入 file_1 文件中。

注意：最高位為符號(hào)位，也就是說(shuō) file_1 中的數(shù)都是負(fù)數(shù)，而 file_0 中的數(shù)都是正數(shù)。

通過(guò)這樣的操作，這 10 億個(gè)數(shù)字分成了兩個(gè)文件，假設(shè) file_0 文件中有 6 億個(gè)數(shù)字，而 file_1 文件中有 4 億個(gè)數(shù)字。

這樣劃分后，思考一下：所求的中位數(shù)在哪個(gè)文件中？

10 億個(gè)數(shù)字的中位數(shù)是10 億個(gè)數(shù)排序之后的第 5 億個(gè)數(shù)，現(xiàn)在 file_0 有 6 億個(gè)正數(shù)，file_1 有 4 億個(gè)負(fù)數(shù)，file_0 中的數(shù)都比 file_1 中的數(shù)要大，排序之后的第 5 億個(gè)數(shù)一定是正數(shù)，那么排序之后的第 5 億個(gè)數(shù)一定位于file_0中。

也就是說(shuō)：中位數(shù)就在 file_0 文件中，并且是 file_0 文件中所有數(shù)字排序之后的第 1 億個(gè)數(shù)字。

現(xiàn)在，我們只需要處理 file_0 文件了（不需要再考慮 file_1 文件）。

而對(duì)于 file_0 文件，可以同樣的采取上面的措施處理：將 file_0 文件依次讀一部分到內(nèi)存(不超內(nèi)存限制：1GB )，將每個(gè)數(shù)字用二進(jìn)制表示，比較二進(jìn)制的 次高位（第 31 位），如果數(shù)字的次高位為 0，寫(xiě)入 file_0_0 文件中；如果次高位為 1 ，寫(xiě)入 file_0_1 文件中。

現(xiàn)假設(shè) file_0_0 文件中有 3 億個(gè)數(shù)字，file_0_1中也有 3 億個(gè)數(shù)字，則中位數(shù)就是：file_0_0 文件中的數(shù)字從小到大排序之后的第 1 億個(gè)數(shù)字。

拋棄 file_0_1 文件，繼續(xù)對(duì) file_0_0 文件 根據(jù)次次高位(第 30 位) 劃分，假設(shè)此次劃分的兩個(gè)文件為：file_0_0_0中有 0.5 億個(gè)數(shù)字，file_0_0_1 中有 2.5 億個(gè)數(shù)字，那么中位數(shù)就是 file_0_0_1 文件中的所有數(shù)字排序之后的第 0.5 億個(gè)數(shù)。

2. 海量數(shù)據(jù)中判斷數(shù)字是否存在

題目描述

現(xiàn)在有 10 億個(gè) int 型的數(shù)字（ java 中 int 型占 4B），以及一臺(tái)可用內(nèi)存為 1GB 的機(jī)器，給出一個(gè)整數(shù)，問(wèn)如果快速地判斷這個(gè)整數(shù)是否在這 10 億數(shù)字中？

題目分析

這里可以使用 布隆過(guò)濾器 進(jìn)行處理。

布隆過(guò)濾器（英語(yǔ)：Bloom Filter）是 1970 年由 Burton Bloom 提出的。

它實(shí)際上是一個(gè)很長(zhǎng)的二進(jìn)制矢量和一系列隨機(jī)映射函數(shù)。


它可以用來(lái)判斷一個(gè)元素是否在一個(gè)集合中。它的優(yōu)勢(shì)是只需要占用很小的內(nèi)存空間以及有著高效的查詢效率。

對(duì)于布隆過(guò)濾器而言，它的本質(zhì)是一個(gè)位數(shù)組：位數(shù)組就是數(shù)組的每個(gè)元素都只占用 1 bit ，并且每個(gè)元素只能是 0 或者 1。

一開(kāi)始，布隆過(guò)濾器的位數(shù)組所有位都初始化為 0。比如，數(shù)組長(zhǎng)度為 m ，那么將長(zhǎng)度為 m 個(gè)位數(shù)組的所有的位都初始化為 0。