2

値の2つの辞書を比較するために、ピアソンの類似性スコアを実装しました。この方法では、他のどこよりも多くの時間が費やされるため（数百万の呼び出しが発生する可能性があります）、これは明らかに最適化するための重要な方法です。

ほんの少しの最適化でもコードに大きな影響を与える可能性があるので、ほんの少しの改善でも探求したいと思っています。

これが私がこれまでに持っているものです：

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
4

8 に答える 8

4

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)

等々; これらのそれぞれが時間の利点をもたらすかどうかは、マイクロベンチマークが必要です。これらの係数をどのように使用しているかに応じて、正方形を返すと sqrt が節約されます (これは、距離自体ではなく、ジオメトリでポイント間の距離の 2 乗を使用するのと同様の考え方であり、同じ理由で、sqrt を節約できます)。 ; 係数は距離なので、これは理にかなっています...;-)。

于 2009-08-20T15:57:29.517 に答える
2

Scipyは最速です！

上記のコードと、コンプで見つけたバージョンを使用していくつかのテストを行いました。結果とコードについては、以下を参照してください。

ピアソン 14.7597990757
sim_pearson 15.6806837987
scipy:pearsonr 0.451986019188


試す：
    輸入サイコ
    psyco.full()
ImportError を除く:
    合格

数学インポート平方根から

def sim_pearson (セット 1、セット 2):
    si={}
    set1 のアイテム:
        set2 のアイテムの場合:
            si[項目] = 1

    #要素数
    n = レン(si)

    #共通点がない場合は類似度 0 を返す
    n == 0 の場合: 0 を返す

    #すべての設定を追加
    sum1 = sum([set1[item] for item in si])
    sum2 = sum([set2[item] for item in si])

    #平方和
    sum_sq1 = sum([pow(set1[item], 2) for item in si])
    sum_sq2 = sum([pow(set2[item], 2) for item in si])

    #商品をまとめる
    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) )

    den==0 の場合: 0 を返す
    名義を返す



# http://stackoverflow.com/questions/1307016/pearson-similarity-score-how-can-i-optimise-this-further から
デフピアソン（v1、v2）：
    vs = [(v1[val],v2[val]) for v1 の val if v2 の val]

    n = レン(対)

    n==0 の場合: 0.0 を返す

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

    vs の v1、v2 の場合:
        sum1+=v1
        sum2+=v2
        sum1_sq+=v1*v1
        sum2_sq+=v2*v2
        p_sum+=v1*v2

    # ピアソンスコアを計算する
    num = p_sum-(sum1*sum2/n)
    temp = max((sum1_sq-pow(sum1,2)/n) * (sum2_sq-pow(sum2,2)/n),0)
    一時的な場合:
        戻り値 / sqrt(temp)
    1.0を返す






if __name__ == "__main__":
    輸入時間

    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 = [range(1000) 内の x の randrange(0,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 'ピアソン', t1.timeit(tt)
    print 'sim_pearson', t2.timeit(tt)
    print 'scipy:pearsonr', t3.timeit(tt)
于 2010-02-17T12:22:13.120 に答える
2

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）。

于 2009-08-21T19:19:26.543 に答える
1

かなりの数値計算を行っているように見えるので、Psycoを試してみてください。実行中のコードを分析し、特定の操作を最適化する JIT コンパイラです。インストールしてから、ファイルの先頭に次のように入力します。

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

これにより、Psyco の JIT が有効になり、無料でコードがいくらか高速化されるはずです :) (実際にはそうではなく、より多くのメモリを消費します)

于 2009-08-21T03:24:43.250 に答える
1

変更することをお勧めします：

[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
于 2009-08-20T16:08:11.977 に答える
0

数学関数への入力がかなり制約されている場合は、数学関数の代わりにルックアップ テーブルを使用できます。これにより、テーブルを格納するための余分なメモリを犠牲にして、ある程度のパフォーマンス (速度) を得ることができます。

于 2009-08-20T15:47:28.897 に答える
0

質問と区別するために、これまでに得たものを回答として投稿します。これは、これまでで最高の改善をもたらしたと思われる、上記のいくつかの手法の組み合わせです。

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

編集: psyco はこのバージョンで 15% の改善を行っているように見えますが、これは大規模ではありませんが、その使用を正当化するのに十分です.

于 2009-08-21T14:23:36.117 に答える
0

これが Python に当てはまるかどうかはわかりません。ただし、sqrt の計算は、プロセッサを集中的に使用する計算です。

あなたは高速近似ニュートンに行くかもしれません

于 2009-08-20T15:49:11.733 に答える