怎樣給一個磁盤文件排序？

一位程序員曾問我一個很簡單的問題：“怎樣給一個磁盤文件排序？”想當年我是一上來就犯了錯誤，現在，在講這個故事之前，先給大家一個機會，看看能否比我當年做得更好。你會怎樣回答上述問題呢？

一次友好的對話

我錯就錯在馬上回答了這個問題。我告訴他一些有關如何在磁盤上實現歸并排序的簡要思路。我建議他深入研究算法教材，他似乎不太感冒。他更關心如何解決這個問題，而不是深入學習。于是我告訴他在一本流行的程序設計書里有磁盤排序的程序。那個程序有大約200行代碼和十幾個函數，我估計他最多需要一周時間來實現和測試該代碼。

我以為已經解決了他的問題，但是他的躊躇使我返回到了正確的軌道上。其后就有了下面的對話，楷體部分是我的問題。

為什么非要自己編寫排序程序呢？為什么不用系統提供的排序功能呢？

我需要在一個大系統中排序。由于不明的技術原因，我不能使用系統中的文件排序程序。

需要排序的內容是什么？文件中有多少條記錄？每條記錄的格式是什么？

文件最多包含1千萬條記錄，每條記錄都是7位的整數。

等一下，既然文件這么小，何必非要在磁盤上進行排序呢？為什么不在內存里進行排序呢？

盡管機器有許多兆字節的內存，但排序功能只是大系統中的一部分，所以，估計到時只有1 MB的內存可用。

你還能告訴我其他一些與記錄相關的信息嗎？

每條記錄都是7位的正整數，再無其他相關數據。每個整數最多只出現一次。

這番對話讓問題更明確了。在美國，電話號碼由3位“區號”后再跟7位數字組成。撥打含“免費”區號800（當時只有這一個號碼）的電話是不收費的。實際的免費電話號碼數據庫包含大量的信息：免費電話號碼、呼叫實際中轉到的號碼（有時是幾個號碼，這時需要一些規則來決定哪些呼叫在什么時間中轉到哪里）、主叫用戶的姓名和地址等。

這位程序員正在開發這類數據庫的處理系統的一小部分，需要排序的整數就是免費電話號碼。輸入文件是電話號碼的列表（已刪除所有其他信息），號碼重復出現算出錯。期望的輸出文件是以升序排列的電話號碼列表。應用背景同時定義了相應的性能需求。當與系統的會話時間較長時，用戶大約每小時請求一次有序文件，并且在排序未完成之前什么都干不了。因此，排序最多只允許執行幾分鐘，10秒鐘是比較理想的運行時間。

準確的問題描述

對程序員來說，這些需求加起來就是：“如何給磁盤文件排序？”在試圖解決這個問題之前，先將已知條件組織成一種更客觀、更易用的形式。

輸入：一個最多包含n個正整數的文件，每個數都小于n，其中n=107。如果在輸入文件中有任何整數重復出現就是致命錯誤。沒有其他數據與該整數相關聯。

輸出：按升序排列的輸入整數的列表。

約束：最多有（大約）1 MB的內存空間可用，有充足的磁盤存儲空間可用。運行時間最多幾分鐘，運行時間為10秒就不需要進一步優化了。

請花上一分鐘思考一下該問題的規范說明。現在你打算給程序員什么樣的建議呢？

程序設計

顯而易見的方法是以一般的基于磁盤的歸并排序程序為起點，但是要對其進行調整，因為我們是對整數進行排序。這樣就可以將原來的200行程序減少為幾十行，同時也使得程序運行得更快，但是完成程序并使之運行可能仍然需要幾天的時間。

另一種解決方案更多地利用了該排序問題的特殊性。如果每個號碼都使用7個字節來存儲，那么在可用的1 MB存儲空間里大約可以存143 000個號碼。如果每個號碼都使用32位整數來表示的話，在1 MB存儲空間里就可以存儲250 000個號碼。因此，可以使用遍歷輸入文件40趟的程序來完成排序。在第一趟遍歷中，將0至249 999之間的任何整數都讀入內存，并對這（最多）250 000個整數進行排序，然后寫到輸出文件中。第二趟遍歷排序250 000至499 999之間的整數，依此類推，到第40趟遍歷的時候對9 750 000至9 999 999之間的整數進行排序。對內存中的排序來說，快速排序會相當高效，而且僅僅需要20行代碼（見第11章）。于是，整個程序就可以通過一兩頁紙的代碼實現。該程序擁有所期望的特性——不必考慮使用中間磁盤文件；但是，為此所付出的代價是要讀取輸入文件40次。

歸并排序讀入輸入文件一次，然后在工作文件的幫助下完成排序并寫入輸出文件一次。工作文件需要多次讀寫。

40趟算法讀入輸入文件多次，寫輸出文件僅一次，不使用中間文件。

下圖所示的方案更可取。我們結合上述兩種方法的優點，讀輸入文件僅一次，且不使用中間文件。

只有在輸入文件中的所有整數都可以在可用的1 MB內存中表示的時候才能夠實現該方案。于是問題就歸結為是否能夠用大約800萬個可用位來表示最多1 000萬個互異的整數。考慮一種合適的表示方式。

實現概要

由是觀之，應該用位圖或位向量表示集合。可用一個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。

在我們的實際問題中，每個7位十進制整數表示一個小于1 000萬的整數。我們使用一個具有1 000萬個位的字符串來表示這個文件，其中，當且僅當整數i在文件中存在時，第i位為1。（那個程序員后來找到了200萬個稀疏位，習題5研究了最大存儲空間嚴格限制為1 MB的情況。）這種表示利用了該問題的三個在排序問題中不常見的屬性：輸入數據限制在相對較小的范圍內；數據沒有重復；而且對于每條記錄而言，除了單一整數外，沒有任何其他關聯數據。

若給定表示文件中整數集合的位圖數據結構，則可以分三個自然階段來編寫程序。第一階段將所有的位都置為0，從而將集合初始化為空。第二階段通過讀入文件中的每個整數來建立集合，將每個對應的位都置為1。第三階段檢驗每一位，如果該位為1，就輸出對應的整數，由此產生有序的輸出文件。令n為位向量中的位數（在本例中為10 000 000），程序可以使用偽代碼表示如下：

/*?phase?1:?initialize?set?to?empty?*/ ????for?i?=?[0,?n) ????????bit[i]?=?0/*?phase?2:?insert?present?elements?into?the?set?*/ ????for?each?i?in?the?input?file ????????bit[i]?=?1/*?phase?3:?write?sorted?output?*/ ????for?i?=?[0,?n)????????if?bit[i]?==?1 ????????????write?i?on?the?output?file

（回想在前言中所提到的，for i=[0, n)表示在從0至n-1的范圍內對i進行迭代。）

這個實現概要已經足以解決那個程序員的問題了。

那個程序員打電話把他的問題告訴我，然后我們花了大約一刻鐘時間明確了問題所在，并找到了位圖解決方案。他花了幾個小時來實現這個幾十行代碼的程序。該程序遠遠優于我們在電話剛開始時所擔心的需要花費一周時間編寫的幾百行代碼的那個程序。而且程序執行得很快：磁盤上的歸并排序可能需要許多分鐘的時間，該程序所需的時間只比讀取輸入和寫入輸出所需的時間多一點點——大約10秒鐘。

從這些事實中可以總結出該實例研究所得到的第一個結論：對小問題的仔細分析有時可以得到明顯的實際益處。在該實例中，幾分鐘的仔細研究可以大幅削減代碼的長度、程序員時間和程序運行時間。Chuck Yeager將軍（第一個超音速飛行的人）贊揚一架飛機的機械系統時用的詞是“結構簡單、部件很少、易于維護、非常堅固”，該程序擁有同樣的屬性。

本文節選自《編程珠璣（第2版?修訂版）》

內容簡介

本文轉載自異步社區。

軟件開發 軟件開發

版權聲明：本文內容由網絡用戶投稿，版權歸原作者所有，本站不擁有其著作權，亦不承擔相應法律責任。如果您發現本站中有涉嫌抄襲或描述失實的內容，請聯系我們jiasou666@gmail.com 處理，核實后本網站將在24小時內刪除侵權內容。