効率的な "in"の代替

Question

私は、クローラが取ったパスのマップを作成する最終的な目標を持つWebクローラを作成しています。他のどのクローラーがページをプルダウンするのかという手掛かりはありませんが、私の時計は約2,000ページ/分です。

クローラは、深さが15に制限されている再帰的なバックトラッキングアルゴリズムで動作します。 さらに、クローラが無限にページを再訪するのを防ぐため、訪問した各ページのURLをリストに格納し、次の候補URLのリストをチェックします。

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

この方法は、約300,000ページをプルダウンするまでに問題になるようです。この時点で、クローラは平均して毎分500ページのクロッキングを行っています。

私の質問は、効率を高めながら同じ機能を実現するもう1つの方法です。

私は、各エントリのサイズを小さくすると役立つかもしれないと思ったので、URL全体を追加する代わりに、各URLの最初の2文字と最後の文字を文字列として追加します。しかし、これは役に立たなかった。

私はセットや何かでこれを行う方法がありますか？ヘルプ

編集用

ありがとう：注意点として、私のプログラムはまだマルチスレッドではありません。私はスレッド化について学ぶ前に、このボトルネックを解決する必要があると考えました。

Answer 1

これまで見たことのあるURLにはlistの代わりにsetを使用している可能性があります。

Answer 2

代わりにURLをキーとして使用する（アクセス時間はO（1））。

しかし、セットも機能します。私は同様の問題があった

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

Answer 3

を参照してください。メモリ対時間のためのさまざまなメソッド（list/file/sets/sqlite）のプロファイリングを終わらせました。これらの2つの記事を参照してください。 最後に、sqliteが最適です。また、単純にクロールされたURLのset 『「と』クロール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

Answer 4

を減らすために、URLハッシュを使用することができます。設定を使用して（ランダムアクセス用に最適化されています辞書と同じハッシュアルゴリズムが使われています）リストの検索操作は線形検索を使用して行われるため、特に高速ではありません。検索を行う実際のコードを変更する必要はありません

これをチェックしてください

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