Pearson Punteggio somiglianza, come posso ottimizzare questo ulteriore?

Question

Ho un implementato del punteggio somiglianza di Pearson per confrontare due dizionari di valori. Più tempo è trascorso in questo metodo che altrove (potenzialmente molti milioni di chiamate), quindi questo è chiaramente il metodo critico per ottimizzare.

Anche il minimo di ottimizzazione potrebbe avere un grande impatto sul mio codice, quindi sono desiderosi di esplorare anche le più piccole migliorie.

Ecco quello che ho finora:

def simple_pearson(v1,v2):

    si = [val for val in v1 if val in v2]

    n = len(si)

    if n==0: return 0.0

    sum1 = 0.0
    sum2 = 0.0
    sum1_sq = 0.0
    sum2_sq = 0.0
    p_sum = 0.0

    for v in si:
        val_1 = v1[v]
        val_2 = v2[v]
        sum1+=val_1
        sum2+=val_2
        sum1_sq+=pow(val_1,2)
        sum2_sq+=pow(val_2,2)
        p_sum+=val_1*val_2

    # Calculate Pearson score
    num = p_sum-(sum1*sum2/n)
    temp = (sum1_sq-pow(sum1,2)/n) * (sum2_sq-pow(sum2,2)/n)
    if temp < 0.0:
        temp = -temp
    den = sqrt(temp)
    if den==0: return 1.0

    r = num/den

    return r

Answer 1

SciPy è il più veloce!

Ho don alcuni test con il codice di cui sopra e anche con una versione che ho trovato sul mio comp, vedi sotto per i risultati e il codice:

pearson 14.7597990757
sim_pearson 15.6806837987
scipy:pearsonr 0.451986019188

try:
    import psyco
    psyco.full()
except ImportError:
    pass

from math import sqrt

def sim_pearson(set1, set2):
    si={}
    for item in set1:
        if item in set2:
            si[item] = 1

    #number of elements
    n = len(si)

    #if none common, return 0 similarity
    if n == 0: return 0

    #add up all the preferences
    sum1 = sum([set1[item] for item in si])
    sum2 = sum([set2[item] for item in si])

    #sum up the squares
    sum_sq1 = sum([pow(set1[item], 2) for item in si])
    sum_sq2 = sum([pow(set2[item], 2) for item in si])

    #sum up the products
    sum_p = sum([set1[item] * set2[item] for item in si])

    nom = sum_p - ((sum1 * sum2) / n )
    den = sqrt( (sum_sq1 - (sum1)**2 / n) * (sum_sq2 - (sum2)**2 / n) )

    if den==0: return 0
    return nom/den



# from http://stackoverflow.com/questions/1307016/pearson-similarity-score-how-can-i-optimise-this-further
def pearson(v1, v2):
    vs = [(v1[val],v2[val]) for val in v1 if val in v2]

    n = len(vs)

    if n==0: return 0.0

    sum1,sum2,sum1_sq,sum2_sq,p_sum = 0.0, 0.0, 0.0, 0.0, 0.0

    for v1,v2 in vs:
        sum1+=v1
        sum2+=v2
        sum1_sq+=v1*v1
        sum2_sq+=v2*v2
        p_sum+=v1*v2

    # Calculate Pearson score
    num = p_sum-(sum1*sum2/n)
    temp = max((sum1_sq-pow(sum1,2)/n) * (sum2_sq-pow(sum2,2)/n),0)
    if temp:
        return num / sqrt(temp)
    return 1.0






if __name__ == "__main__":
    import timeit

    tsetup = """
from random import randrange
from __main__ import pearson, sim_pearson
from scipy.stats import pearsonr
v1 = [randrange(0,1000) for x in range(1000)]
v2 = [randrange(0,1000) for x in range(1000)]
#gc.enable()
"""
    t1 = timeit.Timer(stmt="pearson(v1,v2)", setup=tsetup)
    t2 = timeit.Timer(stmt="sim_pearson(v1,v2)", setup=tsetup)
    t3 = timeit.Timer(stmt="pearsonr(v1,v2)", setup=tsetup)

    tt = 1000

    print 'pearson', t1.timeit(tt)
    print 'sim_pearson', t2.timeit(tt)
    print 'scipy:pearsonr', t3.timeit(tt)

Answer 2

L'aumento della velocità reale sarebbe essere acquisita spostando a NumPy o SciPy. In mancanza di questo, ci sono microoptimizations: per esempio x*x è più veloce di pow(x,2); si potrebbe estrarre i valori nello stesso momento in cui le chiavi da fare, invece di:

si = [val for val in v1 if val in v2]

qualcosa di simile

vs = [ (v1[val],v2[val]) for val in v1 if val in v2]

e quindi

sum1 = sum(x for x, y in vs)

e così via; se ciascuno di essi porta vantaggio tempo necessario microbenchmarking. A seconda di come si sta utilizzando questi coefficienti di ritorno piazza si risparmierebbe uno sqrt (che è un'idea simile ad usare le piazze di distanze tra i punti, in geometria, piuttosto che le distanze stessi, e per la stessa ragione - consente di risparmiare uno sqrt ; che ha un senso, perché il coefficiente è una distanza, un po '...; -).

Answer 3

Se è possibile utilizzare SciPy, è possibile utilizzare la funzione di Pearson: http://www.scipy.org/doc/api_docs/SciPy.stats.stats.html#pearsonr

In alternativa è possibile copiare / incollare il codice (che ha una licenza liberale) da http://svn.scipy.org/svn/scipy/trunk/scipy/stats/stats.py (ricerca di def pearson()). Nel codice np è solo numpy (il codice fa import numpy as np).

Answer 4

Io suggerirei cambiare:

[val for val in v1 if val in v2]

a

set(v1) & set(v2)

do

if not n: return 0.0    # and similar for den

anziché

if n == 0: return 0.0

e vale la pena di sostituire ultimi 6 linee con:

try:
    return num / sqrt(abs(temp))
except ZeroDivisionError:
    return 1.0

Answer 5

Dal momento che sembra che si sta facendo un po 'di calcolo numerico si dovrebbe dare Psyco un colpo. Si tratta di un compilatore JIT che analizza il codice in esecuzione e ottimizza alcune operazioni. Installarlo, quindi nella parte superiore del vostro put file:

try:
    import psyco
    psyco.full()
except ImportError:
    pass

Ciò consentirà JIT di Psyco e dovrebbe accelerare il codice in qualche modo, gratis :) (in realtà non si occupa più memoria)

Answer 6

Se gli ingressi per le tue funzioni matematiche sono abbastanza limitate, è possibile utilizzare una tabella di ricerca anziché la funzione matematica. Questo può guadagnare un po 'di prestazioni (velocità) al costo di memoria aggiuntiva per memorizzare la tabella.

Answer 7

Non sono sicuro se questo vale in Python. Ma il calcolo sqrt è un calcolo intensivi processore.

Si potrebbe andare per una newton

Answer 8

Vi posto quello che ho finora come una risposta per differenziarlo dalla questione. Si tratta di una combinazione di alcune tecniche sopra descritte, che sembrano aver dato il meglio di miglioramento è lontano.

def pearson(v1,v2):
    vs = [(v1[val],v2[val]) for val in v1 if val in v2]

    n = len(vs)

    if n==0: return 0.0

    sum1,sum2,sum1_sq,sum2_sq,p_sum = 0.0, 0.0, 0.0, 0.0, 0.0

    for v1,v2 in vs:
        sum1+=v1
        sum2+=v2
        sum1_sq+=v1*v1
        sum2_sq+=v2*v2
        p_sum+=v1*v2

    # Calculate Pearson score
    num = p_sum-(sum1*sum2/n)
    temp = max((sum1_sq-pow(sum1,2)/n) * (sum2_sq-pow(sum2,2)/n),0)
    if temp:
        return num / sqrt(temp)
    return 1.0

Modifica:. Sembra Psyco dà un improvment 15% per questa versione che non è enorme, ma è abbastanza per giustificare il suo utilizzo