※ 引述《[email protected] (遗憾太常。)》之铭言： : ※ 引述《[email protected] (Go cubs!)》之铭言： : : 第二道题: : : How to fast check if a URL is visited by web crawler? : : 我看到的解法: hash table (有这麽简单吗@@) : : 直觉上来说好像不对劲 : : 一个URL假设是20 char, 算20 bytes : : 假设Internet有5 billion pages -> 5 * 20 billion bytes = 100 billion bytes : : = 100 GB : : 100GB(至少) hastable? 有没搞错? : : 我查了一下wikipedia 上面也是说Google有个URL server专门在作这个URL revisit : : check : : 请问真的是用Hashing吗 还是Distributed Hashing?? : 我会设计的方法： : URL的有效字元 A-Z a-z 加上一些符号，大概总共算是60个symbol， : n0*60^0+n1*60^1+n2*60^2+n3*60^3+n4*60^4+...+ni*60^i : 不过这个数字大的一塌糊涂，所以不是什麽好方法； : 如果不想要collision的话，资料量可能就是那麽大。 : 至於partition的话，用开头字母就可以作uniform dist.了。 用开头字母的话大概会看到一堆http, www之类的东西..然後所有的东西都要放在同一个 partition, 用整个url算hash code可能会好一点 --

※ 发信站: 批踢踢参(ptt3.cc) ◆ From: 64.236.139.123