3

私はいくつかのパフォーマンスの複雑さに苦しんでいます。手元のタスクは、2 つの文字列間の類似値を抽出することです。このために私は使用していfuzzywuzzyます：

from fuzzywuzzy import fuzz

print fuzz.ratio("string one", "string two")
print fuzz.ratio("string one", "string two which is significantly different")
result1 80
result2 38

ただし、これで問題ありません。私が直面している問題は、2 つのリストがあり、1 つには 1500 行、もう 1 つには数千行あることです。最初の要素のすべての要素と 2 番目の要素のすべての要素を比較する必要があります。for ループ内の単純な for は、計算にとてつもなく長い時間がかかります。

どうすればこれをスピードアップできるか提案があれば、大歓迎です。

4

4 に答える 4

2

私はあなたのために自分で何かを作りました（python 2.7）：

from __future__ import division

import time
from itertools import izip

from fuzzywuzzy import fuzz


one = "different simliar"
two = "similar"


def compare(first, second):
    smaller, bigger = sorted([first, second], key=len)

    s_smaller= smaller.split()
    s_bigger = bigger.split()
    bigger_sets = [set(word) for word in s_bigger]

    counter = 0
    for word in s_smaller:
        if set(word) in bigger_sets:
            counter += len(word)
    if counter:
        return counter/len(' '.join(s_bigger))*100 # percentage match
    return counter


start_time = time.time()
print "match: ", compare(one, two)
compare_time = time.time() - start_time
print "compare: --- %s seconds ---" % (compare_time)
start_time = time.time()
print "match: ", fuzz.ratio(one, two)
fuzz_time = time.time() - start_time
print "fuzzy: --- %s seconds ---" % (fuzz_time)
print
print "<simliar or similar>/<length of bigger>*100%"
print 7/len(one)*100
print
print "Equals?"
print 7/len(one)*100 == compare(one, two)
print
print "Faster than fuzzy?"
print compare_time < fuzz_time

私のほうが速いと思いますが、あなたにとってはより正確ですか？あなたが決める。

EDIT Now は高速であるだけでなく、より正確です。

結果：

match:  41.1764705882
compare: --- 4.19616699219e-05 seconds ---
match:  50
fuzzy: --- 7.39097595215e-05 seconds ---

<simliar or similar>/<length of bigger>*100%
41.1764705882

Equals?
True

Faster than fuzzy?
True

もちろん、fuzzywuzzy のように単語をチェックする場合は、次のようにします。

from __future__ import division
from itertools import izip
import time

from fuzzywuzzy import fuzz


one = "different simliar"
two = "similar"


def compare(first, second):
    smaller, bigger = sorted([first, second], key=len)

    s_smaller= smaller.split()
    s_bigger = bigger.split()
    bigger_sets = [set(word) for word in s_bigger]

    counter = 0
    for word in s_smaller:
        if set(word) in bigger_sets:
            counter += 1
    if counter:
        return counter/len(s_bigger)*100 # percentage match
    return counter


start_time = time.time()
print "match: ", compare(one, two)
compare_time = time.time() - start_time
print "compare: --- %s seconds ---" % (compare_time)
start_time = time.time()
print "match: ", fuzz.ratio(one, two)
fuzz_time = time.time() - start_time
print "fuzzy: --- %s seconds ---" % (fuzz_time)
print
print "Equals?"
print fuzz.ratio(one, two) == compare(one, two)
print
print "Faster than fuzzy?"
print compare_time < fuzz_time

結果：

match:  50.0
compare: --- 7.20024108887e-05 seconds ---
match:  50
fuzzy: --- 0.000125169754028 seconds ---

Equals?
True

Faster than fuzzy?
True
于 2016-08-21T18:25:03.757 に答える
1

私が考えることができる最善の解決策は、IBM Streams フレームワークを使用して、本質的に避けられない O(n^2) ソリューションを並列化することです。

このフレームワークを使用すると、次のようなシングルスレッド カーネルを作成できます。

def matchStatements(tweet, statements):
    results = []
    for s in statements:
        r = fuzz.ratio(tweet, s)
        results.append(r)
    return results

次に、これに似たセットアップを使用して並列化します

def main():
    topo = Topology("tweet_compare")
    source = topo.source(getTweets)
    cpuCores = 4
    match = source.parallel(cpuCores).transform(matchStatements)
    end = match.end_parallel()
    end.sink(print)

これにより、処理がマルチスレッド化され、マルチスレッド化の詳細を自分で実装する作業を節約しながら、処理が大幅に高速化されます (これが Streams の主な利点です)。

アイデアは、各ツイートが複数の処理要素にわたって処理される Streams タプルであるということです。

Streams の Python トポロジ フレームワークのドキュメントはこちらで、parallel特に演算子についてはこちらで説明されています。

于 2016-08-22T14:29:42.533 に答える
1

各ステートメントが出現する回数をカウントする必要がある場合は、いいえ、各リストの要素を比較するために必要な n^2 操作を大幅に高速化する方法はありません。長さを使用して一致が発生する可能性を除外することで、一部の文字列一致を回避できる場合がありますが、まだ for ループがネストされています。おそらく、節約できる処理時間よりもはるかに多くの時間を最適化に費やすことになるでしょう。

于 2016-08-21T17:47:26.647 に答える