幾道和「黑洞照片」那種海量數(shù)據(jù)有關(guān)的算法問題

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

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

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

心里不禁納悶：為什么給黑洞拍照需要這么長時間？

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

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

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

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

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

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

題目描述

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

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

題目解析

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

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

桶排序

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

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

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

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

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

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

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

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

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

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

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

題目描述

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

題目分析

這里可以使用 布隆過濾器 進行處理。

布隆過濾器（英語：Bloom Filter）是 1970 年由 Burton Bloom 提出的。

它實際上是一個很長的二進制矢量和一系列隨機映射函數(shù)。


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

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

一開始，布隆過濾器的位數(shù)組所有位都初始化為 0。比如，數(shù)組長度為 m ，那么將長度為 m 個位數(shù)組的所有的位都初始化為 0。