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