大數據排序算法，海量數據處理---外排序

方法介紹

所謂外排序，顧名思義，即是在內存外面的排序，因為當要處理的數據量很大，而不能一次裝入內存時，此時只能放在讀寫較慢的外存儲器（通常是硬盤）上。

外排序通常采用的是一種“排序-歸并”的策略。大數據排序算法、

• 在排序階段，先讀入能放在內存中的數據量，將其排序輸出到一個臨時文件，依此進行，將待排序數據組織為多個有序的臨時文件；
• 爾后在歸并階段將這些臨時文件組合為一個大的有序文件，也即排序結果。

假定現在有20個數據的文件A：{5 11 0 18 4 14 9 7 6 8 12 17 16 13 19 10 2 1 3 15}，但一次只能使用僅裝4個數據的內容，所以，我們可以每趟對4個數據進行排序，即5路歸并，具體方法如下述步驟：

• 我們先把“大”文件A，分割為a1，a2，a3，a4，a5等5個小文件，每個小文件4個數據

  • a1文件為：5 11 0 18
  • a2文件為：4 14 9 7
  • a3文件為：6 8 12 17
  • a4文件為：16 13 19 10
  • a5文件為：2 1 3 15

• 然后依次對5個小文件分別進行排序

  • a1文件完成排序后：0 5 11 18
  • a2文件完成排序后：4 7 9 14
  • a3文件完成排序后：6 8 12 17
  • a4文件完成排序后：10 13 16 19
  • a5文件完成排序后：1 2 3 15

• 最終多路歸并，完成整個排序

  • 整個大文件A文件完成排序后：0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

問題實例

1、給10^7個數據量的磁盤文件排序

輸入：給定一個文件，里面最多含有n個不重復的正整數（也就是說可能含有少于n個不重復正整數），且其中每個數都小于等于n，n=10^7。多列數據排序？ 輸出：得到按從小到大升序排列的包含所有輸入的整數的列表。 條件：最多有大約1MB的內存空間可用，但磁盤空間足夠。且要求運行時間在5分鐘以下，10秒為最佳結果。

解法一：位圖方案

你可能會想到把磁盤文件進行歸并排序，但題目要求你只有1MB的內存空間可用，所以，歸并排序這個方法不行。

熟悉位圖的朋友可能會想到用位圖來表示這個文件集合。例如正如編程珠璣一書上所述，用一個20位長的字符串來表示一個所有元素都小于20的簡單的非負整數集合，邊框用如下字符串來表示集合{1,2,3,5,8,13}：

0 1 1 1 0 1 0 0 1 0 0 0 0 1 0 0 0 0 0 0

上述集合中各數對應的位置則置1，沒有對應的數的位置則置0。

參考編程珠璣一書上的位圖方案，針對我們的10^7個數據量的磁盤文件排序問題，我們可以這么考慮，由于每個7位十進制整數表示一個小于1000萬的整數。我們可以使用一個具有1000萬個位的字符串來表示這個文件，其中，當且僅當整數i在文件中存在時，第i位為1。采取這個位圖的方案是因為我們面對的這個問題的特殊性：

1. 輸入數據限制在相對較小的范圍內，
2. 數據沒有重復，
3. 其中的每條記錄都是單一的整數，沒有任何其它與之關聯的數據。

所以，此問題用位圖的方案分為以下三步進行解決：

• 第一步，將所有的位都置為0，從而將集合初始化為空。
• 第二步，通過讀入文件中的每個整數來建立集合，將每個對應的位都置為1。
• 第三步，檢驗每一位，如果該位為1，就輸出對應的整數。

經過以上三步后，產生有序的輸出文件。令n為位圖向量中的位數（本例中為1000 0000），程序可以用偽代碼表示如下：

//磁盤文件排序位圖方案的偽代碼  
//copyright@ Jon Bentley  
//July、updated，2011.05.29。  //第一步，將所有的位都初始化為0  
for i ={0,....n}      bit[i]=0;  
//第二步，通過讀入文件中的每個整數來建立集合，將每個對應的位都置為1。  
for each i in the input file     bit[i]=1;  //第三步，檢驗每一位，如果該位為1，就輸出對應的整數。  
for i={0...n}      if bit[i]==1        write i on the output file  

上述的位圖方案，共需要掃描輸入數據兩次，具體執行步驟如下：

第一次，只處理1—4999999之間的數據，這些數都是小于5000000的，對這些數進行位圖排序，只需要約5000000/8=625000Byte，也就是0.625M，排序后輸出。 第二次，掃描輸入文件時，只處理4999999-10000000的數據項，也只需要0.625M（可以使用第一次處理申請的內存）。 因此，總共也只需要0.625M 位圖的的方法有必要強調一下，就是位圖的適用范圍為針對不重復的數據進行排序，若數據有重復，位圖方案就不適用了。

不過很快，我們就將意識到，用此位圖方法，嚴格說來還是不太行，空間消耗10^7/8還是大于1M（1M=1024*1024空間，小于10^7/8）。

既然如果用位圖方案的話，我們需要約1.25MB（若每條記錄是8位的正整數的話，則10000000/(102410248) ~= 1.2M）的空間，而現在只有1MB的可用存儲空間，那么究竟該作何處理呢？

解法二：多路歸并

誠然，在面對本題時，還可以通過計算分析出可以用如2的位圖法解決，但實際上，很多的時候，我們都面臨著這樣一個問題，文件太大，無法一次性放入內存中計算處理，那這個時候咋辦呢？分而治之，大而化小，也就是把整個大文件分為若干大小的幾塊，然后分別對每一塊進行排序，最后完成整個過程的排序。k趟算法可以在kn的時間開銷內和n/k的空間開銷內完成對最多n個小于n的無重復正整數的排序。

比如可分為2塊（k=2，1趟反正占用的內存只有1.25/2M），1~4999999，和5000000~9999999。先遍歷一趟，首先排序處理1~4999999之間的整數（用5000000/8=625000個字的存儲空間來排序0~4999999之間的整數），然后再第二趟，對5000001~1000000之間的整數進行排序處理。

解法總結

1、關于本章中位圖和多路歸并兩種方案的時間復雜度及空間復雜度的比較，如下：

        時間復雜度        空間復雜度位圖          O(N)          0.625M多位歸并   O(Nlogn)             1M

（多路歸并，時間復雜度為O（kn/klogn/k ），嚴格來說，還要加上讀寫磁盤的時間，而此算法絕大部分時間也是浪費在這上面）

2、bit-map

適用范圍：可進行數據的快速查找，判重，刪除，一般來說數據范圍是int的10倍以下

基本原理及要點：使用bit數組來表示某些元素是否存在，比如8位電話號碼

擴展：bloom filter可以看做是對bit-map的擴展

舉一反三

1、已知某個文件內包含一些電話號碼，每個號碼為8位數字，統計不同號碼的個數。 8位最多99 999 999，大概需要99m個bit，大概10幾m字節的內存即可。