> 作者:Hawstein
> 出處:[http://hawstein.com/posts/make-thiner-programming-pearls.html](http://www.hawstein.com/posts/make-thiner-programming-pearls.html)
> 聲明:本文采用以下協議進行授權:?[自由轉載-非商用-非衍生-保持署名|Creative Commons BY-NC-ND 3.0](http://creativecommons.org/licenses/by-nc-nd/3.0/deed.zh)?,轉載請注明作者及出處。
## 開篇
具體化你的解決的問題。下面是A和B的對話。
~~~
A:我該如何對磁盤文件進行排序?
B:需要排序的內容是什么?文件中有多少條記錄?每個記錄的格式是什么?
A:該文件包含至多10,000,000個記錄,每條記錄都是一個7位整數。
B:如果文件那么小,為什么要使用磁盤排序呢?為什么不在主存中對它排序?
A:該功能是某大型系統中的一部分,大概只能提供1MB主存給它。
B:你能將記錄方面的內容說得更詳細一些嗎?
A:每個記錄是一個7位正整數,沒有其它的關聯數據,每個整數至多只能出現一次。
... ...
~~~
經過一系統的問題,我們可以將一個定義模糊不清的問題變得具體而清晰:
~~~
輸入:
所輸入的是一個文件,至多包含n個正整數,每個正整數都要小于n,這里n=10^7。
如果輸入時某一個整數出現了兩次,就會產生一個致命的錯誤。
這些整數與其它任何數據都不關聯。
輸出:
以增序形式輸出經過排序的整數列表。
約束:
大概有1MB的可用主存,但可用磁盤空間充足。運行時間至多允許幾分鐘,
10秒鐘是最適宜的運行時間。
~~~
如果主存容量不是嚴苛地限制在1MB,比如說可以是1MB多,或是1~2MB之間, 那么我們就可以一次性將所有數據都加載到主存中,用Bitmap來做。 10,000,000個數就需要10,000,000位,也就是10,000,000b = 1.25MB。
程序可分為三個部分:第一,初始化所有的位為0;第二,讀取文件中每個整數, 如果該整數對應的位已經為1,說明前面已經出現過這個整數,拋出異常,退出程序 (輸入要求每個整數都只能出現一次)。否則,將相應的位置1;第三, 檢查每個位,如果某個位是1,就寫出相應的整數,從而創建已排序的輸出文件。
如果主存容量嚴苛地限制在1MB,而使用Bitmap需要1.25MB, 因此無法一次載入完成排序。那么,我們可以將該文件分割成兩個文件, 再分別用Bitmap處理。分割策略可以簡單地把前一半的數據放到一個文件, 后一半的數據放到另一個文件,分別排序后再做歸并。 也可以把文件中小于某個數(比如5,000,000)的整數放到一個文件,叫less.txt, 把其余的整數放到另一個文件,叫greater.txt。分別排序后, 把greater.txt的排序結果追加到less.txt的排序結果即可。