算法的力量:位運算在排序與搜尋中的應用

楔子:

問題:假設一個檔案中有9億條不重複的9位整數，現在要求對這個檔案進行排序。

一般解題思路:

1、将資料導入到記憶體中

2、将資料進行排序　（比如插入排序、快速排序）

3、将排序好的資料存入檔案

難題:

一個整數為4個位元組

即使使用數組也需要900,000,000 * 4byte = 3.4G記憶體

對于32位系統，通路2G以上的記憶體非常困難，而且一般裝置也沒有這麼多的實體記憶體

将資料完全導入到記憶體中的做法不現實

其他解決辦法:

1、導入資料庫運算

2、分段排序運算

3、使用bit位運算

解決方案一:資料庫排序

将文本檔案導入到資料庫，讓資料庫進行索引排序操作後提取資料到檔案

優點：操作簡單

缺點：運算速度慢，而且需要資料庫裝置。

解決方案二:分段排序

操作方式：

規定一個記憶體大小，比如200M，200M可以記錄52428800條記錄，我們可以每次提取5000萬條記錄到檔案進行排序，要裝滿9位整數需要20次，是以一共要進行20次排序，需要對檔案進行20次讀操作

缺點：

 編碼複雜，速度也慢(至少20次搜尋)

關鍵步驟：

先将整個9位整數進行分段，億條資料進行分成20段，每段5000萬條

在檔案中依次搜尋0~5000萬，50000001~1億……

将排序的結果存入檔案

解決方案三:bit位操作

思考下面的問題:

一個最大的9位整數為999999999

這9億條資料是不重複的

可不可以把這些資料組成一個隊列或數組，讓它有0~999999999(10億個)元素

數組下标表示數值，節點中用0表示這個數沒有，1表示有這個數

判斷0或1隻用一個bit存儲就夠了

聲明一個可以包含9位整數的bit數組(10億)，一共需要10億/8=120M記憶體

把記憶體中的資料全部初始化為0

讀取檔案中的資料，并将資料放入記憶體。比如讀到一個資料為341245909這個資料，那就先在記憶體中找到341245909這個bit，并将bit值置為1

周遊整個bit數組，将bit為1的數組下标存入檔案

關鍵代碼

檢查是某一個char裡面(first)的第second位中存儲的資料是否為1

bool CompareBit (unsigned char first, int second)

{

 const static int mark_buf[] = {0x1, 0x2, 0x4, 0x8, 0x10, 0x20, 0x40, 0x80};

 if (second > 8)

  return false;

 return  (first & mark_buf[second]) == mark_buf[second];

}

将某一個char(Desc)中的第source位置為1

bool WriteToBit (unsigned char *Desc, int source)

 if (source > 8)

 Desc[0] |= mark_buf[source];

 return true;

案例

在某個項目中，我們需要對2億條手機号碼删除重複記錄(過濾号碼黑名單同樣有效)

工作難點就在于如何處理這2億條電話号碼,直接用哈希表存放手機号碼不大現實,即使經過優化,用一個unsigned int存放一條記錄,那也得需要2億*4=8億byte,遠超過32位系統的尋址能力

解決方案:

将電話号碼由12位單個數字組成的字元串轉換為一個unsigned int型資料(這個完全可能,手機号碼由前三位數字和後面八位數字組成,後面八位需要占到1~1000萬的空間,而前面用0~100的數字存儲已經足夠)

為簡單起見,預設為0~4G的數字都有可能分布号碼,為此我們配置設定4G/32=512M的記憶體

将這2億個号碼整理成unsigned int類型後按上述辦法存放在這塊記憶體中(比如13512345678我們整理後為112345678,我們找到記憶體中112345678bit的下标,并将此bit值設為1)

周遊整個bit數組,記錄下所有的号碼,這些号碼即是不重複的手機号碼

總結

建立一個足夠大的bit數組當作hash表

以bit數組的下标來表示一個整數

以bit位中的0或1來表示這個整數是否在這個數組中存在

适用于無重複原始資料的搜尋

原來每個整數需要4byte空間變為1bit，空間壓縮率為32倍

擴充後可實作其他類型（包括重複資料）的搜尋

注意

由于作業系統和程式設計語言本身的限制,有可能記憶體足夠,但無法配置設定一塊連續大記憶體的情況,這樣的話可以申請多塊稍微小一點的記憶體,然後用連結清單或其他的方式連接配接起來使用