Оценка сходства Пирсона, как я могу оптимизировать это дальше?

Question

У меня есть реализованная оценка сходства Пирсона для сравнения двух словарей значений. В этом методе тратится больше времени, чем где бы то ни было (потенциально много миллионов вызовов), поэтому этот метод явно важен для оптимизации.

Даже малейшая оптимизация может оказать большое влияние на мой код, поэтому я стремлюсь исследовать даже самые маленькие улучшения.

Вот что у меня есть:

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

Реальное увеличение скорости можно получить, перейдя в NumPy или Scipy. Если не считать этого, существуют микрооптимизации: например, x*x быстрее pow(x,2); вы можете извлечь значения одновременно с ключами, выполнив вместо:

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

что-то вроде

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

, а затем

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

и т. Д .; требует ли микробенчмаркинг каждое из этих преимуществ для времени? В зависимости от того, как вы используете эти коэффициенты, возвращение квадрата сэкономит вам квадрат (это аналогично использованию квадратов расстояний между точками в геометрии, а не самих расстояний и по той же причине - экономит вам квадрат) ; это имеет смысл, потому что коэффициент - это расстояние, вроде ...; -).

Answer 2

Сципи самый быстрый!

У меня есть несколько тестов с кодом выше, а также с версией, которую я нашел на моем компе, результаты и код см. Ниже:

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 /899238/otsenka-shodstva-pirsona-kak-ya-mogu-optimizirovat-eto-dalshe
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 3

Если вы можете использовать scipy, вы можете использовать функцию Пирсона: http://www.scipy.org/doc/api_docs/SciPy.stats.stats.html#pearsonr

Или вы можете скопировать / вставить код (он имеет либеральную лицензию) из http://svn.scipy.org/svn/scipy/trunk/scipy/stats/stats.py (поиск def pearson()). В коде np это просто numpy (код делает import numpy as np).

Answer 4

Поскольку похоже, что вы делаете довольно много числовых вычислений, вы должны дать Psyco выстрел. Это JIT-компилятор, который анализирует выполняемый код и оптимизирует определенные операции. Установите его, затем в верхней части вашего файла поставьте:

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

Это активирует JIT от Psyco и должно несколько ускорить ваш код бесплатно :) (на самом деле нет, это занимает больше памяти)

Answer 5

Я бы предложил изменить:

[val for val in v1 if val in v2]

до

set(v1) & set(v2)

сделать

if not n: return 0.0    # and similar for den

вместо

if n == 0: return 0.0

и стоит заменить последние 6 строк на:

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

Answer 6

Я опубликую то, что у меня есть, в качестве ответа, чтобы отличить его от вопроса. Это комбинация некоторых методов, описанных выше, которые, похоже, дали наилучшие результаты.

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

Редактировать: похоже, что психо дает 15% улучшения для этой версии, которая не является массовой, но достаточной для оправдания ее использования.

Answer 7

Я не уверен, верно ли это в Python. Но вычисление sqrt требует интенсивного процессора.

Вы можете пойти на быстрое приближение ньютон

Answer 8

Если входные данные для любой из ваших математических функций довольно ограничены, вы можете использовать таблицу поиска вместо математической функции. Это может принести вам некоторую производительность (скорость) за счет дополнительной памяти для хранения таблицы.