|
http://blog.csdn.net/oyd/archive/2007/07/19/1699237.aspx
我這里介紹一個極適合大量URL快速排重的方法 ，這個算法被稱為Bloom filter，基本上，它也只適合這樣的場合。 這里的大量是指有5000萬至1億的URL，更大的數(shù)據(jù)量可能也不合適了。 一開始我使用了一個最復(fù)雜的做法，是有一個單獨的daemon程序負責排重，數(shù)據(jù)和排重結(jié)果通過socket傳輸。 所以，把目標鎖定在單機排重，一開始，試驗了perl中的hash，非常簡單的代碼  use DB_File;my %db;#tie %db, ‘DB_File‘, "createdb.dat", or die "Can‘t initialize db:: $! ";while(<>) { chomp $_; $db{$_} = 1;# add code here}#untie %db;從標準輸入或文件中每行一個URL讀入，插入到perl內(nèi)置的hash表中，這就成了，需要輸出結(jié)果則預(yù)先判斷一下插入的key是否存在。 這個方法速度很快，可惜的是，它占用內(nèi)存太大，假設(shè)1個URL平均50字節(jié)，5000萬個URL需要2.5G內(nèi)存。 于是又想到一個方法，把部分數(shù)據(jù)放入硬盤空間，perl中也提供一個現(xiàn)成的模塊DB_File，把上面代碼中的注釋去掉，就可使用DB_File了，用法與hash一樣，只是內(nèi)部用數(shù)據(jù)庫實現(xiàn)的。 測試了一下，速度明顯下降了一個檔次，僅40萬的數(shù)據(jù)就要1分鐘，關(guān)鍵還在于隨著數(shù)據(jù)量的增加，速度下降加快，兩者不呈線性關(guān)系。 數(shù)據(jù)量大的時候，有可能用MySQL的性能會比DB_File好，但是總體上應(yīng)該是一丘之貉，我已經(jīng)不抱期望了。 也許DB_File可以優(yōu)化一下，使用更多的內(nèi)存和少量的硬盤空間，不過這個方案還是太復(fù)雜，留給專家解決吧，一般來說，我認為簡單的方法才有可能做到高效。 下面我們的重點對象隆重登場：Bloom filter。簡單的說是這樣一種方法：在內(nèi)存中開辟一塊區(qū)域，對其中所有位置0，然后對數(shù)據(jù)做10種不同的hash，每個hash值對內(nèi)存bit數(shù)求模，求模得到的數(shù)在內(nèi)存對應(yīng)的位上置1。置位之前會先判斷是否已經(jīng)置位，每次插入一個URL，只有當全部10個位都已經(jīng)置1了才認為是重復(fù)的。 如果對上面這段話不太理解，可以換個簡單的比喻：有10個桶，一個桶只能容納1個球，每次往這些桶中扔兩個球，如果兩個桶都已經(jīng)有球，才認為是重復(fù)，問問為了不重復(fù)總共能扔多少次球？ 10次，是這個答案吧？每次扔1個球的話，也是10次。表面上看一次扔幾個球沒有區(qū)別，事實上一次兩個球的情況下，重復(fù)概率比一次一個球要低。Bloom filter算法正式借助這一點，僅僅用少量的空間就可以進行大量URL的排重，并且使誤判率極低。 有人宣稱為每個URL分配兩個字節(jié)就可以達到0沖突，我比較保守，為每個URL分配了4個字節(jié)，對于5000萬的數(shù)量級，它只占用了100多M的空間，并且排重速度超快，一遍下來不到兩分鐘，極大得滿足了我的欲望。
接上篇，起初我為了輸入輸出方便，是用perl去實現(xiàn)的，后來發(fā)現(xiàn)perl中求模速度太慢，就改用C了 常量定義：SPACE指你要分配多大的內(nèi)存空間，我這里是為5000萬數(shù)據(jù)的每一條分配4字節(jié) const int SPACE = 50000000 * 4;
const int MAXNUM = SPACE * 8; #define LINE_MAX 2048 int bits[] = {0x1, 0x2, 0x4, 0x8, 16, 32, 64, 128}; char* db = NULL; 主程序：這里循環(huán)讀入標準輸入的每一行，進行排重。 int main(int argc, char* argv[])
{ db = new char[SPACE]; memset(db, 0, SPACE); char line[LINE_MAX]; while (fgets(line, LINE_MAX, stdin) != NULL) { int len = strlen(line); len--; if (len <= 0) continue; if (!is_exist(line, len)) { // add code here } } return 0; } 判定函數(shù)：我沒有做Bloom filter算法中描述的10次hash，而是做了一個MD5，一個SHA1，然后折合成9次hash。 bool is_exist(const char* str, int len) {
unsigned int hashs[9]; unsigned char buf[20]; MD5(str, len, buf); memcpy(hashs, buf, 16); SHA1(str, len, buf); memcpy(hashs + 4, buf, 20); int k = 0; for (int j = 0; j < sizeof(hashs) / sizeof(hashs[0]); j++) { int bitnum = hashs[j] % MAXNUM; int d = bitnum / 8; int b = bitnum % 8; char byte = db[d]; if (byte & bits[b] == bits[b]) { } else { byte |= bits[b]; db[d] = byte; k++; } } return (k == 0); }
主要算法就在這里了，實際應(yīng)用的話可以采用循環(huán)監(jiān)視磁盤文件的方法來讀入排重數(shù)據(jù)，那些代碼就與操作系統(tǒng)相關(guān)，沒必要在這寫了
|
|
|
來自： Ralf_Jones > 《其它》
