有2種辦法;多路歸并排序和位圖法.

多路歸并排序

采用分塊的方法（分而治之），首先將數據分塊，對塊內數據按選擇一種高效的內排序策略進行排序(如快速排序)。然后采用歸并排序的思想對于所有的塊進行排序，得到所有數據的一個有序序列。

1TB數據使用32GB內存如何排序
　　①、把磁盤上的1TB數據分割為40塊（chunks），每份25GB。（注意，要留一些系統空間！）
　　②、順序將每份25GB數據讀入內存，使用quick sort算法排序。
　　③、把排序好的數據（也是25GB）存放回磁盤。
　　④、循環40次，現在，所有的40個塊都已經各自排序了。（剩下的工作就是如何把它們合并排序！）
　　⑤、從40個塊中分別讀取25G/40=0.625G入內存（40 input buffers）。
　　⑥、執行40路合并，并將合并結果臨時存儲于2GB 基于內存的輸出緩沖區中。當緩沖區寫滿2GB時，寫入硬盤上最終文件，并清空輸出緩沖區；當40個輸入緩沖區中任何一個處理完畢時，寫入該緩沖區所對應的塊中的下一個0.625GB，直到全部處理完成。

繼續優化
　　磁盤I/O通常是越少越好（最好完全沒有），那么如何降低磁盤I/O操作呢？關鍵就在第5和第6步中的40路輸入緩沖區，我們可以先做8路merge sort，把每8個塊合并為1路，然后再做5-to-1的合并操作。

所以K路合并的次數為 logk(N/M)的向上取整。n為數據總大小，m為最大的內存。

　　再深入思考一下，如果有多余的硬件，如何繼續優化呢？有三個方向可以考慮：
　　使用并發：如多磁盤（并發I/O提高）、多線程、使用異步I/O、使用多臺主機集群計算。
　　提升硬件性能：如更大內存、更高RPM的磁盤、升級為SSD、Flash、使用更多核的CPU。
　　提高軟件性能：比如采用radix sort、壓縮文件（提高I/O效率）等。

位圖法

前提是數據不重復。

缺點：不適用的場景有數據稀疏。要存入(10,8887983,93452134)這三個數據，我們需要建立一個 99999999 長度的 BitMap ，但是實際上只存了3個數據，這時候就有很大的空間浪費

在c++中使用 new byte的思路進行處理。如果想用bitset數組的話，數量就不能很大（因為是在棧上創建內存空間的）。

實現過程: 找出整個數組的最大元素max，然后創建一個長度為max + 1的新數組，然后再次掃原數組，遇到幾就給新數組的第幾位置上置1.最后重新遍歷整個新數組進行輸出。

優點就是：1內存空間少.2 運算時間快。

#define max_len 4000000000DWORD dwstart = GetTickCount();byte *bt = new byte[max_len];memset(bt, 0, sizeof(byte)*max_len);for (int64_t i = 0; i <= max_len; i++){if (bt[i] == 1){}}DWORD dwend = GetTickCount();DWORD dw = dwend - dwstart;delete []bt;//測試遍歷40億的數據，內存是4G,大概需要8s.改造,使用bitsetDWORD dwstart = GetTickCount();bitset<max_len+1> bt;for (int64_t i = 0; i <= max_len; i++){if (bt[i] == 1){}}DWORD dwend = GetTickCount();DWORD dw = dwend - dwstart;//測試遍歷40億的數據，內存是500M,大概需要91s.因為是在堆棧上開辟內存，所以要設置vs的堆棧大小，這里設置為600M.

延伸：處理海量數據問題：

1.分而治之/hash映射 + hash統計 + 堆/快速/歸并排序；
2.雙層桶劃分
3.Bloom filter/Bitmap；
4.Trie樹/數據庫/倒排索引；
5.外排序；
6.分布式處理之Hadoop/Mapreduce。

教你如何迅速秒殺掉：99%的海量數據處理面試題_v_JULY_v的博客-CSDN博客
?

前提基礎：序列容器

序列式容器(vector/list/deque/stack/queue/heap)

關聯容器（set/map/multiset/multimap）

散列容器或者說哈希列表 （hash_set/hash_map/hash_multiset/hash_multimap）

分而治之/hash映射 + hash統計 + 堆/快速/歸并排序

說白了，就是先映射，而后統計，最后排序：
分而治之/hash映射：針對數據太大，內存受限，只能是：把大文件化成(取模映射)小文件，即16字方針：大而化小，各個擊破，縮小規模，逐個解決
hash_map統計：當大文件轉化了小文件，那么我們便可以采用常規的hash_map(ip，value)來進行頻率統計。時間復雜度為n*o(1).
堆/快速排序：統計完了之后，便進行排序(可采取堆排序)，得到次數最多的IP。時間復雜度為N'*logK
?

具體步驟是：在海量的數據中，沒法一次性把數據放進內存。操作思路：使用分治思維＋hash。分治表現為外排序的多路歸并排序。

1.要考慮分成N塊小文件，分塊的思想是：hash散列表，目的是把相同的數據放到一個小文件。

如果文件不是特別大，看能否一次性裝進內存不，如可以，就不用映射分塊文件了。

2.對分塊的小文件進行歸并排序，或者hash統計及排序。

3.已經排好序的分塊文件中，提取想要的數據，進行歸并整合成新文件。

4.有可能進行重復2-3的步驟，直到滿足要求。

多層劃分

多層劃分----其實本質上還是分而治之的思想，重在“分”的技巧上！
　　適用范圍：第k大，中位數，不重復或重復的數字
　　基本原理及要點：因為元素范圍很大，不能利用直接尋址表，所以通過多次劃分，逐步確定范圍，然后最后在一個可以接受的范圍內進行。

如 2.5億個整數中找出不重復的整數的個數，內存空間不足以容納這2.5億個整數。
? ? 有點像鴿巢原理，整數個數為2^32,也就是，我們可以將這2^32個數，劃分為2^8個區域(比如用單個文件代表一個區域)，然后將數據分離到不同的區域，然后不同的區域在利用bitmap就可以直接解決了。也就是說只要有足夠的磁盤空間，就可以很方便的解決。

Bloom filter/Bitmap

其中Bitmap　適用范圍：可進行數據的快速查找，判重，刪除，一般來說數據范圍是int的10倍以下基本原理及要點：使用bit數組來表示某些元素是否存在，比如8位電話號碼。見上面的位圖法。

擴展：bloom filter可以看做是對bit-map的擴展。還有2-bitmap.

將bit-map擴展一下，用2bit表示一個數即可，0表示未出現，1表示出現一次，2表示出現2次及以上。或者我們不用2bit來進行表示，我們用兩個bit-map即可模擬實現這個2bit-map。

外排序

　　適用范圍：大數據的排序，去重
　　基本原理及要點：外排序的歸并方法，置換選擇敗者樹原理，最優歸并樹
?問題實例：
　　1).有一個1G大小的一個文件，里面每一行是一個詞，詞的大小不超過16個字節，內存限制大小是1M。返回頻數最高的100個詞。
　　這個數據具有很明顯的特點，詞的大小為16個字節，但是內存只有1M做hash明顯不夠，所以可以用來排序。內存可以當輸入緩沖區使用。

具體見最上面的介紹
?

Trie樹/數據庫/倒排索引

Trie樹

　　適用范圍：數據量大，重復多，但是數據種類小可以放入內存
　　基本原理及要點：實現方式，節點孩子的表示方式
　　擴展：壓縮實現。

數據庫索引
　　適用范圍：大數據量的增刪改查
　　基本原理及要點：利用數據的設計實現方法，對海量數據的增刪改查進行處理。

倒排索引(Inverted index)
　　適用范圍：搜索引擎，關鍵字查詢
　　基本原理及要點：為何叫倒排索引？一種索引方法，被用來存儲在全文搜索下某個單詞在一個文檔或者一組文檔中的存儲位置的映射。

分布式處理之Mapreduce

? ? MapReduce是一種計算模型，簡單的說就是將大批量的工作（數據）分解（MAP）執行，然后再將結果合并成最終結果（REDUCE）。這樣做的好處是可以在任務被分解后，可以通過大量機器進行并行計算，減少整個操作的時間。但如果你要我再通俗點介紹，那么，說白了，Mapreduce的原理就是一個歸并排序。

?適用范圍：數據量大，但是數據種類小可以放入內存
?基本原理及要點：將數據交給不同的機器去處理，數據劃分，結果歸約。
?

例子：

給40億個不重復的unsigned int的整數進行排序。

//排序，按升序排列的輸入正數的列表#define max_len 4000000000DWORD dwstart = GetTickCount();bitset<max_len+1> bt1;FILE *fpsrc;fpsrc = fopen("data.txt", "r");int data;while (fscanf(fpsrc, "%d ", &data) != EOF){if (data <= max_len){bt1.set(data, 1);}}FILE *fpdst;fpdst = fopen("result.txt", "w");for (int64_t i = 0; i <= max_len; i++){if (bt1[i] == 1){fprintf(fpdst, "%d ", i);}}fclose(fpdst);fclose(fpsrc);DWORD dwend = GetTickCount();DWORD dw = dwend - dwstart;時間復雜度為O（2N）,N表示總數

給40億個不重復的unsigned int的整數，沒排過序的，然后再給一個數，如何快速判斷這個數是否在那40億個數當中？

解：申請512M的內存，一個bit位代表一個unsigned int值。讀入40億個數，設置相應的bit位，讀入要查詢的數，查看相應bit位是否為1，為1表示存在，為0表示不存在。

//排序，按升序排列的輸入正數的列表DWORD dwstart = GetTickCount();bitset<max_len+1> bt1;FILE *fpsrc;fpsrc = fopen("data.txt", "r");int data;while (fscanf(fpsrc, "%d ", &data) != EOF){if (data <= max_len){bt1.set(data, 1);}}int ndst;if (bt1[ndst] == 1){//表示存在}fclose(fpsrc);DWORD dwend = GetTickCount();DWORD dw = dwend - dwstart;時間復雜度為O（N）,N表示總數 解法二： 又因為2^32為40億多，所以給定一個數可能在，也可能不在其中； 這里我們把40億個數中的每一個用32位的二進制來表示 假設這40億個數開始放在一個文件中。然后將這40億個數分成兩類:1.最高位為02.最高位為1并將這兩類分別寫入到兩個文件中，其中一個文件中數的個數<=20億，而另一個>=20億（這相當于折半了）； 與要查找的數的最高位比較并接著進入相應的文件再查找再然后把這個文件為又分成兩類:1.次最高位為02.次最高位為1并將這兩類分別寫入到兩個文件中，其中一個文件中數的個數<=10億，而另一個>=10億（這相當于折半了）；與要查找的數的次最高位比較并接著進入相應的文件再查找。.......以此類推，就可以找到了,而且時間復雜度為O(logn)，方案2完。

?

在2.5億個整數中找出不重復的正整數，注，內存不足以容納這2.5億個整數

解法1：采用2-Bitmap（每個數分配2bit，00表示不存在，01表示出現一次，10表示多次，11無意義）。 解法2：采用2個bitmap.即第一個Bitmap存儲的是整數是否出現過， 如果沒出現過，把第一個bitmap對應的位置置1. 如果出現過就設置第二個BitMap對應的位置也為1。 最后同時遍歷這2個BitMap，僅僅在第一個BitMap相應位置為1，第二個bitmap相應位置為0的元素，就是不重復的整數。int temp;bitset<max_len+1> bt1(0);bitset<max_len+1> bt2(0);for (int i= 0; i < max_len;i++){if (bt1[temp] == 0){bt1.set(temp,1);}else{bt2.set(temp, 1);}}for (int i = 0; i < max_len; i++){if (bt1[i] == 1 && bt2[i] == 0){//只有一次}}

?搜索引擎會通過日志文件把用戶每次檢索使用的所有檢索串都記錄下來，每個查詢串的長度為1-255字節。
? ? 假設目前有一千萬個記錄（這些查詢串的重復度比較高，雖然總數是1千萬，但如果除去重復后，不超過3百萬個。一個查詢串的重復度越高，說明查詢它的用戶越多，也就是越熱門。），請你統計最熱門的10個查詢串，要求使用的內存不能超過1G。
?

要統計最熱門查詢，首先就是要統計每個Query出現的次數，然后根據統計結果，找出Top 10。 第一步：Query統計 使用Hash Table法（散列表法），因為散列表的每個元素的查找時間復雜度是0（1）。事實上只有300萬的Query，每個Query255Byte，那總大小是7百多M,1G的內存夠用。因此我們可以考慮把他們都放進內存中去。 具體是：維護一個Key為Query字串，Value為該Query出現次數的HashTable，每次讀取一個Query，如果該字串不在Table中，那么加入該字串，并且將Value值設為1；如果該字串在Table中，那么將該字串的計數加一即可。最終我們在O(N)的時間復雜度內完成了對該海量數據的處理。n表示1000萬。 第二步：找出Top 10 辦法1：沒有必要對所有的Query都進行排序，我們只需要維護一個10個大小的數組，初始化放入10個Query，按照每個Query的統計次數由大到小排序，因為有序，每一次可以采用二分的方法查找，遍歷這300萬條記錄。最后當所有的數據都遍歷完畢之后，那么這個數組中的10個Query便是我們要找的Top10了。排序的時間復雜度是N'*O（logK）。 n'表示的是300萬，k表示10 辦法二：借助堆結構，我們可以在log量級的時間內查找和調整/移動。維護一個K(該題目中是10)大小的小根堆，然后遍歷300萬的Query，分別和根元素進行對比。 具體過程是，堆頂存放的是整個堆中最小的數，現在遍歷N個數，把最先遍歷到的k個數存放到最小堆中，并假設它們就是我們要找的最大的k個數，X1>X2...Xmin(堆頂)，而后遍歷后續的N-K個數，一一與堆頂元素進行比較，如果遍歷到的Xi大于堆頂元素Xmin，則把Xi放入堆中，而后更新整個堆，更新的時間復雜度為logK，如果Xi<Xmin，則不更新堆，整個過程的復雜度為O(K)+O(（N-K）*logK)=O（N*logK）。 總結： 經過上述第一步、先用Hash表統計每個Query出現的次數，O（N）；然后第二步、采用堆數據結構找出Top 10，N*O（logK）。所以，我們最終的時間復雜度是：O（N） + N'*O（logK）

有一個1G大小的一個文件，里面每一行是一個詞，詞的大小不超過16字節，內存限制大小是1M。返回頻數最高的100個詞。
?

? ? 方案：順序讀文件中，對于每個詞x，取hash(x)%5000， 然后按照該值存到5000個小文件（記為x0,x1,...x4999）中。 這樣每個文件大概是200k左右。如果其中的有的文件超過了1M大小，還可以按照類似的方法繼續往下分， 直到分解得到的小文件的大小都不超過1M。對每個小文件，統計每個文件中出現的詞以及相應的頻率（可以采用trie樹/hash_map等）， 并取出出現頻率最大的100個詞（可以用含100個結點的最小堆）， 并把100個詞及相應的頻率存入文件，這樣又得到了5000個文件。 下一步就是把這5000個文件進行歸并（類似與歸并排序）的過程了。

有10個文件，每個文件1G，每個文件的每一行存放的都是用戶的query，每個文件的query都可能重復。要求你按照query的頻度排序。

一般query的總量是有限的，只是重復的次數比較多而已， 可能對于所有的query，一次性就可以加入到內存了。 這樣，我們就可以采用trie樹/hash_map等直接來統計每個query出現的次數， 然后按出現次數做快速/堆/歸并排序就可以了。

海量日志數據，提取出某日訪問百度次數最多的那個IP。

算法思想：分而治之+Hash1.IP地址最多有2^32=4G種取值情況，所以不能完全加載到內存中處理； 2.可以考慮采用“分而治之”的思想，按照IP地址的Hash(IP)%1024值，把海量IP日志分別存儲到1024個小文件中。如果要求使用內存很小，同時按hash分出的文件大小大于要求的內存，則繼續對分出來的文件求hash繼續分，知道所有的文件大小都小于要求的內存；3.對于每一個小文件，可以構建一個IP為key，出現次數為value的Hash map，同時記錄當前出現次數最多的那個IP地址； 4.可以得到1024個小文件中的出現次數最多的IP，再依據常規的排序算法得到總體上出現次數最多的IP；

在2.5億個整數中找出不重復的整數，注，內存不足以容納這2.5億個整數。

可以考慮采用“分而治之”的思想，按照hash散列表,進行劃分小文件的方法。 然后在小文件使用hash key為數值，value為數值的次數，進行記錄，從而找出不重復的整數，并排序。 然后再進行歸并，注意去除重復的元素。

十道海量數據處理面試題與十個方法大總結_v_JULY_v的博客-CSDN博客

總結

以上是生活随笔為你收集整理的处理海量数据的磁盘外排序算法的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。