歡迎光臨
每天分享高質量文章

如何只用 2GB 記憶體從 20/40/80 億個整數中找到出現次數最多的數

(給演演算法愛好者加星標,修煉程式設計內功

作者:苦逼的碼農

20億級別

面試官:如果我給你 2GB 的記憶體,並且給你 20 億個 int 型整數,讓你來找出次數出現最多的數,你會怎麼做?

小秋:(嗯?怎麼感覺和之前的那道判斷一個數是否出現在這 40 億個整數中有點一樣?可是,如果還是採用 bitmap 演演算法的話,好像無法統計一個數出現的次數,只能判斷一個數是否存在),我可以採用雜湊表來統計,把這個數作為 key,把這個數出現的次數作為 value,之後我再遍歷雜湊表哪個數出現最多的次數最多就可以了。

面試官:你可以算下你這個方法需要花費多少記憶體嗎?

小秋:key 和 value 都是 int 型整數,一個 int 型佔用 4B 的記憶體,所以雜湊表的一條記錄需要佔用 8B,最壞的情況下,這 20 億個數都是不同的數,大概會佔用 16GB 的記憶體。

面試官:你的分析是對的,然而我給你的只有 2GB 記憶體。

小秋:(感覺這道題有點相似,不過不知為啥,沒啥思路,這下涼涼),目前沒有更好的方法。

面試官:按照你那個方法的話,最多隻能記錄大概 2 億多條不同的記錄,2 億多條不同的記錄,大概是 1.6GB 的記憶體。

小秋:(嗯?面試官說這話是在提示我?)我有點思路了,我可以把這 20 億個數存放在不同的檔案,然後再來篩選。

面試題:可以具體說說嗎?

小秋:剛才你說,我的那個方法,最多隻能記錄大概 2 億多條的不同記錄,那麼我可以把這 20 億個數對映到不同的檔案中去,例如,數值在 0 至 2億之間的存放在檔案1中,數值在2億至4億之間的存放在檔案2中….,由於 int 型整數大概有 42 億個不同的數,所以我可以把他們對映到 21 個檔案中去,如圖

顯然,相同的數一定會在同一個檔案中,我們這個時候就可以用我的那個方法,統計每個檔案中出現次數最多的數,然後再從這些數中再次選出最多的數,就可以了。

面試官:嗯,這個方法確實不錯,不過,如果我給的這 20 億個數數值比較集中的話,例如都處於 1~20000000 之間,那麼你都會把他們全部對映到同一個檔案中,你有最佳化思路嗎?

小秋:那我可以先把每個數先做雜湊函式對映,根據雜湊函式得到的雜湊值,再把他們存放到對應的檔案中,如果雜湊函式設計到好的話,那麼這些數就會分佈的比較平均。(關於雜湊函式的設計,我就不說了,我這隻是提供一種思路)

40億級別

面試官:那如果我把 20 億個數加到 40 億個數呢?

小秋:(這還不簡單,對映到42個檔案唄)那我可以加大檔案的數量啊。

面試官:那如果我給的這 40 億個數中數值都是一樣的,那麼你的雜湊表中,某個 key 的 value 存放的數值就會是 40 億,然而 int 的最大數值是 21 億左右,那麼就會出現上限溢位,你該怎麼辦?

小秋:(那我把 int 改為 long 不就得了,雖然會佔用更多的記憶體,那我可以把檔案分多幾份唄,不過,這應該不是面試官想要的答案),我可以把 value 初始值賦值為 負21億,這樣,如果 value 的數值是 21 億的話,就代表某個 key 出現了 42 億次了。

80億級別

面試官:反應挺快哈,那我如果把 40 億增加到 80 億呢?

小秋:(我靠,這變本加厲啊)………我知道了,我可以一邊遍歷一遍判斷啊,如果我在統計的過程中,發現某個 key 出現的次數超過了 40 億次,那麼,就不可能再有另外一個 key 出現的次數比它多了,那我直接把這個 key 傳回就搞定了。

面試官:行,此次面試到此結束,回去等通知吧。

總結

今天這篇文章主要講了大資料處理相關的一些問題,後面可能還會給大家找一些類似,但處理方式不同的題勒,當然,閱讀量很差的話,就會沒動力寫了,所以,如果覺得不錯,或許可以轉發一波,,,閱讀量一好,熬夜也要擼,嘿嘿。對了,後面的那些拓展問題是我自己想的,我也不知道我對應的思路是否是最優解,大家有更好思路的可以底部留言提供哈。

 

【本文作者】

苦逼的碼農:一個熱愛程式設計的在校生,我的世界不只有coding,還有writing。目前維護訂閱號「苦逼的碼農」,專註於寫「演演算法與資料結構」,「Java」,「計算機網路」。

贊(0)

分享創造快樂