0

いくつかのコンテンツを含むテキストファイルがあります。このコンテンツを頻繁に検索する必要があります。次の2つのオプションがありますが、どちらが最適ですか（実行速度が速いため）？

方法1：

def search_list(search_string):
    if search_word in li:
        print "found at line ",li.indexOf(search_word)+1

if __name__="__main__":
    f=open("input.txt","r")
    li=[]
    for i in f.readlines():
        li.append(i.rstrip("\n"))
    search_list("appendix")

方法2：

def search_dict(search_string):
    if d.has_key(search_word):
        print "found at line ",d[search_word]

if __name__="__main__":
    f=open("input.txt","r")
    d={}
    for i,j in zip(range(1,len(f.readlines())),f.readlines()):
        d[j.rstrip("\n")]=i
    search_dict("appendix")
4

5 に答える 5

2

本当に頻繁に行う場合は、2番目の方法の方が高速です（インデックスのようなものを作成しました）。

少しだけ適応させてください。

def search_dict(d, search_string):
    line = d.get(search_string)
    if line:
        print "found at line {}".format(line)
    else:
        print "string not found"

d = {}
with open("input.txt", "r") as f:
    for i, word in enumerate(f.readlines(), 1):
        d[word.rstrip()] = i
search_dict(d, "appendix")
于 2012-09-17T12:14:28.960 に答える
2

キーがハッシュされ、O(1) 操作で検索されるため、頻繁に検索する場合は、辞書の方が確実に優れています (行番号も格納するのに十分なメモリがある場合)。ただし、実装は機能しません。1 つ目f.readlines()はファイル オブジェクトを使い果たし、2 つ目では何も読み取れませんf.readlines()。

あなたが探しているのはenumerate：

with open('data') as f:
    d = dict((j[:-1],i) for i,j in enumerate(f,1))

また、どちらの場合も、検索を行う関数は、探しtry/exceptているインデックスが通常見つかった場合に使用すると高速になることにも注意してください。in(最初のケースでは、注文N操作であり、リストの操作であるため、とにかく高速になる可能性があり.indexます)。

例えば：

def search_dict(d, search_string):
    try:
        print "found at line {0}".format(d[search_string])
    except KeyError:
        print "string not found"

またはリストの場合：

def search_list(search_string):
    try:
        print "found at line {0}".format(li.indexOf(search_word)+1)
    except ValueError:
        print "string not found"
于 2012-09-17T12:16:56.613 に答える
1

eumiro と mgilson の回答を読んだ後、これを投稿しています。

コマンド ラインで 2 つの方法を比較すると、最初の方法の方が高速であることがわかると思います。2番目の方法の方が高速であるという他の回答もありますが、それらは、インデックスを作成した後にファイルに対して複数の検索を行うという前提に基づいています。コマンドラインからそのまま使用する場合は、そうではありません。

インデックスの構築は、文字列を直接検索するよりも時間がかかりますが、インデックスを構築すると、検索を非常に迅速に実行できるため、構築に費やされた時間を補うことができます。プログラムが完了すると、インデックスは破棄され、次の実行時に再構築する必要があるため、この余分な時間が無駄になります。これがうまくいくようにするには、作成されたインデックスをクエリ間でメモリに保持する必要があります。

これにはいくつかの方法があります。1 つは、インデックスを保持するデーモンを作成し、フロントエンド スクリプトを使用してクエリを実行する方法です。Googleなどで検索するpython daemon client communicationと、これを実装するためのヒントが得られます。ここに 1 つの方法があります。

于 2012-09-17T12:31:16.853 に答える
0

スローインする別のオプションは、SQLite3によって提供されるFTSを使用することです...（テストされておらず、単語の部分文字列などではなく、単語全体を探していると仮定します）

import sqlite3

# create db and table
db = sqlite3.connect(':memory:') # replace with file on-disk?
db.execute('create virtual table somedata using fts4(line)')

# insert the data
with open('yourfile.txt') as fin:
    for lineno, line in enumerate(fin):
        # You could put in a check here I guess...
        if somestring in line:
            print lineo # or whatever....
        # put row into FTS table
        db.execute('insert into somedata (line) values (?)', (line,))
    # or possibly more efficient
    db.executemany('insert into somedata (line) values (?)', fin)
db.commit()

look_for = 'somestring'
matches = db.execute('select rowid from somedata where line match ?', (look_for,) )
print '{} is on lines: {}'.format(look_for, ', '.join(match[0] for match in matches))

最初の行だけが必要な場合limit 1は、クエリの最後に追加します。

また、を使用mmapしてファイルをマップし、.findメソッドを使用して文字列の最も早いオフセットを取得し、それが-1見つからないと仮定して（つまり、123456としましょう）、mapped_file [：123456] .count（ ' \ n'）+1で行番号を取得します。

于 2012-09-17T12:51:04.567 に答える
0

最初のものは O(n) です。2 つ目は O(1) ですが、キーを検索する必要があります。私なら2番目を選びます。

ドキュメント内のアドホック検索の場合、どちらも機能しません。そのためには、Lucene などを使用して解析し、インデックスを作成する必要があります。

于 2012-09-17T12:17:22.167 に答える