Оптимизация на Python Для расчета эуклидианского расстояния

Question

Эта функция запускается более чем 2 миллиона раз в моей программе. Может ли кто-нибудь предложить оптимизировать это? 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 и х ** 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 

Есть еще performance tips on the 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) 

EDIT: На самом деле, это работает через timeit против функции ФП в чисто-питон расстояние(), это на самом деле, оказывается, путь медленнее питона поплавков. Я думаю, что scipy версия тратит некоторое время, бросая поплавки на numpy dtypes. Я очень удивлен, если не сказать больше.