我对算法的一点感触

xtthnfr

原帖由 nully 于 2007-9-3 13:20 发表
我的算法：

1.重排URL变量
2.md5一次，16个字节128位
3.将16字节运算得到34位数据
4.34位数据刚好使用2G文件(* 8 bit)来记录是否出现过

可能有重叠情况发生，但16G的位空间应该够用了。

用MD5的话.....其实本质上就是自己的Hash函数,用MD5来代替.

但是,MD5运算过于复杂,每运算一次需要的CPU运算次数,过多.....可做个实验....50亿次的MD5运算....花费时间太长.

所以,自己来设计的HASH函数一定要简单,速度很重要.



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

xtthnfr

原帖由 lemosa 于 2007-9-3 17:49 发表
算法就像登山中寻找的路。
找对了，能省很多力气！

对头.....这个比喻很形象.

爬到山顶,是我们程序设计的最后目的.但如何爬上去,路线选择就是算法之路了.

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

1.自己走路.

2.找个人背我上去.

3.开车上去.

4.坐缆车.

5.坐直升机...

nully

原帖由 xtthnfr 于 2007-9-3 18:13 发表


用MD5的话.....其实本质上就是自己的Hash函数,用MD5来代替.

但是,MD5运算过于复杂,每运算一次需要的CPU运算次数,过多.....可做个实验....50亿次的MD5运算....花费时间太长.

所以,自己来设计的HASH函数 ...

就我这个算法，I/O才是瓶劲，对于整个爬虫来说，网络I/O是瓶颈。
自己写出来效果很难比md5好，重叠率较高

xtthnfr

原帖由 nully 于 2007-9-3 18:23 发表


就我这个算法，I/O才是瓶劲，对于整个爬虫来说，网络I/O是瓶颈。
自己写出来效果很难比md5好，重叠率较高

MD5肯定玩不转的.....运算一次,耗费时间太长.

现在的网络速度,对于搜索引擎公司来讲,不是啥问题.

如果,你抓取的URL总数是50亿....那么你要处理的URL估计就会是 50 X N 亿次.

把所有的URL排重都放到一个MD5里面来考虑....

可以算一下时间.....可以找些URL来做实验....看看1万个URL,全部MD5运算,需要多少时间....

如果抓取回来的URL为200亿....可以大概估算出来MD5的运算时间.

有时间的写个小程序,运算一下单条URL做MD5的平均时间.

xtthnfr

原帖由 xtthnfr 于 2007-9-3 19:04 发表


MD5肯定玩不转的.....运算一次,耗费时间太长.

现在的网络速度,对于搜索引擎公司来讲,不是啥问题.

如果,你抓取的URL总数是50亿....那么你要处理的URL估计就会是 50 X N 亿次.

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

我错了....

MD5的运算速度是很快的....

写了调用MD5的小程序,速度真的很快.

醉卧水云间

原帖由 xtthnfr 于 2007-9-3 11:16 发表


我都说了是自己写HASH了....

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

终于说到用HASH了！我觉得也是。50亿个地址用多少位HASH比较合适？128？160？还是更短点就行？

醉卧水云间

原帖由 xtthnfr 于 2007-9-3 20:07 发表


我错了....

MD5的运算速度是很快的....

写了调用MD5的小程序,速度真的很快.

相对于提取网页数据，MD5的计算时间只是一小点点而已，网络再快，提取网页速度也是秒级的，计算MD5时间可以忽略不计。

chinesedragon

不参与论战～～～～～～··

jlogzl

个人对于算法的看法是：
人机部分以人为本，机器处理部分以效率为本。

unicorns

原帖由 benjiam 于 2007-9-1 16:41 发表
以后再遇到瓶颈，采用B+树算法构建索引文件

并不合适， 多个客户端 一起用 也是非常麻烦的。

使用B树是一种可选的路径。
作HASH当然效率比B树高，但是需要大内存阿。
B树只要磁盘够大就行了。还是比内存便宜很多很多的。


如果是一个要卖给客户的产品的话，只要效率完全够用，
这一点上就会增强产品竞争力了。

当然这个选型要结合具体情况分析，本身是一个权衡的过程。

多个客户端的问题没看明白，是说要同步多个客户端吗，
那这个问题无论采用哪种方式来组织都是不可避免的阿。