姓名:李歡洋? 學號 :16010110003
轉(zhuǎn)載自https://www.zhihu.com/question/20899988/answer/24923424?utm_source=com.jianshu.haruki&utm_medium=social ，有刪節(jié)壁查。
【嵌牛導(dǎo)讀】：“入門”是良好的動機，但是可能作用緩慢祖屏。如果你手里或者腦子里有一個項目，那么實踐起來你會被目標驅(qū)動买羞，而不會像學習模塊一樣慢慢學習袁勺。
【嵌牛鼻子】:python，爬蟲哩都，入門，深度學習婉徘。
【嵌牛提問】:你是否曾經(jīng)想自學python但苦于無從下手漠嵌。
【嵌牛正文】:
先長話短說summarize一下：
你需要學習
基本的爬蟲工作原理
基本的http抓取工具，scrapy
Bloom Filter: Bloom Filters by Example
如果需要大規(guī)模網(wǎng)頁抓取盖呼，你需要學習分布式爬蟲的概念儒鹿。其實沒那么玄乎，你只要學會怎樣維護一個所有集群機器能夠有效分享的分布式隊列就好几晤。最簡單的實現(xiàn)是python-rq: https://github.com/nvie/rq
rq和Scrapy的結(jié)合：darkrho/scrapy-redis · GitHub
后續(xù)處理约炎，網(wǎng)頁析取(grangier/python-goose · GitHub)，存儲(Mongodb)
以下是短話長說：
說說當初寫的一個集群爬下整個豆瓣的經(jīng)驗吧蟹瘾。
1）首先你要明白爬蟲怎樣工作圾浅。
想象你是一只蜘蛛，現(xiàn)在你被放到了互聯(lián)“網(wǎng)”上憾朴。那么狸捕，你需要把所有的網(wǎng)頁都看一遍。怎么辦呢众雷？沒問題呀灸拍，你就隨便從某個地方開始做祝，比如說人民日報的首頁，這個叫initial pages鸡岗，用$表示吧混槐。
在人民日報的首頁，你看到那個頁面引向的各種鏈接轩性。于是你很開心地從爬到了“國內(nèi)新聞”那個頁面声登。太好了，這樣你就已經(jīng)爬完了倆頁面（首頁和國內(nèi)新聞）炮姨！暫且不用管爬下來的頁面怎么處理的捌刮，你就想象你把這個頁面完完整整抄成了個html放到了你身上。
突然你發(fā)現(xiàn)舒岸， 在國內(nèi)新聞這個頁面上绅作，有一個鏈接鏈回“首頁”。作為一只聰明的蜘蛛蛾派，你肯定知道你不用爬回去的吧俄认，因為你已經(jīng)看過了啊。所以洪乍，你需要用你的腦子眯杏，存下你已經(jīng)看過的頁面地址。這樣壳澳，每次看到一個可能需要爬的新鏈接岂贩，你就先查查你腦子里是不是已經(jīng)去過這個頁面地址。如果去過巷波，那就別去了萎津。
好的，理論上如果所有的頁面可以從initial page達到的話抹镊，那么可以證明你一定可以爬完所有的網(wǎng)頁锉屈。
2）效率
如果你直接加工一下上面的代碼直接運行的話，你需要一整年才能爬下整個豆瓣的內(nèi)容垮耳。更別說Google這樣的搜索引擎需要爬下全網(wǎng)的內(nèi)容了颈渊。
問題出在哪呢？需要爬的網(wǎng)頁實在太多太多了终佛，而上面的代碼太慢太慢了俊嗽。設(shè)想全網(wǎng)有N個網(wǎng)站，那么分析一下判重的復(fù)雜度就是N*log(N)铃彰，因為所有網(wǎng)頁要遍歷一次乌询，而每次判重用set的話需要log(N)的復(fù)雜度。OK豌研，OK妹田，我知道python的set實現(xiàn)是hash——不過這樣還是太慢了唬党，至少內(nèi)存使用效率不高。
通常的判重做法是怎樣呢鬼佣？Bloom Filter. 簡單講它仍然是一種hash的方法驶拱，但是它的特點是，它可以使用固定的內(nèi)存（不隨url的數(shù)量而增長）以O(shè)(1)的效率判定url是否已經(jīng)在set中晶衷±陡伲可惜天下沒有白吃的午餐，它的唯一問題在于晌纫，如果這個url不在set中税迷，BF可以100%確定這個url沒有看過。但是如果這個url在set中锹漱，它會告訴你：這個url應(yīng)該已經(jīng)出現(xiàn)過箭养，不過我有2%的不確定性。注意這里的不確定性在你分配的內(nèi)存足夠大的時候哥牍，可以變得很小很少毕泌。一個簡單的教程:Bloom Filters by Example
注意到這個特點，url如果被看過嗅辣，那么可能以小概率重復(fù)看一看（沒關(guān)系撼泛，多看看不會累死）。但是如果沒被看過澡谭，一定會被看一下（這個很重要愿题，不然我們就要漏掉一些網(wǎng)頁了！）蛙奖。 [IMPORTANT: 此段有問題潘酗，請暫時略過]
好，現(xiàn)在已經(jīng)接近處理判重最快的方法了外永。另外一個瓶頸——你只有一臺機器崎脉。不管你的帶寬有多大拧咳，只要你的機器下載網(wǎng)頁的速度是瓶頸的話伯顶，那么你只有加快這個速度。用一臺機子不夠的話——用很多臺吧骆膝！當然祭衩，我們假設(shè)每臺機子都已經(jīng)進了最大的效率——使用多線程（python的話，多進程吧）阅签。
