1

率直に申し上げて、私は楽しみのためにコードを書いています。これは、ここ数日間、空き時間に取り組んできたコードの課題です。課題は、スペースで区切られた一連の単語 (ドキュメント) と、リスト内のいくつかの検索用語が与えられることです。これらの検索用語が最も近い文書内の場所を見つける必要があります。基本的に、すべての 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 を追加すると、その行で大きなパフォーマンス ヒットが見られます。他のすべては、私が知ることができるものとはほとんど異なりません..

4

2 に答える 2

1

私はこの問題について 1 日考えてきましたが、かなり興味深いと思います。「ドキュメント」を線と考え、各「単語」を線上の点と考えると役立ちます。次に、任意のソリューションは、この行の一部を左側 ( start ) と右側 ( end ) でカバーするウィンドウ/範囲です。

試行された解決策: Mad Physicist の解決策が機能しない理由は、この線上の点から開始し、この点と他のすべての点の間の距離が実際には多くのオーバーラップを含む場合に直交として扱うためです。一致する各検索語の最も近いポイントのみを選択するため、検索されるソリューション スペースが制限され、一部のソリューションが見落とされます。次のような例を見つけるのは難しくありません。

document = 'a x x d x x x a j x x'
searchTerms = 'a d j'.split()

で開始しd、最も近い を選択します。aさらにaすると、全体的なソリューションが短くなります。

ブルートフォースソリューション: 質問のソリューションは、product可能なソリューションを生成し、それぞれをチェックするために使用されます。これは問題なく、投稿した例のような小さな問題では実際にはかなり高速ですが、ドキュメントの長さが長くなり、特に検索用語の数が増えると、からの組み合わせの数productが急速に増えます。

新しい解決策: 最初にできることは、最小インデックスと最大インデックスの間にすべてのポイントが含まれていない組み合わせは無効であることを認識することです。これにより、多くの組み合わせが排除され、検索語の数に関係なく、 ( startend ) ポイントの組み合わせのみを効果的に選択できるようになります。

これらの組み合わせを生成するための凝った数式があるかもしれませんが、私は別のアプローチを取りました...

各検索語のインデックスを個別に最小インデックスから最大インデックスまでのミニ ウィンドウと見なす場合、ソリューションの終了インデックスの下限がこれらすべての範囲の最大開始インデックスであることは明らかです。これは、終了インデックスが小さいウィンドウにはこの検索語が含まれないためです。開始インデックスの下限は、単純に最低一致インデックスです。

これ ( start , end ) は解でなければならないので、最初の推測として使用し、次の手順に従います。

一致するすべてのインデックスのフラット リストを作成し、このリストで作業すると役立ちます。他のすべてのインデックスは無関係であるためです。この場合start = 0.

開始インデックスを次の一致インデックス (start++フラット リスト) に進めます。これにより、一番左の一致がウィンドウからポップされます。startより小さくないその一致の次のインデックスを取得します。このインデックスがすでに範囲内にある場合は、冗長な一致を減らし、別の解決策を用意しています。このインデックスが右側の範囲外にある場合は、endを移動して範囲を拡張し、この一致を再度含めます。この一致がこれ以上ない場合は、ソリューションが不足しています。

解がなくなるまでこのプロセスを繰り返し、どの解が最も短い を生成するかを追跡します。これが最終的な解決策です。 range = end - start

テスト:

テストにもう少し多様性を持たせ、私のソリューションが元のソリューションと同じソリューションを生成していることを確認するために、次のk検索語句をランダムに取得しますdocument

import random
terms = random.sample(document.split(), random.randint(3,5))
print(terms)
s1 = answer_product(document, terms)
s2 = answer_window(document, terms)

assert s1 == s2

そして、私が使用した簡単なベンチマークを試してみました:

import timeit
N = 1000
for j in xrange(2,8):
    terms = random.sample(document.split(), j)
    print(N,j)
    print('window: %s s'%timeit.timeit(lambda: answer_window(document*4, terms), number=N))
    print('product: %s s'%timeit.timeit(lambda: answer_product(document*4, terms), number=N))

私のコンピューターでは、 の小さなケースの場合、N=1000,k=2両方とも で非常に高速t~=0.03sです。ただし、 が にk成長するにつれて、がまでに達するまでの時間は 静止です。テスト用の実際の「ドキュメント」がないため、検索の量を増やすために例を 4 倍しただけです。k=7answer_productt>20sanswer_windowt~=0.03s

╔═════╦═══╦═══════════════════╦════════════════════╦═══════╗ ║ N ║ k ║ answer_window (s) ║ answer_product (s) ║ p/w ║ ╠═════╬═══╬═══════════════════╬════════════════════╬═══════╣ ║ 1e3 ║ 2 ║ 0.0231 ║ 0.0347 ║ 1.5 ║ ║ 1e3 ║ 3 ║ 0.0227 ║ 0.058 ║ 2.55 ║ ║ 1e3 ║ 4 ║ 0.025 ║ 0.242 ║ 9.68 ║ ║ 1e3 ║ 5 ║ 0.0326 ║ 3.044 ║ 93.4 ║ ║ 1e3 ║ 6 ║ 0.035 ║ 11.55 ║ 330 ║ ║ 1e3 ║ 7 ║ 0.0299 ║ 23.82 ║ 797 ║ ║ 1e5 ║ 2 ║ 2.2 ║ 2.524 ║ 1.15 ║ ║ 1e5 ║ 3 ║ 2.195 ║ 2.743 ║ 1.25 ║ ║ 1e5 ║ 4 ║ 3.272 ║ 46.51 ║ 14.2 ║ ║ 1e5 ║ 5 ║ 3.74 ║ 67.71 ║ 18.1 ║ ║ 1e5 ║ 6 ║ 3.52 ║ 1137 ║ 323 ║ ║ 1e5 ║ 7 ║ 3.98 ║ 4519 ║ 1135 ║ ╚═════╩═══╩═══════════════════╩════════════════════╩═══════╝

コード:

def answer_window(doc, terms):
    doc = doc.split()
    # create a grouping of indices by match and a flat array of all match
    # indices
    index = {w:[] for w in terms}
    indices = []
    j = 0
    for (i, w) in enumerate(doc):
        if w in index:
            # save real doc indices in flat array and use indices into that
            # array to simplify stepping.  both are automatically ordered
            indices.append(i)
            index[w].append(j)
            j += 1
    # find the maximum leftmost match index.  this is the lower bound on the
    # right side of the solution window
    highest_min = max(v[0] for v in index.values())

    # start with lowest minimum index (first) and highest minimum index (which
    # is the lower bound on the right side). this must be a solution.
    # then look for a shorter one by stepping the left side, replacing lost
    # matches from the right (expanding when necessary) until the left cannot
    # be advanced anymore.  this will cover all possible solution windows and the
    # one with the shortest length is saved
    start, end = 0, highest_min
    sol = start, end
    dsol = indices[sol[1]]-indices[sol[0]]
    while True:
        # pop leftmost match
        pop = doc[indices[start]]
        start += 1
        # need to make sure we still have the match we popped in the range
        for j in index[pop]:
            if j >= start:
                # another copy to the right!
                if j > end:
                    # must expand end to include the replacement
                    end = j
                    if indices[end]-indices[start] < dsol:
                        # new window is shorter than sol
                        sol = start, end
                        dsol = indices[sol[1]]-indices[sol[0]]
                elif indices[end]-indices[start] < dsol:
                    # the replacement is already inside the range, and moving
                    # the left side made the window smaller than sol
                    sol = start,end
                    dsol = indices[sol[1]]-indices[sol[0]]
                break # done with this pop
            else:
                # this match is left of our window
                pass
        else:
            # found no replacement, can't shrink left side anymore so we are
            # out of solutions
            break
    return (' '.join(doc[indices[sol[0]]:indices[sol[1]]+1]))
于 2016-03-09T22:33:07.287 に答える
0

コードの速度低下の主な原因は、異なる単語間のインデックスのすべての組み合わせを探すことです。明らかに、これらの組み合わせのほとんどは、最短実行の対象となることはほとんどありません。これは、少し高速に実行されるアルゴリズムの 1 つです。

  1. 検索語で区切られたすべての検索語のインデックスを検索します(あなたがやっているように)
  2. 一致数が最も少ない用語をベースとして使用します。
  3. 基本用語が出現するたびに、他のすべての用語の中で最も近いものを見つけます (これは、すべての組み合わせの距離を計算するよりもはるかに高速であることに注意してください)。最近傍の最大広がりは、候補ランの長さです。
  4. 最短の候補ランを見つけて返します。

このバージョンでは、辞書内包表記とkeyto パラメーターを使用しますmin。ただし、__builtins__モジュールの外では何も使用しません。以下のコードは、Python 2.7 および 3.5 で実行されます。

def answer(document, searchTerms):
    #build a list of the input document
    document = document.split()

    # construct list of indices of occurrences for each term
    indices = {w: [i for i,x in enumerate(document) if x == w] for w in searchTerms}

    # find the least frequent term and isolate it
    leastFrequent = min(indices.keys(), key=lambda x: len(indices[x]))
    loopIndex = indices[leastFrequent]
    del indices[leastFrequent]

    # for each element of leastFrequent, compute the nearest distance to each other item
    candidates = [None] * len(loopIndex)
    for index, element in enumerate(loopIndex):
        neighbors = [None] * len(indices)

        # find the distance to the nearest neighbor in each other list
        for ind, term in enumerate(indices):
            neighbors[ind] = min(indices[term], key=lambda x, e=element: abs(x - e))

        # the run length is the maximum of the maximum and element minus the minimum of the minimum and element
        start = min(min(neighbors), element)
        end = max(max(neighbors), element) + 1
        length = end - start
        candidates[index] = length, start, end

    # get the shortest candidate segment
    winner = min(candidates, key=lambda x: x[0])
    return ' '.join(document[winner[1]:winner[2]])

それぞれ (幾何学的) 平均回数sで発生する検索用語がある場合、このアルゴリズムはおよその時間で実行されます。の要因は、ループ オーバーとその内部への呼び出しに由来します。の因数は、 のループから得られます。最も頻度の低い要素をベースにすることで、用語の 1 つを大幅に削減しています。特に、用語の 1 つが 1 回だけ出現する場合、すべての可能な組み合わせであることが保証されているため、外側のループは 1 回だけ実行されます。kO(k * s * k) = O(s * k^2)kelementminktermk

比較のために、実装では を使用します。これは、ネストされたループitertools.productを生成し、それぞれが反復のために実行されます。これにより、ほぼランタイムになります。skO(k^s)

于 2016-03-07T17:49:45.850 に答える