資源限制類問題的常用解決方案

作者：Grey

原文位址：資源限制類問題的常用解決方法

以下提到的資料結構和元素類型均基于Java語言。

32位無符号整數的範圍是<code>0~4,294,967,295</code>(即：<code>0 ~ 2^32 - 1</code>）現在有一個正好包含40億個無符号整數的檔案，可以使用最多1GB的記憶體，怎麼找到出現次數最多的數？

首先，需要考慮最差情況，假設40億個數都不一樣。

如果使用Hash表，key表示其中的某個數，value表示出現的次數，由于

<code>40億 &gt; Integer.MAX_VALUE</code>

是以Hash表的key和value都需要<code>long</code>類型來存，

Hash表中的每條記錄至少需要

<code>8Byte + 8Byte = 16Byte</code>

最差情況，40億條不同記錄進入Hash表，

需要

<code>16Byte * 40億 = 640億Byte</code>

約等于<code>64G</code>。記憶體不夠。

如果申請數組來存，由于Java中數組長度有限制(<code>Integer.MAX_VALUE</code>)，是以要存下40億個數，一個數組一定不夠。

<code>long</code>類型的多個數組假設把所有40億個不同的數都存下，

需要的記憶體空間是：

<code>40億 * 8Byte = 320億Byte</code>

約等于<code>32G</code>, 記憶體也不夠。

如果隻有<code>1G</code>記憶體，如果用Hash表，key和value均為<code>long</code>類型，即一條記錄大約<code>8Byte</code>，保守估計，可以裝下

<code>1G / 8 Byte = 10億Byte / 8Byte = 1.25億</code>，

在這個<code>1.25億</code>基礎上再減少到<code>1千萬</code>， 處理<code>1千萬</code>種類的資料，絕對不會超過現有的記憶體限制。通過如下計算

<code>40億 / 1千萬 = 400</code>

我們可以建立400個空檔案，然後，對于每一個數m，通過hash函數得到一個hash值，假設m的哈希值為n, 然後用n

<code>hash(m) % 400 = n % 400 = i</code>

得到的i的值是多少，就把m這個值配置設定到第i号檔案中。

根據hash函數的性質，相同的數一定進入同一個檔案。 且400個檔案中每個檔案大約都是1千萬種數。

使用hash表統計每個檔案中出現次數最多的數（最多1千萬種左右，hash表在現有資源限制下無壓力），就是整個檔案出現次數最多的數。

32位無符号整數的範圍是<code>0~4,294,967,295</code>，現在有一個正好包含40億個無符号整數的檔案，是以在整個範圍中必然存在沒出現過的數, 可以使用最多1GB的記憶體，怎麼找到所有未出現過的數？

如果使用HashSet，需要用<code>long</code>類型來存，大約需要

大約<code>32G</code>，記憶體不夠。

我們可以使用bit數組(位圖)來存每個數是否出現，<code>0</code>表示出現，<code>1</code>表示沒有出現。Java中，一個<code>int</code>類型可以表示<code>32</code>位， 因為要辨別每個數是否出現過。是以<code>2^32</code>個數大約需要

<code>(2^32) / 8 = 537M</code>

537M空間的記憶體占用，滿足限制條件。

Java中，因為每個<code>int</code>數字可以表示<code>32位</code>的二進制數，是以可以使用<code>int</code>數組來構造位圖,

參考如下示例代碼(179這個數字是否出現過)：

<code>status = 0</code>則表示沒有出現過，<code>status = 1</code>則表示沒有出現過。

32位無符号整數的範圍是<code>0~4,294,967,295</code>，現在有一個正好包含40億個無符号整數的檔案，是以在整個範圍中必然存在沒出現過的數, 記憶體限制為<code>3KB</code>，隻用找到一個沒出現過的數即可。

3KB 如果用來表示<code>long</code>類型的數組，數組最大長度大約是

<code>3KB / 8Byte = 375</code>。大約<code>375</code>長度, 然後我們尋找比<code>375</code>小的離<code>375</code>最近的2的某次方的數，得到<code>256</code>, 那我們可以申請一個<code>256</code>長度的<code>long</code>類型數組，假設叫<code>arr</code>。

由于數字一共有<code>2^32</code>次方個，我們可以将

<code>2^32 / 256 = 16,777,216</code>

均分成256份，每一份負責統計每16,777,216個數出現的次數。

arr[0] 統計 <code>0 ~ 16,777,215</code>出現的次數。

arr[1] 統計 <code>16,777,216 ~ （16,777,216 + 16,777,215）</code> 出現的次數。

.....

arr[255] 統計 <code>（2^32 - 1 - 16,777,215） ~ 2^32 - 1</code> 出現過的數。

由于現在的數個數是40億, 不到2^32次方，是以，肯定有某個位置上的arr值不夠<code>16,777,216</code>個。 由于隻需要找到一個沒有出現過的數，是以隻需要在不夠16,777,216這個範圍的位置上進行再一次的<code>256</code>份的劃分，然後再次使用上述邏輯，直到劃分到某個數單獨作為一個範圍同時沒出現過，這個數就是我們需要找的數。

32位無符号整數的範圍是<code>0~4,294,967,295</code>，現在有一個正好包含40億個無符号整數的檔案，是以在整個範圍中必然存在沒出現過的數, 隻能使用有限幾個變量，如何找到一個沒出現過的數（找到一個即可）。

參考問題3，我們可以設定一個變量<code>L</code>定位第0個數，設定變量<code>R</code>定位<code>2^32-1</code>上的數，設定<code>M</code>變量定位到中間位置。由于一共有<code>2^32</code>次方個數，是以統計左邊和右邊都應該有<code>2^31</code>個數，但是總共40億個數，是以必然有一邊不滿足<code>2^31</code>方個數，然後不滿足的這一邊繼續二分，重複上述邏輯，即可找到沒有出現過的一個數字。

問題3和問題4類似，我們可以得到一個結論： 如果記憶體3KB，就用256分，如果是幾個變量，就用二分。

有一個包含100億個URL的大檔案，假設每個URL占用64B，請找出其中所有重複的URL。

如果允許失誤率，這個問題可以使用布隆過濾器來解決。

如果不允許失誤，則可以使用問題1的方法，Hash函數結合取模操作，分到小檔案思想。

32位無符号整數的範圍是<code>0~4294967295</code>，現在有40億個無符号整數，可以使用最多1GB的記憶體，找出所有出現了兩次的數。

問題2中，我們拿一個bit來表示一個數出現過一次或者沒出現過，本問題我們可以拿兩個bit來表達一個數出現的次數。

<code>00</code>表示沒出現

<code>01</code>表示出現過1次

<code>10</code>表示出現過2次

<code>11</code>表示出現過3次及3次以上

32位無符号整數的範圍是<code>0~4294967295</code>，現在有40億個無符号整數, 可以使用最多3KB的記憶體，怎麼找到這40億個整數的中位數？

參考問題3的做法，把整個<code>2^32</code>個數均分到一個256長度的<code>long</code>型數組中，每個位置管理<code>16,777,216</code>個數出現的次數。 然後逐個累加區間中數字出現的次數，一直累加到21億左右，即可判斷，中位數一定存在這個區間中。

32位無符号整數的範圍是<code>0~4294967295</code>，有一個10G大小的檔案，每一行都裝着這種類型的數字，整個檔案是無序的，給你5G的記憶體空間，請你輸出一個10G大小的檔案，就是原檔案所有數字排序的結果。

我們定義一個資料結構

value表示檔案中的數值，times表示檔案中的數值出現的次數。

然後設定一個大根堆存Node。value大的數值在堆頂， 假設堆大小我們設定為3，每次周遊的數和次數加入大根堆。大根堆滿了以後，如果新加入一個大根堆中沒有的數，則比較新加入的數和大根堆堆頂元素，如果比堆頂元素小，則剔除堆頂元素，加入新元素。周遊一輪以後，大根堆中的三個數一定是整個檔案中最小的三個數。然後把這三個數和次數依次寫入新檔案，然後繼續上述周遊和處理。每次都可以拿到三個排序後的數值，直接加入到新檔案即可。

是以，因為本問題中有<code>5G</code>記憶體，根據我們上述的方案，綽綽有餘。

某搜尋公司一天的使用者搜尋詞彙是海量的(百億資料量)，請設計一種求出每天熱門Top100詞彙的可行辦法。

參考問題1，我們可以使用Hash函數結合取模操作，分到小檔案思想。

然後使用大根堆，統計每個檔案中的top100。

最後，把每個檔案對應的大根堆的堆頂元素彈出放入新的一個大根堆（假設這個大根堆叫superHeap）中。然後從這個新的大根堆的堆頂彈出堆頂元素，即為全局top1。

然後看這個彈出的堆頂元素是來自于哪個檔案，繼續把這個檔案對應的大根堆堆頂元素彈出，繼續放入superHeap中，然後從superHeap彈出堆頂元素，就是全局top2。

依次類推，直到top100。

算法和資料結構筆記

程式員代碼面試指南（第2版）

算法和資料結構體系班-左程雲