《程式設計珠玑（第2版•修訂版）》—第1章1.4節實作概要

本節書摘來自異步社群《程式設計珠玑（第2版•修訂版）》一書中的第1章1.4節實作概要，作者【美】jon bentley，更多章節内容可以通路雲栖社群“異步社群”公衆号檢視。

1.4　實作概要

由是觀之，應該用位圖或位向量表示集合。可用一個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），程式可以使用僞代碼表示如下：

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

這個實作概要已經足以解決那個程式員的問題了。習題2、習題5和習題7描述了他會遇到的一些實作細節。