※ 引述《LINC.bbs@ptt3.cc (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.了。
--
Je t'aime,o capitale infame.
Tu m'as donne ta boue et j'en ai fait de l'or.
Charles Baudelaire 1821-67
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 216.145.49.21
※ 編輯: Baudelaire 來自: 216.145.49.21 (08/24 08:03)