高效替代「in」

我正在編寫一個網絡爬蟲，其最終目標是創建爬蟲所採用路徑的地圖。雖然我不知道其他什麼比例，並且絕對是更好的爬蟲拉下頁面，但我的時鐘大約是每分鐘2000頁。高效替代「in」

爬蟲工作在遞歸回溯算法，我已經限制在15的深度。此外，爲了防止我的爬行程序無休止地重新訪問頁面，它將它訪問過的每個頁面的url存儲在列表中，並檢查下一個候選URL的列表。

for href in tempUrl: 
    ... 
    if href not in urls: 
     collect(href,parent,depth+1)

這種方法在下拉大約300,000頁時似乎成了問題。此時，爬蟲平均每分鐘記錄500頁。

所以我的問題是，什麼是實現相同的功能，同時提高其效率的另一種方法。

我認爲減小每個條目的大小可能會有所幫助，所以不是追加整個url，而是將每個url的前兩個和最後一個字符附加爲一個字符串。但是，這並沒有幫助。

有沒有一種方法，我可以做套或什麼的？

感謝您的幫助

編輯：作爲一個方面說明，我的計劃是沒有多線程。我想我應該在瞭解線程之前解決這個瓶頸問題。

來源

2011-06-28 danem

也許您可以使用set而不是list作爲您迄今爲止看到的網址。

來源

2011-06-28 16:17:18

我只是按照我列表的方式檢查它嗎？這樣一個簡單的改變，性能是否真的會提高？ D： – danem

+1作爲一個嘗試，檢查集中的存在應該是O（1）iirc，我已經看到驚人的加速檢查現有的切換到集列表 – Davy8

@Pete，是 - 測試會員資格集和字典是O（1），在列表和元組中，O（n）在列表/元組長度中。所以對於長列表/元組來說，它會產生一個_huge_差異。（+1 btw。） – senderle

改爲使用dict作爲關鍵字（O（1）訪問時間）作爲關鍵字。

但一套也將工作。見

http://wiki.python.org/moin/TimeComplexity

來源

2011-06-28 16:19:02

非常豐富的鏈接。謝謝！ – danem

我也有類似的問題。結束分析內存與時間的各種方法（列表/文件/集/ sqlite）。看到這2個職位。最後sqlite是最好的選擇。您還可以使用URL哈希，以減少大小

Searching for a string in a large text file - profiling various methods in python

sqlite database design with millions of 'url' strings - slow bulk import from csv

來源

2011-06-28 16:19:28 Medorator

簡單「與‘抓取的網址set’取代你的「抓取的網址列表。Sets是隨機存取優化（使用與詞典使用的散列算法相同），它們的速度快得多，列表的查找操作使用線性搜索來完成，因此速度並不是特別快，您不需要更改查找的實際代碼。

看看這個。

In [3]: timeit.timeit("500 in t", "t = list(range(1000))") 
Out[3]: 10.020853042602539 

In [4]: timeit.timeit("500 in t", "t = set(range(1000))") 
Out[4]: 0.1159818172454834

來源

2011-06-28 16:20:08

高效替代「in」

回答

相關問題