파이썬에서 코사인 거리를 계산하기위한 최적화 된 방법
https://stackoverflow.com/questions/1823293
-
22-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian문제
두 배열 사이의 코사인 거리를 계산하는 방법을 썼습니다.
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를 포함하여 현재까지 모든 제안을 시도했습니다. Mike와 Steve의 제안을 통합하여 이길 버전은 다음과 같습니다.
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를 사용할 수 있다면 사용할 수 있습니다 cosine ~에서 spatial.distance:
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 코드에서 수행되는 대부분의 작업으로 값을 계산할 수 있습니다. 이것은 a를 사용하는 것보다 빠르야합니다 for 고리.
나는 이것을 시간을 정하지 않았으므로 얼마나 빠른지 추측 할 수 없습니다. 그러나 Scipy 코드는 거의 C 또는 C ++로 작성되었으며 가능한 한 빨리 적어야합니다.
파이썬에서 생물 정보학을하고 있다면 어쨌든 scipy를 사용해야합니다.
편집 : 다리우스 베이컨은 내 코드를 시간에 타이어 느린다는 것을 알았습니다. 그래서 나는 내 코드를 시간에 시간을 보냈다. 예, 느린다. 모두를위한 교훈 : 속도를 높이려고 할 때 추측하지 말고 측정하십시오.
Python의 C 내부에 더 많은 작업을 시도하려는 시도가 속도가 느려진 이유에 대해 당황했습니다. 나는 길이 1000 목록을 시도했지만 여전히 느 렸습니다.
파이썬을 영리하게 해킹하려고 더 이상 시간을 보낼 수 없습니다. 더 빠른 속도가 필요하면 Scipy를 시도하는 것이 좋습니다.
편집 : 시간이없이 손으로 테스트했습니다. 짧은 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에서 대략 두 배 빠릅니다. (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로 속도를 높입니다. 어떻게 잊을 수 있습니까?
가져갈 필요가 없습니다 abs() 의 a[i] 그리고 b[i] 당신이 그것을 제곱한다면.
가게 a[i] 그리고 b[i] 임시 변수에서 인덱싱을 두 번 이상 피하기 위해. 컴파일러는 이것을 최적화 할 수 있지만 아마도 그렇지 않을 수도 있습니다.
체크인 **2 운영자. 곱하기로 단순화합니까, 아니면 일반 전력 함수 (로그 - 곱하기 2- antilog)를 사용하고 있습니까?
SQRT를 두 번하지 마십시오 (비용은 작지만). 하다 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 코드를 사용하면 긴 입력 배열에서 큰 승리를 거두었습니다. 간단하고 직접 파이썬을 사용하여 짧은 입력 배열에 승리합니다. 다리우스 베이컨 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
업데이트 된 솔루션에는 여전히 두 개의 정사각형 뿌리가 있습니다. SQRT 라인을 다음과 같이 대체하여 이것을 하나로 줄일 수 있습니다.
결과 = 1- 분자 / (sqrt (denoma*dellomb))
곱하기는 일반적으로 SQRT보다 훨씬 빠릅니다. 함수에서 한 번만 호출되는 것처럼 보이지는 않지만 많은 코사인 거리를 계산하는 것처럼 들리므로 개선이 더해집니다.
코드는 벡터 최적화에 익숙 해야하는 것처럼 보입니다. 따라서 Cross-PlatoFRM 지원이 문제가되지 않고 더 속도를 높이고 싶다면 C로 코사인 거리 코드를 C로 코딩하고 컴파일러가 결과 코드를 적극적으로 벡터화하고 있는지 확인할 수 있습니다 (Pentium II조차도 일부 부동 소수점 벡터화가 가능합니다. )
