姓名:李歡洋? 學號 :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的話，多進程吧）。