Optimiertes Verfahren zum Berechnen Cosinus Abstandes in Python

Question

Ich schrieb eine Methode, um den Cosinus-Abstand zwischen zwei Arrays zu berechnen:

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

es betrieben wird, kann auf einem großen Array sehr langsam sein. Gibt es eine optimierte Version dieses Verfahrens, die schneller laufen würde?

Update: Ich habe versucht, alle Vorschläge bisher, einschließlich scipy. Hier ist die Version zu schlagen, enthält Vorschläge von Mike und 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

Answer 1

Wenn Sie SciPy verwenden können, Sie cosine von spatial.distance verwenden können:

http://docs.scipy.org/doc/scipy/reference/spatial.distance.html

Wenn Sie nicht SciPy verwenden können, können Sie versuchen, eine kleine Beschleunigung zu erhalten, durch Umschreiben Ihres Python (EDIT: aber es hat nicht funktioniert, wie ich dachte, es wäre, siehe unten).

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

Es ist besser, eine Ausnahme zu erhöhen, wenn die Längen von a und b stimmen nicht überein.

Durch die Verwendung von Generator Ausdrücke innerhalb von Anrufen Sie sum() Ihre Werte mit den meisten der Arbeit berechnen können innerhalb von Python durch den C-Code getan. Dies sollte schneller sein als eine for Schleife.

Ich habe dies nicht abgelaufen ist, so kann ich nicht erraten, wie viel schneller könnte es sein. Aber der SciPy Code in C oder C ++ an Sicherheit grenzender Wahrscheinlichkeit geschrieben und es sollte über sein so schnell, wie Sie bekommen können.

Wenn Sie Bioinformatik in Python tun, sollten Sie wirklich verwenden SciPy sowieso.

EDIT: Darius Speck timed meinen Code und fand es langsamer. So timed ich meinen Code und ... ja, es langsamer ist. Die Lektion für alle. Wenn Sie versuchen, die Dinge zu beschleunigen, nicht erraten, messen

Ich bin ratlos, warum mein Versuch, mehr Arbeit an den C-Interna von Python zu setzen ist langsamer. Ich habe versucht, es für die Listen der Länge 1000 und es war noch langsamer.

Ich kann nicht mehr Zeit damit verbringen, zu versuchen, den Python geschickt zu hacken. Wenn Sie mehr Geschwindigkeit benötigen, empfehle ich Ihnen SciPy versuchen.

EDIT: Ich habe von Hand geprüft, ohne timeit. Ich finde, dass für kurze a und b, der alte Code ist schneller; für lange a und b, ist der neue Code schneller; in beiden Fällen ist der Unterschied nicht groß. (Ich frage mich jetzt, ob ich timeit auf meinen Windows-Computer vertrauen kann;. Ich mag auf Linux diesen Test noch einmal versuchen) Ich würde nicht ändern Code arbeiten zu versuchen, es schneller zu bekommen. Und noch eine Zeit, die ich fordere Sie SciPy zu versuchen. : -)

Answer 2

(Ich dachte ursprünglich) Sie es nicht beschleunigen würden viel ohne zu C Ausbrechen (wie numpy oder scipy) oder zu ändern, was Sie berechnen. Aber hier ist, wie ich das versuchen würde, auf jeden Fall:

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))))

Es ist etwa doppelt so schnell in Python 2.6 mit 500k-Element-Arrays. (Nach Karte Ändern imap nach Jarret Hardie.)

Hier ist eine gezwickt Version der überarbeiteten Code der Original-Poster:

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)

Es ist hässlich, aber es kommt schneller aus. . .

Edit: Und versuchen Psyco ! Es beschleunigt die finale Version von einem anderen Faktor 4 bis Wie konnte ich das vergessen?

Answer 3

Keine Notwendigkeit abs() von a[i] und b[i] zu nehmen, wenn Sie es sind quadriert.

Shop a[i] und b[i] in temporären Variablen, tun die Indizierung mehr als einmal zu vermeiden. Vielleicht kann der Compiler dies optimieren, aber vielleicht auch nicht.

Überprüfen Sie in den **2 Operator. Ist es in eine mehrfach zu vereinfachen, oder ist es eine allgemeine Leistungsfunktion (log - mit 2 multiplizieren - Antilogs).

Sie tun sqrt nicht zweimal (obwohl die Kosten für das klein ist). Haben sqrt(denoma * denomb).

Answer 4

Ähnlich wie Darius Bacons Antwort, ich habe liebäugelt worden mit Operator und itertools eine schnellere Antwort zu produzieren. Die folgende scheint nach timeit 1/3 schneller auf einer 500-Element-Array zu sein:

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)

Answer 5

Dies ist schneller für Arrays von rund 1000 Elemente.

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

Answer 6

Mit dem C-Code innerhalb von SciPy groß für lange Eingangsarrays gewinnt. Mit einfachen und direkten Python gewinnt für kurze Eingabe-Arrays; Darius Bacon izip()-basierten Code gebenchmarkt aus am besten. Somit ist die ultimative Lösung zu entscheiden, welches zur Laufzeit zu verwenden, bezogen auf die Länge der Eingabefelder:

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)

habe ich einen Test-Harnisch, der die Funktionen mit unterschiedlicher Länge Eingänge getestet und festgestellt, dass die SciPy Funktion um Länge 200 gestartet, um zu gewinnen. Je größer die Eingabefelder, desto größer ist es gewinnt. Für sehr kurze Länge Arrays, sagt Länge 3, desto einfacher Code gewinnt. Diese Funktion fügt eine winzige Menge an Overhead zu entscheiden, welche Art und Weise, es zu tun, dann tut es der beste Weg.

Falls Sie daran interessiert sind, hier ist der Test-Harnisch:

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)

Answer 7

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

Answer 8

Ihre aktualisierte Lösung hat noch zwei Quadratwurzeln. Sie können dies durch den Austausch der sqrt Linie auf eine Verringerung mit:

  

result = 1 - Zähler /   (Sqrt (denoma * denomb))

Eine Multiplikation ist in der Regel ziemlich viel schneller als ein sqrt. Es ist vielleicht nicht viel erscheinen, wie es nur einmal in der Funktion aufgerufen wird, aber es klingt wie Sie eine Menge Cosinus Abstände zu berechnen, so wird die Verbesserung addiert.

Ihr Code sieht aus wie es für Vektor-Optimierungen reif sein sollte. Also, wenn Quer platofrm Unterstützung kein Problem ist und Sie wollen es beschleunigen noch weiter, können Sie die Cosinus-Distanz Code in C-Code könnte und stellen Sie sicher, dass Ihr Compiler aggressiv den resultierenden Code Vektorisierung (auch Pentium II ist in der Lage einige Floating-Point-Vektorisierung )