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)

编辑：实际上，通过 timeit 针对 OP 的纯 python distance() 函数运行它，这实际上在 python 浮点数上要慢得多。我认为 scipy 版本浪费了一些时间将浮点数转换为 numpy dtypes。至少可以说我很惊讶。