Efficent検索

Question

私は（10K項目を持つ）リストlstとクエリ用語qを持っている、と私はlstの任意の項目をqで終わる場合見つけたいと思います。私は1に設定された基準タイマー、このステートメントとして

：

x = q in lst 

私はこれらを試してみました。これらの結果（xタイマーに対してタイミング）で

# obvious endswith method 
y = [k for k in lst if k.endswith(q)] 
# find method 
z = [k for k in lst if k.find(q, len(k)-len(q))] 
# regex 
v = [k for k in lst if re.search(q + '$', k)] 
# regex without list comprehension 
w = re.search(q + '~', '~'.join(lst) + '~') 

を：

x: 1 
y: 650 
z: 1209 
v: 7160 
w: 241 

良い実装がされていない限り、私はregexと参加リストに行くことができると思います。

現実世界では、実行時に複数回ヒットしたコードブロックを最適化しようとしていますが、.endswithメソッドのリストの理解はボトルネックです。

Answer 1

私は正規表現が行く方法だとは思わない。 joined = '~'.join(lst) + '~'をループ外に割り当てても、q+'~' in joinedは、re.search(q + '~', joined)（0.00093秒vs 0.0034秒）を上回ります。

ただし、結合された文字列をまだ持っていないと仮定すると、それを必要としない方法は高速になる可能性があります。ジェネレータは、必要なときにのみ値を生成するので便利です（リストの残りの部分をチェックするのではなく、あなたのアイテムの最後にクエリを見つけると停止することができます）。

これは私のための最速だった：any(k for k in lst if k.endswith(q))

マイコード：

import timeit 

setup = ''' 

import string 
import random 
import re 

lst = [] 
for i in range(10000): 
    lst.append(random.choice(string.letters)+random.choice(string.letters)+random.choice(string.letters)+random.choice(string.letters)) 

q = 'ab' 

''' 

print "reference: " 
print round(min(timeit.Timer("q in lst", setup=setup).repeat(7,500)),5) 
# 0.05435 

print "\nreference with joined string: " 
print round(min(timeit.Timer("q+'~' in '~'.join(lst) + '~'", setup=setup).repeat(7,500)),5) 
# 0.05462 

print "\nendswith, with list approach: " 
print round(min(timeit.Timer("any([k for k in lst if k.endswith(q)])", setup=setup).repeat(7,500)),5) 
# 0.62998 

print "\nfind method: " 
print round(min(timeit.Timer("[k for k in lst if k.find(q, len(k)-len(q))]", setup=setup).repeat(7,500)),5) 
# 1.22274 

print "\nregex: " 
print round(min(timeit.Timer("[k for k in lst if re.search(q + '$', k)]", setup=setup).repeat(7,500)),5) 
# 3.73494 

print "\nregex without list comprehension: " 
print round(min(timeit.Timer("re.search(q + '~', '~'.join(lst) + '~')", setup=setup).repeat(7,500)),5) 
# 0.05435 

print "\nendswith, with generator approach: " 
print round(min(timeit.Timer("any((k for k in lst if k.endswith(q)))", setup=setup).repeat(7,500)),5) 
# 0.02052