6

文字列 (のような単語) のリストがあり、テキストを解析しているときに、単語が現在のリストの単語のグループに属しているかどうかを確認する必要があります。

ただし、私の入力はかなり大きく (約 6 億行)、要素がリストに属しているかどうかを確認することは、Python のドキュメントによると O(n) 操作です。

私のコードは次のようなものです：

words_in_line = []
for word in line:
    if word in my_list:
        words_in_line.append(word)

時間がかかりすぎるので（実際には数日）、最も時間がかかっている部分を改善したいと考えました。Python コレクション、より正確には deque について調べました。ただし、リストの途中ではなく、リストの先頭と末尾への O(1) 操作時間アクセスのみを提供します。

誰かがそれをより良い方法で行う方法についてアイデアを持っていますか?

4

4 に答える 4

19

トライ、DAWG、またはデータベースを検討することもできます。同じものの Python 実装がいくつかあります。

セットとリストの相対的なタイミングを次に示します。

import timeit
import random

with open('/usr/share/dict/words','r') as di:  # UNIX 250k unique word list 
    all_words_set={line.strip() for line in di}

all_words_list=list(all_words_set)    # slightly faster if this list is sorted...      

test_list=[random.choice(all_words_list) for i in range(10000)] 
test_set=set(test_list)

def set_f():
    count = 0
    for word in test_set:
        if word in all_words_set: 
           count+=1
    return count

def list_f():
    count = 0
    for word in test_list:
        if word in all_words_list: 
           count+=1
    return count

def mix_f():
    # use list for source, set for membership testing
    count = 0
    for word in test_list:
        if word in all_words_set: 
           count+=1
    return count    

print "list:", timeit.Timer(list_f).timeit(1),"secs"
print "set:", timeit.Timer(set_f).timeit(1),"secs" 
print "mixed:", timeit.Timer(mix_f).timeit(1),"secs"

版画:

list: 47.4126560688 secs
set: 0.00277495384216 secs
mixed: 0.00166988372803 secs

つまり、10000 語のセットを 250,000 語のセットと照合すると、同じ 250,000 語のリスト内の同じ 10000 語のリストを照合するよりも17,085 倍高速です。ソースにリストを使用し、メンバーシップ テストにセットを使用すると、並べ替えられていないリストのみを使用するよりも28,392 倍高速です。

メンバーシップ テストの場合、リストは O(n) であり、セットとディクテーションはルックアップの O(1) です。

結論: 6 億行のテキストには、より適切なデータ構造を使用してください。

于 2012-06-08T00:18:14.853 に答える
1

最初にリストを選択した理由はよくわかりませんが、いくつかの代替案を次に示します。

set() を使用することは、おそらく良い考えです。これは非常に高速ですが、順序付けされていませんが、まさに必要な場合もあります。

順序付けが必要で、任意のルックアップも必要な場合は、ある種のツリーを使用できます: http://stromberg.dnsalias.org/~strombrg/python-tree-and-heap-comparison/

あちこちで少数の誤検知を伴うセット メンバーシップ テストが許容される場合は、ブルーム フィルターをチェックインできます: http://stromberg.dnsalias.org/~strombrg/drs-bloom-filter/

あなたが何をしているかによっては、トライも非常に良いかもしれません。

于 2012-06-08T00:58:01.853 に答える
0

これはリスト内包表記を使用します

words_in_line = [word for word in line if word in my_list]

これはあなたが投稿したコードよりも効率的ですが、あなたの巨大なデータセットがどれだけ多いかを知るのは難しいです。

于 2012-06-08T00:02:35.313 に答える
0

ここでできる改善点は 2 つあります。

  • ハッシュテーブルを使用して単語リストをバックアップします。これにより、単語リストに単語が存在するかどうかを確認するときに、O(1) のパフォーマンスが得られます。これを行うにはいくつかの方法があります。このシナリオに最も適しているのは、リストをセットに変換することです。
  • 一致する単語のコレクションにより適切な構造を使用します。
    • すべての一致を同時にメモリに保存する必要がある場合は、dequeueリストよりも追加のパフォーマンスが優れている を使用します。
    • メモリ内のすべての一致を一度に必要としない場合は、ジェネレーターの使用を検討してください。ジェネレーターは、指定したロジックに従って一致する値を反復処理するために使用されますが、一度に結果のリストの一部のみをメモリに格納します。I/O ボトルネックが発生している場合は、パフォーマンスが向上する可能性があります。

以下は、私の提案に基づいた実装例です (これらすべての単語を一度にメモリに格納する必要があるとは思えないため、ジェネレーターを選択しています)。

from itertools import chain
d = set(['a','b','c']) # Load our dictionary
f = open('c:\\input.txt','r')
# Build a generator to get the words in the file
all_words_generator = chain.from_iterable(line.split() for line in f)
# Build a generator to filter out the non-dictionary words
matching_words_generator = (word for word in all_words_generator if word in d)
for matched_word in matching_words_generator:
    # Do something with matched_word
    print matched_word
# We're reading the file during the above loop, so don't close it too early
f.close()

入力.txt

a b dog cat
c dog poop
maybe b cat
dog

出力

a
b
c
b
于 2012-06-08T00:47:15.027 に答える