率直に申し上げて、私は楽しみのためにコードを書いています。これは、ここ数日間、空き時間に取り組んできたコードの課題です。課題は、スペースで区切られた一連の単語 (ドキュメント) と、リスト内のいくつかの検索用語が与えられることです。これらの検索用語が最も近い文書内の場所を見つける必要があります。基本的に、すべての searchTerm を含むドキュメントの最小のサブセットを見つけて、そのサブセットを出力します。これまでのところ、私の機能は私のシステムで機能しているようです。ただし、アップロードすると、アルゴリズムの実行に時間がかかりすぎると言われます。私の考えたプロセスは、ドキュメント内の searchTerm のすべてのインスタンスを見つけてから、それに対して itertools.product() を実行することでした。次に、それぞれをテストして、インデックス値に基づいてどれが最も短いかを判断します。これが私がこれまでに持っているものです：
def answer(document, searchTerms):
from itertools import product
#build a list of the input document
document = document.split()
index = []
#find all indexes for the searchTerms and build a list of lists
for w in searchTerms:
index.append([i for i,x in enumerate(document) if x == w])
#build iterator of all possible combinations of indexes for each of the searchTerms
combinations = product(*index)
#recover memory
del index
#build tuple of minimum distance between all search terms
shortest = min(((max(x) - min(x),x) for x in combinations),key=lambda x: x[0])
return (' '.join(document[min(shortest[1]):max(shortest[1])+1]))
マルチプロセッシングを使用してコードのセクションを高速化しようとしましたが、正しい構文が得られませんでした。例えば：
from multiprocessing import Pool
p = Pool(processes=2)
shortest = p.map(min_max,combinations)
def min_max(combinations):
return min(((max(x) - min(x),x) for x in combinations))
結果:
Traceback (most recent call last):
File "./searchTerms2.py", line 65, in <module>
print (answer(document,searchTerms))
File "./searchTerms2.py", line 45, in answer
shortest = p.map(min_max,combinations)
File "/usr/lib/python2.7/multiprocessing/pool.py", line 251, in map
return self.map_async(func, iterable, chunksize).get()
File "/usr/lib/python2.7/multiprocessing/pool.py", line 567, in get
raise self._value
TypeError: 'int' object is not iterable
任意のポインタをいただければ幸いです。この問題を攻撃するより良い方法はありますか? もっと効率的にできる分野はありますか?
--EDIT-- 問題の詳細な説明:
document = 'this is a song that never ends it goes on and on my friend some people started singing it not knowing what it was and they will continue singing it forever just because this is the song'
searchTerms = ['this', 'goes','on']
結果は次のようになります。
'this is a song that never ends it goes on'
これは私の現在のアルゴリズムでは機能しますが、はるかに大きなドキュメントと検索用語が与えられた場合、十分に速くはありません. これがより明確であることを願っています...
私は自分のコードのタイミングを計っていますが、私の最大のパフォーマンス ヒットは以下から来ているようです:
shortest = min(((max(x) - min(x),x) for x in combinations),key=lambda x: x[0])
'document' の単語数を増やし、'searchTerms' に searchTerms を追加すると、その行で大きなパフォーマンス ヒットが見られます。他のすべては、私が知ることができるものとはほとんど異なりません..