0

〜800kbの単語と、各行の「値の単語」としてフォーマットされ、単語でソートされたスコア値を含む巨大な.txt.gzファイルがあります。与えられた単語の値を検索する最速の方法は何ですか?

次を使用してファイルを読み取ることができます。

import gzip

f = gzip.open('somefile.txt.gz', 'rb')
file_content = f.read()

最も速い方法は、ある種の二分探索でしょうか?

サンプルデータ：

0.090909 chevre#n#1

0.058824 シェブロン#n#1

0.071429 シェブロン#n#2

0.071429 シェブロテイン#n#1

0.166667 チェワ#n#1

4

1 に答える 1

1

二分探索はこのようなことを行う効果的な方法ですが、それでもデータをテキスト (結局は単なるバイトの集まり) からリストなどの他のデータ構造に移動する必要があります。寿命が短い、または長期的なメモリ制限のないプログラムがある場合は、(おそらく)dict起動時 (または適切なとき)にすべてを Python にロードするだけでさらに高速になります。

# This may not work exactly right for your file format, but you get the idea.
lookup = {}
for line in f:
    if line:
        value, key = line.trim().split():
        lookup[key] = value

次に、Python の組み込み辞書を使用してアクセスします。これは素晴らしく高速です。

def get_value(word):
    return lookup.get(word)

編集

単語ごとにファイル全体を読み込むことが唯一の選択肢であり、多くの単語を検索している場合、巧妙な検索アルゴリズムを実装することで節約できる時間は、ファイルを開いて開くのに費やす時間と比較して、おそらくわずかです。ファイルを何度も読み込んでいます。本当に欲しいのは、この種のことを実際にすばやく処理できるデータベースです。とはいえ、これらのパラメーターが与えられた場合、ファイルシステムを使用する必要がある場合は、おそらく次のようにします。

import bisect

# Define searchable (word, value) tuples for every word in the file.
# I'm assuming your files are sorted, but if not, sort this list (SLOW!!)
words = [(w[1], w[0]) for w in (line.strip().split() for line in f if line)]

# Binary search for the word and return its associated value.
def get_value(word):
    idx = bisect.bisect_left(words, (word,None)) # Tuples compare element-wise
    if idx != len(words) and words[idx][0] == word:
        return words[idx][1]
    raise ValueError('word not found')

最後に、gzip 圧縮されたファイルを使用していることに気付きました。これは、ストレージ容量が問題である場合には賢明ですが、プロセスがさらに遅くなります。もう一度、データベースを提案する必要があります。いずれにせよ、あなたがここで問題を抱えているかどうかはわかりませんが、念のため、gzip で圧縮されたファイルを読み取ることは、通常のファイルを読み取ることよりも「難しく」ありません。gzip モジュールを見てください。基本的に、gzip ファイルは通常のファイルと同じように機能するため、引き続き書き込みfor line in fileなどを行うことができます。

于 2013-05-14T23:12:39.393 に答える