開篇

作者：Hawstein
出處：http://hawstein.com/posts/make-thiner-programming-pearls.html
聲明：本文采用以下協(xié)議進(jìn)行授權(quán)：?自由轉(zhuǎn)載-非商用-非衍生-保持署名|Creative Commons BY-NC-ND 3.0?，轉(zhuǎn)載請(qǐng)注明作者及出處。

開篇

具體化你的解決的問題。下面是A和B的對(duì)話。

A：我該如何對(duì)磁盤文件進(jìn)行排序？
B：需要排序的內(nèi)容是什么？文件中有多少條記錄？每個(gè)記錄的格式是什么？
A：該文件包含至多10,000,000個(gè)記錄，每條記錄都是一個(gè)7位整數(shù)。
B：如果文件那么小，為什么要使用磁盤排序呢？為什么不在主存中對(duì)它排序？
A：該功能是某大型系統(tǒng)中的一部分，大概只能提供1MB主存給它。
B：你能將記錄方面的內(nèi)容說得更詳細(xì)一些嗎？
A：每個(gè)記錄是一個(gè)7位正整數(shù)，沒有其它的關(guān)聯(lián)數(shù)據(jù)，每個(gè)整數(shù)至多只能出現(xiàn)一次。
... ...

經(jīng)過一系統(tǒng)的問題，我們可以將一個(gè)定義模糊不清的問題變得具體而清晰：

輸入：
所輸入的是一個(gè)文件，至多包含n個(gè)正整數(shù)，每個(gè)正整數(shù)都要小于n，這里n=10^7。
如果輸入時(shí)某一個(gè)整數(shù)出現(xiàn)了兩次，就會(huì)產(chǎn)生一個(gè)致命的錯(cuò)誤。
這些整數(shù)與其它任何數(shù)據(jù)都不關(guān)聯(lián)。
輸出：
以增序形式輸出經(jīng)過排序的整數(shù)列表。
約束：
大概有1MB的可用主存，但可用磁盤空間充足。運(yùn)行時(shí)間至多允許幾分鐘，
10秒鐘是最適宜的運(yùn)行時(shí)間。

如果主存容量不是嚴(yán)苛地限制在1MB，比如說可以是1MB多，或是1~2MB之間， 那么我們就可以一次性將所有數(shù)據(jù)都加載到主存中，用Bitmap來做。 10,000,000個(gè)數(shù)就需要10,000,000位，也就是10,000,000b = 1.25MB。

程序可分為三個(gè)部分：第一，初始化所有的位為0；第二，讀取文件中每個(gè)整數(shù)， 如果該整數(shù)對(duì)應(yīng)的位已經(jīng)為1，說明前面已經(jīng)出現(xiàn)過這個(gè)整數(shù)，拋出異常，退出程序 (輸入要求每個(gè)整數(shù)都只能出現(xiàn)一次)。否則，將相應(yīng)的位置1；第三， 檢查每個(gè)位，如果某個(gè)位是1，就寫出相應(yīng)的整數(shù)，從而創(chuàng)建已排序的輸出文件。

如果主存容量嚴(yán)苛地限制在1MB，而使用Bitmap需要1.25MB， 因此無法一次載入完成排序。那么，我們可以將該文件分割成兩個(gè)文件， 再分別用Bitmap處理。分割策略可以簡(jiǎn)單地把前一半的數(shù)據(jù)放到一個(gè)文件， 后一半的數(shù)據(jù)放到另一個(gè)文件，分別排序后再做歸并。 也可以把文件中小于某個(gè)數(shù)(比如5,000,000)的整數(shù)放到一個(gè)文件，叫l(wèi)ess.txt， 把其余的整數(shù)放到另一個(gè)文件，叫g(shù)reater.txt。分別排序后， 把greater.txt的排序結(jié)果追加到less.txt的排序結(jié)果即可。