Pythonでコサイン距離を計算するための最適化された方法
https://stackoverflow.com/questions/1823293
-
22-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian質問
2つの配列間のコサイン距離を計算するメソッドを作成しました：
def cosine_distance(a, b):
if len(a) != len(b):
return False
numerator = 0
denoma = 0
denomb = 0
for i in range(len(a)):
numerator += a[i]*b[i]
denoma += abs(a[i])**2
denomb += abs(b[i])**2
result = 1 - numerator / (sqrt(denoma)*sqrt(denomb))
return result
大きなアレイでは、実行に非常に時間がかかる場合があります。より高速に実行されるこのメソッドの最適化バージョンはありますか？
更新：scipyを含むこれまでのすべての提案を試しました。マイクとスティーブからの提案を取り入れた、打ち負かすべきバージョンは次のとおりです。
def cosine_distance(a, b):
if len(a) != len(b):
raise ValueError, "a and b must be same length" #Steve
numerator = 0
denoma = 0
denomb = 0
for i in range(len(a)): #Mike's optimizations:
ai = a[i] #only calculate once
bi = b[i]
numerator += ai*bi #faster than exponent (barely)
denoma += ai*ai #strip abs() since it's squaring
denomb += bi*bi
result = 1 - numerator / (sqrt(denoma)*sqrt(denomb))
return result
解決
SciPyを使用できる場合は、 spatial.distance の cosine を使用できます。
http://docs.scipy.org/doc/scipy/reference/spatial.distance.html
SciPyを使用できない場合は、Pythonを書き直して少し高速化を試みることができます（編集：しかし、思ったようには動作しませんでした。以下を参照）。
from itertools import izip
from math import sqrt
def cosine_distance(a, b):
if len(a) != len(b):
raise ValueError, "a and b must be same length"
numerator = sum(tup[0] * tup[1] for tup in izip(a,b))
denoma = sum(avalue ** 2 for avalue in a)
denomb = sum(bvalue ** 2 for bvalue in b)
result = 1 - numerator / (sqrt(denoma)*sqrt(denomb))
return result
aとbの長さが一致しない場合は、例外を発生させることをお勧めします。
sum（）の呼び出し内でジェネレーター式を使用することにより、Python内のCコードによって実行されるほとんどの作業で値を計算できます。これは、 for ループを使用するよりも高速です。
これのタイミングを計っていないので、どれだけ速くなるか推測できません。ただし、SciPyコードはほぼ確実にCまたはC ++で記述されており、できるだけ高速である必要があります。
Pythonでバイオインフォマティクスを行っている場合は、とにかくSciPyを使用する必要があります。
編集：ダリウス・ベーコンは私のコードの時間を計り、それがより遅いことを発見しました。だから私は自分のコードの時間を計った...そう、それは遅い。すべての教訓：物事をスピードアップしようとしているときは、推測せずに測定してください。
PythonのC内部でより多くの作業を行う試みが遅い理由について私は困惑しています。長さ1000のリストで試してみましたが、それでもまだ低速でした。
Pythonを巧みにハックするのにこれ以上時間を使うことはできません。もっと高速が必要な場合は、SciPyをお試しください。
編集：timeitなしで、手作業でテストしました。短いaとbの場合、古いコードの方が速いことがわかります。長いaとbの場合、新しいコードは高速です。どちらの場合も、差は大きくありません。 （今、Windowsコンピューターでtimeitを信頼できるかどうか疑問に思っています。Linuxでこのテストを再試行します。）作業コードを変更して、高速化を試みません。そしてもう一度、SciPyを試してみることをお勧めします。 ：-）
他のヒント
（当初考えていた）C（numpyやscipyなど）にブレークアウトしたり、計算対象を変更したりせずに、速度を大幅に上げることはできません。とにかく、とにかく私がそれを試す方法は次のとおりです：
from itertools import imap
from math import sqrt
from operator import mul
def cosine_distance(a, b):
assert len(a) == len(b)
return 1 - (sum(imap(mul, a, b))
/ sqrt(sum(imap(mul, a, a))
* sum(imap(mul, b, b))))
500k要素の配列を持つPython 2.6では、約2倍の速度です。 （Jarret Hardieに従って、マップをimapに変更した後。）
元のポスターの修正されたコードの微調整バージョンは次のとおりです。
from itertools import izip
def cosine_distance(a, b):
assert len(a) == len(b)
ab_sum, a_sum, b_sum = 0, 0, 0
for ai, bi in izip(a, b):
ab_sum += ai * bi
a_sum += ai * ai
b_sum += bi * bi
return 1 - ab_sum / sqrt(a_sum * b_sum)
見苦しいが、もっと早く出てくる。 。 。
編集：そして、 Psyco を試してください！最終バージョンをさらに4倍高速化します。どうすれば忘れられますか？
a [i] および b [i] の abs（）を使用する必要はありません。 p>
a [i] および b [i] を一時変数に保存して、インデックス作成が複数回行われないようにします。
コンパイラはこれを最適化できるかもしれませんが、そうでないかもしれません。
** 2 演算子にチェックインします。乗算に単純化するのか、それとも一般的なべき関数を使用するのか（log-2で乗算-antilog）。
sqrtを2回実行しないでください（ただし、コストはわずかです）。 sqrt（denoma * denomb）を実行します。
Darius Baconの答えと同様に、私は演算子とitertoolsをいじってより速い答えを出しました。 timeitによると、500項目の配列では次のように1/3速くなります：
from math import sqrt
from itertools import imap
from operator import mul
def op_cosine(a, b):
dot_prod = sum(imap(mul, a, b))
a_veclen = sqrt(sum(i ** 2 for i in a))
b_veclen = sqrt(sum(i ** 2 for i in b))
return 1 - dot_prod / (a_veclen * b_veclen)
これは、約1000以上の要素の配列に対して高速です。
from numpy import array
def cosine_distance(a, b):
a=array(a)
b=array(b)
numerator=(a*b).sum()
denoma=(a*a).sum()
denomb=(b*b).sum()
result = 1 - numerator / sqrt(denoma*denomb)
return result
SciPy内でCコードを使用すると、長い入力配列の場合に大きなメリットがあります。シンプルで直接的なPythonを使用すると、短い入力配列が優先されます。 Darius Baconの izip（）ベースのコードは、最高のベンチマークでした。したがって、最終的な解決策は、入力配列の長さに基づいて、実行時に使用するものを決定することです。
from scipy.spatial.distance import cosine as scipy_cos_dist
from itertools import izip
from math import sqrt
def cosine_distance(a, b):
len_a = len(a)
assert len_a == len(b)
if len_a > 200: # 200 is a magic value found by benchmark
return scipy_cos_dist(a, b)
# function below is basically just Darius Bacon's code
ab_sum = a_sum = b_sum = 0
for ai, bi in izip(a, b):
ab_sum += ai * bi
a_sum += ai * ai
b_sum += bi * bi
return 1 - ab_sum / sqrt(a_sum * b_sum)
異なる長さの入力を持つ関数をテストするテストハーネスを作成しましたが、長さ200前後でSciPy関数が勝ち始めました。入力配列が大きいほど、勝ちます。非常に短い長さの配列、たとえば長さ3の場合、より単純なコードが優先されます。この関数は、わずかなオーバーヘッドを追加して、それを行う方法を決定し、最適な方法で実行します。
興味のある方のために、ここにテストハーネスを示します。
from darius2 import cosine_distance as fn_darius2
fn_darius2.__name__ = "fn_darius2"
from ult import cosine_distance as fn_ult
fn_ult.__name__ = "fn_ult"
from scipy.spatial.distance import cosine as fn_scipy
fn_scipy.__name__ = "fn_scipy"
import random
import time
lst_fn = [fn_darius2, fn_scipy, fn_ult]
def run_test(fn, lst0, lst1, test_len):
start = time.time()
for _ in xrange(test_len):
fn(lst0, lst1)
end = time.time()
return end - start
for data_len in range(50, 500, 10):
a = [random.random() for _ in xrange(data_len)]
b = [random.random() for _ in xrange(data_len)]
print "len(a) ==", len(a)
test_len = 10**3
for fn in lst_fn:
n = fn.__name__
r = fn(a, b)
t = run_test(fn, a, b, test_len)
print "%s:\t%f seconds, result %f" % (n, t, r)
def cd(a,b):
if(len(a)!=len(b)):
raise ValueError, "a and b must be the same length"
rn = range(len(a))
adb = sum([a[k]*b[k] for k in rn])
nma = sqrt(sum([a[k]*a[k] for k in rn]))
nmb = sqrt(sum([b[k]*b[k] for k in rn]))
result = 1 - adb / (nma*nmb)
return result
更新されたソリューションにはまだ2つの平方根があります。 sqrt行を次のように置き換えることにより、これを1つに減らすことができます。
result = 1-分子/ （sqrt（denoma * denomb））
乗算は通常、sqrtよりもかなり高速です。関数内で一度しか呼び出されないため、それほど多くはないように思えるかもしれませんが、多くのコサイン距離を計算しているように聞こえるので、改善は合計されます。
あなたのコードは、ベクトル最適化の機が熟しているように見えます。クロスプラットフォームのサポートが問題ではなく、さらに高速化する場合は、Cでコサイン距離コードをコーディングし、コンパイラが結果コードを積極的にベクトル化することを確認できます（Pentium IIでも浮動小数点ベクトル化が可能です） ）
