如何解決處理大數據的時候的內存不足?

01-30

比如現在手上有70億＋1份身高數據，如何用有限的4GB內存找到這些數據中的中間值（也就是從小到大排列的第35億個人的身高）
粗略計算了一下，4GB／sizeof(double)約等於5億，也就是說無法把這70億份數據同時放入內存中進行處理。

求可行的方案（內存可以反覆擦寫）

如果僅僅只有單獨的身高數據沒有對應的其他信息，那很明顯數據的個數遠遠超過數據的取值範圍。話說身高需要用double么？用int16都綽綽有餘了啊，量身高的設備有那麼高精度么？

所以用一個數組記錄每個身高的個數即可。完成後從數組第一個元素開始累加看到什麼時候超過35億就知道中位數在哪裡了

也許思路和程序員不一樣，既然70億的數據已經隨機分布了，那麼你就拿出5億的數據出來統計，結果也不會差到哪去，至少足夠給CCTV交差了

偽代碼：

創建一個長度為 3000 的 64位整數的統計數組 count，並將數據初始化為0；

依次遍歷身高h(float 0.2f )，將數據單位轉換為毫米 H( int )，然後將數據中對應的整數值加一

( count[H]++ )，直到遍歷完文件。

遍歷 count數組，依次累加數組中的值，當值大於或等於35億時，這時數組的下表就是需要查詢的結果。

身高為啥要用double，unsigned short足矣……

你這個例子方法很多，拋磚引玉下。

不妨設所有身高範圍是0～2000mm。開一個長度為2001的數組，對，計數一下。然後找中間的就是一個循環的事。

要記住人的體力，能力是有限的，任何數據都不可能無限精確存儲，即使高大上的谷歌，其詞庫也就千萬級別，淘寶上一年出現的商品價格也就百萬級別，甚至於我們去統計百度所有用戶的查詢次數，拿這個次數去排序，對於每個人來說同樣也只具有有限的查詢次數，以上所有的例子，現在的手機內存都能裝得下，更別說伺服器了。

再說一句，這種爛大街的所謂大數據排序問題能不能少出點來噁心人了。

當年面試百度的時候，哥就是這樣反問的，你們的詞庫數量增長能跟得上現在內存性價比增長的速度嗎？

磁碟沒要求的話，桶排序，然後直接找第35億個記錄。

桶排序就是文件分份然後每一份快排，排完了堆排。

全排到一個文件里之後，讀一個數個數，數到中間就輸出。

其實已經有的答案里開數組數數是線性時間最優的。

如果70億數據沒有排序那麼需要先排序，4g內存夠了。只是時間問題。

然後直接取第35億個數據不就行了。

排序中堆的歸併演算法就是為了降低內存佔用的。

首先，我覺得這個不是大數據的範疇。

對於大量的數據處理，如果使用內存有限制（一般在面試題中有更好的表述方式），應該採用的方式有一下幾種：

以上6條內容，全部抄襲。未得到任何授權，有質疑，立刻刪除。

虛擬內存開大點，讓它自己跑去

PS：用歸併哦