我對(duì)算法的一點(diǎn)感觸

xtthnfr

原帖由 nully 于 2007-9-3 13:20 發(fā)表
我的算法：

1.重排URL變量
2.md5一次，16個(gè)字節(jié)128位
3.將16字節(jié)運(yùn)算得到34位數(shù)據(jù)
4.34位數(shù)據(jù)剛好使用2G文件(* 8 bit)來記錄是否出現(xiàn)過

可能有重疊情況發(fā)生，但16G的位空間應(yīng)該夠用了。

用MD5的話.....其實(shí)本質(zhì)上就是自己的Hash函數(shù),用MD5來代替.

但是,MD5運(yùn)算過于復(fù)雜,每運(yùn)算一次需要的CPU運(yùn)算次數(shù),過多.....可做個(gè)實(shí)驗(yàn)....50億次的MD5運(yùn)算....花費(fèi)時(shí)間太長(zhǎng).

所以,自己來設(shè)計(jì)的HASH函數(shù)一定要簡(jiǎn)單,速度很重要.



[ 本帖最后由 xtthnfr 于 2007-9-3 18:19 編輯 ]

xtthnfr

原帖由 lemosa 于 2007-9-3 17:49 發(fā)表
算法就像登山中尋找的路。
找對(duì)了，能省很多力氣！

對(duì)頭.....這個(gè)比喻很形象.

爬到山頂,是我們程序設(shè)計(jì)的最后目的.但如何爬上去,路線選擇就是算法之路了.

我能想到的爬山路線有...

1.自己走路.

2.找個(gè)人背我上去.

3.開車上去.

4.坐纜車.

5.坐直升機(jī)...

nully

原帖由 xtthnfr 于 2007-9-3 18:13 發(fā)表


用MD5的話.....其實(shí)本質(zhì)上就是自己的Hash函數(shù),用MD5來代替.

但是,MD5運(yùn)算過于復(fù)雜,每運(yùn)算一次需要的CPU運(yùn)算次數(shù),過多.....可做個(gè)實(shí)驗(yàn)....50億次的MD5運(yùn)算....花費(fèi)時(shí)間太長(zhǎng).

所以,自己來設(shè)計(jì)的HASH函數(shù) ...

就我這個(gè)算法，I/O才是瓶勁，對(duì)于整個(gè)爬蟲來說，網(wǎng)絡(luò)I/O是瓶頸。
自己寫出來效果很難比md5好，重疊率較高

xtthnfr

原帖由 nully 于 2007-9-3 18:23 發(fā)表


就我這個(gè)算法，I/O才是瓶勁，對(duì)于整個(gè)爬蟲來說，網(wǎng)絡(luò)I/O是瓶頸。
自己寫出來效果很難比md5好，重疊率較高

MD5肯定玩不轉(zhuǎn)的.....運(yùn)算一次,耗費(fèi)時(shí)間太長(zhǎng).

現(xiàn)在的網(wǎng)絡(luò)速度,對(duì)于搜索引擎公司來講,不是啥問題.

如果,你抓取的URL總數(shù)是50億....那么你要處理的URL估計(jì)就會(huì)是 50 X N 億次.

把所有的URL排重都放到一個(gè)MD5里面來考慮....

可以算一下時(shí)間.....可以找些URL來做實(shí)驗(yàn)....看看1萬個(gè)URL,全部MD5運(yùn)算,需要多少時(shí)間....

如果抓取回來的URL為200億....可以大概估算出來MD5的運(yùn)算時(shí)間.

有時(shí)間的寫個(gè)小程序,運(yùn)算一下單條URL做MD5的平均時(shí)間.

xtthnfr

原帖由 xtthnfr 于 2007-9-3 19:04 發(fā)表


MD5肯定玩不轉(zhuǎn)的.....運(yùn)算一次,耗費(fèi)時(shí)間太長(zhǎng).

現(xiàn)在的網(wǎng)絡(luò)速度,對(duì)于搜索引擎公司來講,不是啥問題.

如果,你抓取的URL總數(shù)是50億....那么你要處理的URL估計(jì)就會(huì)是 50 X N 億次.

把所有的URL排重都放到 ...

我錯(cuò)了....

MD5的運(yùn)算速度是很快的....

寫了調(diào)用MD5的小程序,速度真的很快.

醉臥水云間

原帖由 xtthnfr 于 2007-9-3 11:16 發(fā)表


我都說了是自己寫HASH了....

搜索引擎里面很多地方都用到HASH.

終于說到用HASH了！我覺得也是。50億個(gè)地址用多少位HASH比較合適？128？160？還是更短點(diǎn)就行？

醉臥水云間

原帖由 xtthnfr 于 2007-9-3 20:07 發(fā)表


我錯(cuò)了....

MD5的運(yùn)算速度是很快的....

寫了調(diào)用MD5的小程序,速度真的很快.

相對(duì)于提取網(wǎng)頁數(shù)據(jù)，MD5的計(jì)算時(shí)間只是一小點(diǎn)點(diǎn)而已，網(wǎng)絡(luò)再快，提取網(wǎng)頁速度也是秒級(jí)的，計(jì)算MD5時(shí)間可以忽略不計(jì)。

chinesedragon

不參與論戰(zhàn)～～～～～～··

jlogzl

個(gè)人對(duì)于算法的看法是：
人機(jī)部分以人為本，機(jī)器處理部分以效率為本。

unicorns

原帖由 benjiam 于 2007-9-1 16:41 發(fā)表
以后再遇到瓶頸，采用B+樹算法構(gòu)建索引文件

并不合適， 多個(gè)客戶端 一起用 也是非常麻煩的。

使用B樹是一種可選的路徑。
作HASH當(dāng)然效率比B樹高，但是需要大內(nèi)存阿。
B樹只要磁盤夠大就行了。還是比內(nèi)存便宜很多很多的。


如果是一個(gè)要賣給客戶的產(chǎn)品的話，只要效率完全夠用，
這一點(diǎn)上就會(huì)增強(qiáng)產(chǎn)品競(jìng)爭(zhēng)力了。

當(dāng)然這個(gè)選型要結(jié)合具體情況分析，本身是一個(gè)權(quán)衡的過程。

多個(gè)客戶端的問題沒看明白，是說要同步多個(gè)客戶端嗎，
那這個(gè)問題無論采用哪種方式來組織都是不可避免的阿。