大きなリストに特定の文字列（Python）が含まれているかどうかを調べる最も効率的な方法

Question

英語の単語がすべて〜60k単語〜500k文字のファイルがあります。入力として受け取った特定の単語が「英語」であるかどうか（つまり、この単語がリストに含まれているかどうか）をテストします。

Pythonでこれを行う最も効率的な方法は何でしょうか？

簡単な解決策は、ファイルをリストにロードして、単語がそのリストに含まれているかどうかを確認することです。リストをソートすることができますが、これは複雑さをO（logn）に縮小します。しかし、私はPythonがどのようにリストを検索しているのか、そのような大きなリストがメモリにあればパフォーマンスのペナルティがあるかどうかはわかりません。私は言葉の長さに上限を置くことができるという事実を「乱用することはできますか？ （たとえば、最長の長さは15文字です）。

多くのメモリを搭載したマシン上でアプリケーションを実行していますので、スピードとCPU使用率よりもメモリ消費量が少なくて済みます。

おかげ

Answer 1

python Setはお試しください。

setオブジェクトは、別個のハッシュ可能オブジェクトの順序付けられていないコレクションです。一般的な用途には、メンバーシップテスト、シーケンスから重複を削除し、交差、結合、差異、対称差などの数学演算を計算することが含まれます。

Answer 2

あなたは基本的にメンバーは、右のセットであるかどうかをテストしていますか？

もしそうなら、あなたはたくさんのメモリを持っていると言われているので、すべての単語をmemcacheのキーとしてロードし、すべての単語に対してmemcacheに存在するかどうかを確認してください。

または、コマンド名をオートコンプリートするためにbashによって使用されるデータ構造を使用します。これは高速かつ効率的で、メモリ内では（名前を覚えていません）。

Answer 3

Trie構造はあなたの目的に合っています。間違いなくそこにあるPythonの実装が見つかるはずです...

Answer 4

メモリ消費は問題ではなく、言葉も変わらない場合は、これを実行する最速の方法はすべてをハッシュに入れてその方法で検索することです。 Pythonでは、これはSetです。あなたは一定時間の検索をします。

Answer 5

500k文字は大きなリストではありません。リスト内の項目が一意で、この検索を繰り返し実行する必要がある場合は、setを使用すると、最適なケースでは複雑さがO(1)に低下します。

Answer 6

サンプルPythonコード：

L = ['foo', 'bar', 'baz'] # Your list 
s = set(L) # Converted to Set 

print 'foo' in s # True 
print 'blah' in s # False 

Answer 7

2つのこと：あなたが右から行くことができるよう

ザ・Pythonの可変セット」タイプは、 '追加' 方法（s.add（アイテム））がありますあなたの大きなファイルから中間データ構造としてリストを使用せずにセットにまっすぐ（ライン）を読み込みます。

Pythonでは、データ構造を「pickle」することができるので、大きなセットをファイルに保存して、セットを再初期化する時間を節約することができます。

第二に、私は自分の娯楽のために英語のすべての一音節の単語のリストを探していましたが、私が述べたものは専有的なようです。それが介入していない場合、私はあなたの英語の単語のリストが他の人によって取得できるかどうか尋ねることができますか？

Answer 8

リストをセットに変換すると、リストをソートしてバイナリ検索を行うように、データに対してこのような種類のクエリを繰り返し実行した場合にのみ役立ちます。あなたは一度だけリストからデータを取得しようとしている場合は、昔ながらの線形検索が最善の策である：

if 'foo' in some_list: 
    do_something() 

そうでない場合は、あなたの最善の策は言及されているようにセットまたはバイナリのどちらかを使用することですサーチ。どちらを選択するかは、データの量とスペアメモリの量によって大きく異なります。私は、本当に大きなリストはハッシュからより多くの利益を得る傾向があると言われていますが、取り込まれるメモリの量は非常に高価になる可能性があります。

最後に、3番目のオプションは、データをsqliteデータベースにインポートし、そこから直接読み取ることです。 Sqliteは非常に高速で、全体のリストをファイルからロードする手間を省くことができます。 Pythonには非常に良い組み込みのsqlite libraryがあります。

Answer 9

他の人がset（）を使用してメモリ内の方法を指定していますが、これは一般的に最速の方法であるため、60kワードのデータセット（最大で数MBB）のメモリには税金をかけてはいけません。

f=open('words.txt') 
s = set(word.strip() for word in f) 

ただし、セットをメモリにロードするのに時間がかかることがあります。たくさんの言葉をチェックしている場合、これは問題ありません。検索時間はそれを補うものではありません。しかし、コマンド実行ごとに1つの単語しかチェックしない場合（例えば、これは "checkenglish [word]"のようなコマンドラインアプリです）、起動時間はファイルラインを検索するよりも長くなります行ごとに

これがあなたの状況である場合や、より大きなデータセットを使用している場合は、ディスク上のフォーマットを使用する方が良い場合があります。最も簡単な方法は、dbmモジュールを使用することです。次に、あなたのプログラムがでメンバーシップを確認することができます

import dbm 
f=open('wordlist.txt') 
db = dbm.open('words.db','c') 
for word in f: 
    db[word] = '1' 
f.close() 
db.close() 

：：でワードリストから、このようなデータベースを作成します

db = dbm.open('words.db','r') 
if db.has_key(word): 
    print "%s is english" % word 
else: 
    print "%s is not english" % word 

これは、ディスクへのアクセスがあるでしょうから、設定した検索よりも遅くなりますが、になります検索より速く、メモリ使用量が少なく、初期化時間が大幅に短縮されます。

SQLデータベース（例：sqlite）の使用など、他の選択肢もあります。