楔子:
問題:假設(shè)一個(gè)文件中有9億條不重復(fù)的9位整數(shù)，現(xiàn)在要求對這個(gè)文件進(jìn)行排序。
一般解題思路:
1、將數(shù)據(jù)導(dǎo)入到內(nèi)存中
2、將數(shù)據(jù)進(jìn)行排序 （比如插入排序、快速排序）
3、將排序好的數(shù)據(jù)存入文件
難題:
一個(gè)整數(shù)為4個(gè)字節(jié)
即使使用數(shù)組也需要900,000,000 * 4byte = 3.4G內(nèi)存
對于32位系統(tǒng)，訪問2G以上的內(nèi)存非常困難，而且一般設(shè)備也沒有這么多的物理內(nèi)存
將數(shù)據(jù)完全導(dǎo)入到內(nèi)存中的做法不現(xiàn)實(shí)
其他解決辦法:
1、導(dǎo)入數(shù)據(jù)庫運(yùn)算
2、分段排序運(yùn)算
3、使用bit位運(yùn)算
解決方案一:數(shù)據(jù)庫排序
將文本文件導(dǎo)入到數(shù)據(jù)庫，讓數(shù)據(jù)庫進(jìn)行索引排序操作后提取數(shù)據(jù)到文件
優(yōu)點(diǎn)：操作簡單
缺點(diǎn)：運(yùn)算速度慢，而且需要數(shù)據(jù)庫設(shè)備。
解決方案二:分段排序
操作方式：
規(guī)定一個(gè)內(nèi)存大小，比如200M，200M可以記錄52428800條記錄，我們可以每次提取5000萬條記錄到文件進(jìn)行排序，要裝滿9位整數(shù)需要20次，所以一共要進(jìn)行20次排序，需要對文件進(jìn)行20次讀操作
缺點(diǎn)：
編碼復(fù)雜，速度也慢(至少20次搜索)
關(guān)鍵步驟：
先將整個(gè)9位整數(shù)進(jìn)行分段，億條數(shù)據(jù)進(jìn)行分成20段，每段5000萬條
在文件中依次搜索0~5000萬，50000001~1億……
將排序的結(jié)果存入文件
解決方案三:bit位操作
思考下面的問題:
一個(gè)最大的9位整數(shù)為999999999
這9億條數(shù)據(jù)是不重復(fù)的
可不可以把這些數(shù)據(jù)組成一個(gè)隊(duì)列或數(shù)組，讓它有0~999999999(10億個(gè))元素
數(shù)組下標(biāo)表示數(shù)值，節(jié)點(diǎn)中用0表示這個(gè)數(shù)沒有，1表示有這個(gè)數(shù)
判斷0或1只用一個(gè)bit存儲(chǔ)就夠了
聲明一個(gè)可以包含9位整數(shù)的bit數(shù)組(10億)，一共需要10億/8=120M內(nèi)存
把內(nèi)存中的數(shù)據(jù)全部初始化為0
讀取文件中的數(shù)據(jù)，并將數(shù)據(jù)放入內(nèi)存。比如讀到一個(gè)數(shù)據(jù)為341245909這個(gè)數(shù)據(jù)，那就先在內(nèi)存中找到341245909這個(gè)bit，并將bit值置為1
遍歷整個(gè)bit數(shù)組，將bit為1的數(shù)組下標(biāo)存入文件
關(guān)鍵代碼
檢查是某一個(gè)char里面(first)的第second位中存儲(chǔ)的數(shù)據(jù)是否為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];
}
將某一個(gè)char(Desc)中的第source位置為1
bool WriteToBit (unsigned char *Desc, int source)
{
const static int mark_buf[] = {0x1, 0x2, 0x4, 0x8, 0x10, 0x20, 0x40, 0x80};
if (source > 8)
return false;
Desc[0] |= mark_buf[source];
return true;
}
案例
在某個(gè)項(xiàng)目中，我們需要對2億條手機(jī)號碼刪除重復(fù)記錄(過濾號碼黑名單同樣有效)
工作難點(diǎn)就在于如何處理這2億條電話號碼,直接用哈希表存放手機(jī)號碼不大現(xiàn)實(shí),即使經(jīng)過優(yōu)化,用一個(gè)unsigned int存放一條記錄,那也得需要2億*4=8億byte,遠(yuǎn)超過32位系統(tǒng)的尋址能力
解決方案:
將電話號碼由12位單個(gè)數(shù)字組成的字符串轉(zhuǎn)換為一個(gè)unsigned int型數(shù)據(jù)(這個(gè)完全可能,手機(jī)號碼由前三位數(shù)字和后面八位數(shù)字組成,后面八位需要占到1~1000萬的空間,而前面用0~100的數(shù)字存儲(chǔ)已經(jīng)足夠)
為簡單起見,默認(rèn)為0~4G的數(shù)字都有可能分布號碼,為此我們分配4G/32=512M的內(nèi)存
將這2億個(gè)號碼整理成unsigned int類型后按上述辦法存放在這塊內(nèi)存中(比如13512345678我們整理后為112345678,我們找到內(nèi)存中112345678bit的下標(biāo),并將此bit值設(shè)為1)
遍歷整個(gè)bit數(shù)組,記錄下所有的號碼,這些號碼即是不重復(fù)的手機(jī)號碼
總結(jié)
建立一個(gè)足夠大的bit數(shù)組當(dāng)作hash表
以bit數(shù)組的下標(biāo)來表示一個(gè)整數(shù)
以bit位中的0或1來表示這個(gè)整數(shù)是否在這個(gè)數(shù)組中存在
適用于無重復(fù)原始數(shù)據(jù)的搜索
原來每個(gè)整數(shù)需要4byte空間變?yōu)?bit，空間壓縮率為32倍
擴(kuò)展后可實(shí)現(xiàn)其他類型（包括重復(fù)數(shù)據(jù)）的搜索
注意
由于操作系統(tǒng)和編程語言本身的限制,有可能內(nèi)存足夠,但無法分配一塊連續(xù)大內(nèi)存的情況,這樣的話可以申請多塊稍微小一點(diǎn)的內(nèi)存,然后用鏈表或其他的方式連接起來使用
參考資料