python - ユークリッド距離の計算のための Python 最適化

Question

この関数は、私のプログラムで 200 万回以上実行されています。誰でもこれを最適化することを提案できますか? x と y はタプルです。

def distance(x,y):

    return sqrt((x[0]-y[0])*(x[0]-y[0])+(x[1]-y[1])*(x[1]-y[1])+(x[2]-y[2])*(x[2]-y[2]))

私の試み: math.sqrt、pow、および x**.5 を使用してみましたが、パフォーマンスはあまり向上しません。

Answer 1

同じ x[i] 要素にアクセスせず、ローカルにバインドすることで、いくつかのサイクルを削減できます。

def distance(x,y):
    x0, x1, x2 = x
    y0, y1, y2 = y
    return sqrt((x0-y0)*(x0-y0)+(x1-y1)*(x1-y1)+(x2-y2)*(x2-y2))

例、比較:

>>> import timeit
>>> timer = timeit.Timer(setup='''
... from math import sqrt
... def distance(x,y):
...    return sqrt((x[0]-y[0])*(x[0]-y[0])+(x[1]-y[1])*(x[1]-y[1])+(x[2]-y[2])*(x[2]-y[2]))
... ''', stmt='distance((0,0,0), (1,2,3))')
>>> timer.timeit(1000000)
1.2761809825897217

と：

>>> import timeit
>>> timer = timeit.Timer(setup='''
... from math import sqrt
... def distance(x,y):
...    x0, x1, x2 = x
...    y0, y1, y2 = y
...    return sqrt((x0-y0)*(x0-y0)+(x1-y1)*(x1-y1)+(x2-y2)*(x2-y2))
... ''', stmt='distance((0,0,0), (1,2,3))')
>>> timer.timeit(1000000)
0.8375771045684814

python wiki には、パフォーマンスに関するヒントが他にもあります。

Answer 2

オリジナル：

>>> timeit.timeit('distance2((0,1,2),(3,4,5))', '''
... from math import sqrt
... def distance2(x,y):
...     return sqrt((x[0]-y[0])*(x[0]-y[0])+(x[1]-y[1])*(x[1]-y[1])+(x[2]-y[2])*(x[2]-y[2]))
... ''')
1.1989610195159912

一般的な部分式除去：

>>> timeit.timeit('distance((0,1,2),(3,4,5))', '''
... def distance(x,y):
...     d1 = x[0] - y[0]
...     d2 = x[1] - y[1]
...     d3 = x[2] - y[2]
...     return (d1 * d1 + d2 * d2 + d3 * d3) ** .5''')
0.93855404853820801

最適化された開梱：

>>> timeit.timeit('distance((0,1,2),(3,4,5))', '''
... def distance(x,y):
...     x1, x2, x3 = x
...     y1, y2, y3 = y
...     d1 = x1 - y1
...     d2 = x2 - y2
...     d3 = x3 - y3
...     return (d1 * d1 + d2 * d2 + d3 * d3) ** .5''')
0.90851116180419922

ライブラリ関数：

>>> timeit.timeit('distance((0,1,2),(3,4,5))', '''
... import math
... def distance(x,y):
...     x1, x2, x3 = x
...     y1, y2, y3 = y
...     d1 = x1 - y1
...     d2 = x2 - y2
...     d3 = x3 - y3
...     return math.sqrt(d1 * d1 + d2 * d2 + d3 * d3)
... ''')
0.78318595886230469

点在：

>>> timeit.timeit('distance((0,1,2),(3,4,5))', '''
... from math import sqrt
... def distance(x,y):
...     x1, x2, x3 = x
...     y1, y2, y3 = y
...     d1 = x1 - y1
...     d2 = x2 - y2
...     d3 = x3 - y3
...     return sqrt(d1 * d1 + d2 * d2 + d3 * d3)
... ''')
0.75629591941833496

Answer 3

scipy にはユークリッド距離関数があります。おそらくこれ以上速くなることはないでしょう。

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

from scipy.spatial.distance import euclidean
import numpy as np

# x and y are 1 x 3 vectors
x = np.random.rand(1,3) 
y = np.random.rand(1,3)
euclidean(x,y)

編集:実際には、OP の pure-python distance() 関数に対して timeit を介してこれを実行すると、これは実際には Python フロートでかなり遅くなることが判明しています。scipy バージョンは、float を numpy dtype にキャストするのに時間を浪費していると思います。控えめに言っても、かなり驚いています。