アルゴリズムの遅さは主に、len(db[2]) 回反復する外部ループ内に含まれる len(db[2]) 回反復する内部ループがあるという事実に起因します。これは、内部コードが len(db[2])^2 回実行されていることを意味します。ファイルが大きく、たとえば 5000 語を解析している場合、コードは 5000^2 = 25,000,000 回実行されます!
したがって、問題を解決するための攻撃の角度は、その内部ループのコストを排除または大幅に削減する方法を見つけることです。以下は、 len(db[2]) を 1 回だけ反復する必要があるソリューションの例です。次に、はるかに小さな項目セットを反復する 2 番目の別のループを実行します。2 番目の反復内にいくつかの内部ループがありますが、それらの実行回数はさらに少なく、コストはほとんど取るに足らないものです。
約 48kb のテキスト ファイルを使用して、あなたのアルゴリズムと私のアルゴリズムの時間を計りました。あなたのアルゴリズムは私のコンピューターで平均約 14 秒、私のアルゴリズムは平均 0.6 秒でした。したがって、その内側のループを取り除くことで、アルゴリズムは 23 倍以上高速になりました。また、比較をテキストではなく数値間で行うように変更したり、append() の使用を避けるためにストレージ配列を最初からフルサイズで作成したりするなど、その他の小さな最適化もいくつか行いました。Append() を使用すると、インタープリターは必要に応じて配列のサイズを動的に増やしますが、これは遅くなります。
from collections import defaultdict
# Create zero-filled sim1, sim2, sim3 arrays to avoid append() overhead
len_ = len(db[2]) - 2
for _ in range(3):
db.append([0] * len_)
# Create dictionary, containing d['word'] = [count, [indexes]]
# Do just one full iteration, and make good use of it by calculating
# sim1 (as 'count') and storing an array of number indexes for each word,
# allowing for a very efficient loop coming up...
d = defaultdict(lambda: [0, []])
for index, word in enumerate(db[2]):
if index < len_:
# Accumulate sim1
d[word][0] += 1
# Store all db[2] indexes where this word exists
d[word][1].append(index)
# Now loop only through words which occur more than once (smaller loop)
for word, (count, indexes) in d.iteritems():
if count > 1:
# Place the sim1 values into the db[3] array
for i in indexes:
if i < len_:
db[3][i] = count - 1
# Look for sim2 matches by using index numbers
next_word = db[2][i+1]
for next_word_index in d[next_word][1]:
if next_word_index - 1 != i and next_word_index - 1 in indexes:
# Accumulate sim2 value in db[4]
db[4][i] += 1
# Look for sim3 matches
third_word = db[2][i+2]
if third_word == db[2][next_word_index + 1]:
# Accumulate sim3 value in db[5]
db[5][i] += 1