挑戰程序員同學，如何只用2GB內存從20/40/80億個整數中找到出現次數最多的數？

沙茶敏碎碎念

64mb內存就夠。假設你的數據都存在文件中。

1，分治法，空間換時間，分片讀取hash到n個文件中

2，統計每個文件中出現次數最多的數字

3，堆排序，對比每個文件中出現次數最多的數字。

4，結束

wuyukun91

需求：

使用2G的內存，找出80億個數字中出現最多的數字。

假設：

1. 整數為4字節（2^32=4G），即最大40多億。
   
2. 所有的數字有80億個。
3. 所有數字在硬盤中，本身不會佔用內存。
   
4. 所用內存為2G多一些，例如有限的變量。但多出的內存和2G相比可以忽略不計。
   
   

設計：

1. 80億的計數可以用4字節保存（2^32=4G）。因為如果計數超過一半，則表明該數字一定是出現最多的。
   
2. 2G的內存約可以保存5億多數字的計數（2G/4=512M）。
   

也就是說，將2G的內存分成單位為4字節的數組，可以一次獲得0∼5億多之間出現最多的數字。

步驟：

1. 順序掃描80億個數字，忽略0∼512M之外的數字，每個數字N的出現個數累加存放在第N個數組元素中。最後將最出現最多的數字及其次數保存起來，出現並列第一時，只保存第一個數字。如果過程中某數字出現個數超過40億，則直接結束。
   
2. 再次掃描所有數字，此次忽略512M∼1G之外的數字。每個數字N的出現個數累加存放在第N-512M個數組元素中。本輪所獲得的數字的出現個數和第一輪結果比較，保存較大的那個。
   
   
3. 由於整數取值範圍為4G，所以最多掃描8次後即可獲得最終結果。
   

問題：

如果整數長度為8字節，則需要掃描約300多億次（2^64/512M=2^40）。所以此算法並不適用於8字節的整數。

討論：

當數字足夠多，且數字取值範圍足夠大時，以有限內存獲取出現次數最多的數字幾乎是不可能的。因為數字的取值範圍極大，且數字極多，任何哈希或其它分片的算法都有可能出現極端情況，導致分片數據過多而無法一次性導入內存計算。除非我們預先知道部分數字規律，否則考慮到效率，應該只會要求得到近似結果。

tutu_cloud

只有不是程序員才會出這樣的題，你要知道，3、8、55246546是整數，但12345的階乘，葛立恆數等也是整數，葛立恆數的葛立恆數次方也是整數，你沒有限定整數範圍，所以我覺得真正的程序員會先和你談需求。另，我就是程序員。

伴你去看海850

low一點的不考慮時間成本，直接按2G分批MapReduce。

Deathef

小問題。

有限集。

坑不多，一個是複雜度，一個是準確度。

解

將整個集劃分為000-XXX的子集，每個子集內統計000-YYY的數，形成列表，合併各表，

然後前ZZZ個數再全集統計一遍。

搞定。

巫師威武

一、用4字節表示的整數個數為2^32≈40億，而用2字節表示的無符號整數個數為2^16≈6萬。

二、2G=2^31B≈20億字節。

三、要找出出現次數最多的數，則應記錄每個數出現的次數，最快的方法是在內存中將每個數出現的次數記錄下來，記錄的方法則是內存地址對應數，相應地址的內存單元記錄次數，但2G內存以字節為單位僅能記錄20億個數，且每個數出現的次數大於255將會出現溢出風險。因此，這一方案不可取。

四、這樣只能將每個次出現的次數記錄在磁盤上。這樣在磁盤上建一個16G的文件，每4字節對應一個整數，可對應40億個整數，並用於記錄相應整數的出現的次數。

1、將文件初始化。

2、依次讀取數據，並用無符號整數記錄在磁盤文件中，如出現溢出，則該數為次數最多的數。

3、從文件中讀取各數出現的次數，用一個變量A記錄最高次數，再用一個變量B記錄最高次數出現的數據個數，要用個文件依次記錄最高次數出現的數。當最高次數增加時，A+1，B置1，文件中寫入該數，同次數的數出現時，B+1，文件相應位置寫入該數，直到全部讀完。

這樣根本不需2G內存。

新熱機發明者曾祥雲

2g內存不是重點，80億數字和取值範圍才是重要的：

1. 80億的數字至少需要加載一遍，才知道有哪些數據

2. 如果是取mapsize = 2ˇ16 或者 80億開方，一個map

3. 順序讀80億數據，除以mapsize取餘，同一餘數放追加同一文件,餘數作文件名

4. 順序讀取步驟3產生的所有文件，讀取的每個文件時新建mapsize大小的hashmap，統計每個數的次數，再取該hashmap中出現最多次數的整數放到新的map中

5. 依次讀完步驟3 產生的文件，就能得到每個文件最多次數的整數map

所有步驟需要80億數據的兩次讀盤，一次寫盤，mapsize次取最大值，80億數據取餘數

結翼唯乃

用類似Spark的AppendOnlyMap（本質是個用數組和開放定址法做成的Map）的思想做略小於2G內存的聚合，快滿的時候把數組元素前挪然後排序再append到單獨一個文件並清空map。遍歷完20億行數據的時候，也就生成了n個部分聚合的有序kv文件（key是數值，value是key出現的次數）。

然後每個文件生成一個Iterator，記錄當前行的值。再搞個長度為n的優先隊列，每個隊列元素是文件Iterator，排序比較的是每個文件Iterator的當前值。這樣每從優先隊列中取出一個文件Iterator，對這個Iterator取下一個kv，再把這個Iterator塞回到優先隊列。相同的key必相鄰，把連續相同的key的value相加即可得到這個key的出現次數，遍歷一次優先隊列就能知道哪個key出現次數最多

924060929

以最高位或最低位為依據分組，寫入各個文件

再從條數最多的文件開始，去掉分組標誌位，再以最高位或最低位分組，重複以上，得到一組相同數字個數，把所有低於這個條數的文件丟棄，重複過程，可以幾十k內存搞定

關鍵字: 內存 科技 程序員