У меня две точки в 3D:
(xa, ya, za)
(xb, yb, zb)
И я хочу рассчитать расстояние:
dist = sqrt((xa-xb)^2 + (ya-yb)^2 + (za-zb)^2)
Какой лучший способ сделать это с помощью NumPy или с Python в целом? У меня есть:
a = numpy.array((xa ,ya, za))
b = numpy.array((xb, yb, zb))
Используйте numpy.linalg.norm:
dist = numpy.linalg.norm(a-b)
Теория За этим: как описано в Введение в интеллектуальный анализ данных
Это работает, потому что евклидово расстояние равно l2 норма, а значение по умолчанию для параметра ord в numpy.linalg.norm равно 2.
Там функция для SciPy. Он назывался евклидовым.
Пример:
from scipy.spatial import distance
a = (1, 2, 3)
b = (4, 5, 6)
dst = distance.euclidean(a, b)
Для тех, кто интересуется вычислением нескольких расстояний одновременно, я провел небольшое сравнение, используя perfplot (мой небольшой проект).
Первый совет - организовать ваши данные так, чтобы массивы имели размерность (3, n) (и, очевидно, C-смежны). Если добавление происходит в смежном первом измерении, все происходит быстрее, и это не имеет большого значения, если вы используете sqrt-sum с axis=0, linalg.norm с axis=0 или
a_min_b = a - b
numpy.sqrt(numpy.einsum('ij,ij->j', a_min_b, a_min_b))
который с небольшим отрывом самый быстрый вариант. (Это действительно справедливо только для одной строки.)
Варианты, в которых вы суммируете по второй оси, axis=1, все значительно медленнее.
Код для воспроизведения сюжета:
import numpy
import perfplot
from scipy.spatial import distance
def linalg_norm(data):
a, b = data[0]
return numpy.linalg.norm(a - b, axis=1)
def linalg_norm_T(data):
a, b = data[1]
return numpy.linalg.norm(a - b, axis=0)
def sqrt_sum(data):
a, b = data[0]
return numpy.sqrt(numpy.sum((a - b) ** 2, axis=1))
def sqrt_sum_T(data):
a, b = data[1]
return numpy.sqrt(numpy.sum((a - b) ** 2, axis=0))
def scipy_distance(data):
a, b = data[0]
return list(map(distance.euclidean, a, b))
def sqrt_einsum(data):
a, b = data[0]
a_min_b = a - b
return numpy.sqrt(numpy.einsum("ij,ij->i", a_min_b, a_min_b))
def sqrt_einsum_T(data):
a, b = data[1]
a_min_b = a - b
return numpy.sqrt(numpy.einsum("ij,ij->j", a_min_b, a_min_b))
def setup(n):
a = numpy.random.rand(n, 3)
b = numpy.random.rand(n, 3)
out0 = numpy.array([a, b])
out1 = numpy.array([a.T, b.T])
return out0, out1
perfplot.save(
"norm.png",
setup=setup,
n_range=[2 ** k for k in range(22)],
kernels=[
linalg_norm,
linalg_norm_T,
scipy_distance,
sqrt_sum,
sqrt_sum_T,
sqrt_einsum,
sqrt_einsum_T,
],
logx=True,
logy=True,
xlabel="len(x), len(y)",
)
Другой пример этого метода решения проблемы:
def dist(x,y):
return numpy.sqrt(numpy.sum((x-y)**2))
a = numpy.array((xa,ya,za))
b = numpy.array((xb,yb,zb))
dist_a_b = dist(a,b)
Я хочу изложить простой ответ с различными заметками о производительности. np.linalg.norm сделает, возможно, больше, чем вам нужно:
dist = numpy.linalg.norm(a-b)
Во-первых, эта функция предназначена для работы со списком и возврата всех значений, например, для сравнения расстояния от pA до набора точек sP:
sP = set(points)
pA = point
distances = np.linalg.norm(sP - pA, ord=2, axis=1.) # 'distances' is a list
Помните несколько вещей:
Так
def distance(pointA, pointB):
dist = np.linalg.norm(pointA - pointB)
return dist
не так невинно, как кажется.
>>> dis.dis(distance)
2 0 LOAD_GLOBAL 0 (np)
2 LOAD_ATTR 1 (linalg)
4 LOAD_ATTR 2 (norm)
6 LOAD_FAST 0 (pointA)
8 LOAD_FAST 1 (pointB)
10 BINARY_SUBTRACT
12 CALL_FUNCTION 1
14 STORE_FAST 2 (dist)
3 16 LOAD_FAST 2 (dist)
18 RETURN_VALUE
Во-первых - каждый раз, когда мы вызываем его, мы должны выполнить глобальный поиск для "np", поиск в области видимости для "linalg" и поиск в области видимости для "нормы", а издержки простого вызова функции могут равняться десяткам Python инструкции.
Наконец, мы потратили две операции, чтобы сохранить результат и перезагрузить его для возврата...
Первый шаг к улучшению: сделайте поиск быстрее, пропустите магазин
def distance(pointA, pointB, _norm=np.linalg.norm):
return _norm(pointA - pointB)
Мы получаем гораздо более упорядоченный:
>>> dis.dis(distance)
2 0 LOAD_FAST 2 (_norm)
2 LOAD_FAST 0 (pointA)
4 LOAD_FAST 1 (pointB)
6 BINARY_SUBTRACT
8 CALL_FUNCTION 1
10 RETURN_VALUE
Затраты на вызов функции по-прежнему составляют некоторую работу. И вы захотите сделать тесты, чтобы определить, лучше ли вам делать математику самостоятельно:
def distance(pointA, pointB):
return (
((pointA.x - pointB.x) ** 2) +
((pointA.y - pointB.y) ** 2) +
((pointA.z - pointB.z) ** 2)
) ** 0.5 # fast sqrt
На некоторых платформах **0.5 быстрее, чем math.sqrt. Ваш пробег может варьироваться.
**** Расширенные заметки производительности.
Почему вы рассчитываете расстояние? Если единственной целью является его отображение,
print("The target is %.2fm away" % (distance(a, b)))
двигаться вперед. Но если вы сравниваете расстояния, проводите проверки дальности и т.д., Я хотел бы добавить некоторые полезные наблюдения за производительностью.
Давайте рассмотрим два случая: сортировка по расстоянию или отбор списка по элементам, которые соответствуют ограничению диапазона.
# Ultra naive implementations. Hold onto your hat.
def sort_things_by_distance(origin, things):
return things.sort(key=lambda thing: distance(origin, thing))
def in_range(origin, range, things):
things_in_range = []
for thing in things:
if distance(origin, thing) <= range:
things_in_range.append(thing)
Первое, что нам нужно помнить, это то, что мы используем Pythagoras для вычисления расстояния (dist = sqrt(x^2 + y^2 + z^2)), поэтому мы делаем много вызовов sqrt. Математика 101:
dist = root ( x^2 + y^2 + z^2 )
:.
dist^2 = x^2 + y^2 + z^2
and
sq(N) < sq(M) iff M > N
and
sq(N) > sq(M) iff N > M
and
sq(N) = sq(M) iff N == M
Короче говоря, пока нам не потребуется расстояние в единице X, а не X ^ 2, мы можем исключить самую сложную часть вычислений.
# Still naive, but much faster.
def distance_sq(left, right):
""" Returns the square of the distance between left and right. """
return (
((left.x - right.x) ** 2) +
((left.y - right.y) ** 2) +
((left.z - right.z) ** 2)
)
def sort_things_by_distance(origin, things):
return things.sort(key=lambda thing: distance_sq(origin, thing))
def in_range(origin, range, things):
things_in_range = []
# Remember that sqrt(N)**2 == N, so if we square
# range, we don't need to root the distances.
range_sq = range**2
for thing in things:
if distance_sq(origin, thing) <= range_sq:
things_in_range.append(thing)
Отлично, обе функции больше не делают дорогих квадратных корней. Это будет намного быстрее. Мы также можем улучшить in_range, преобразовав его в генератор:
def in_range(origin, range, things):
range_sq = range**2
yield from (thing for thing in things
if distance_sq(origin, thing) <= range_sq)
Это особенно полезно, если вы делаете что-то вроде:
if any(in_range(origin, max_dist, things)):
...
Но если следующая вещь, которую вы собираетесь сделать, требует расстояния,
for nearby in in_range(origin, walking_distance, hotdog_stands):
print("%s %.2fm" % (nearby.name, distance(origin, nearby)))
рассмотреть возможность получения кортежей:
def in_range_with_dist_sq(origin, range, things):
range_sq = range**2
for thing in things:
dist_sq = distance_sq(origin, thing)
if dist_sq <= range_sq: yield (thing, dist_sq)
Это может быть особенно полезно, если вы можете связать проверки диапазона ("найдите вещи, которые находятся около X и в пределах Nm от Y", так как вам не нужно снова вычислять расстояние).
Но что делать, если мы ищем действительно большой список things и ожидаем, что многие из них не заслуживают рассмотрения?
Там на самом деле очень простая оптимизация:
def in_range_all_the_things(origin, range, things):
range_sq = range**2
for thing in things:
dist_sq = (origin.x - thing.x) ** 2
if dist_sq <= range_sq:
dist_sq += (origin.y - thing.y) ** 2
if dist_sq <= range_sq:
dist_sq += (origin.z - thing.z) ** 2
if dist_sq <= range_sq:
yield thing
Будет ли это полезно, будет зависеть от размера "вещей".
def in_range_all_the_things(origin, range, things):
range_sq = range**2
if len(things) >= 4096:
for thing in things:
dist_sq = (origin.x - thing.x) ** 2
if dist_sq <= range_sq:
dist_sq += (origin.y - thing.y) ** 2
if dist_sq <= range_sq:
dist_sq += (origin.z - thing.z) ** 2
if dist_sq <= range_sq:
yield thing
elif len(things) > 32:
for things in things:
dist_sq = (origin.x - thing.x) ** 2
if dist_sq <= range_sq:
dist_sq += (origin.y - thing.y) ** 2 + (origin.z - thing.z) ** 2
if dist_sq <= range_sq:
yield thing
else:
... just calculate distance and range-check it ...
И снова, рассмотрите возможность выдачи dist_sq. Наш пример хот-дога становится:
# Chaining generators
info = in_range_with_dist_sq(origin, walking_distance, hotdog_stands)
info = (stand, dist_sq**0.5 for stand, dist_sq in info)
for stand, dist in info:
print("%s %.2fm" % (stand, dist))
Это можно сделать следующим образом. Я не знаю, как это быстро, но не использует NumPy.
from math import sqrt
a = (1, 2, 3) # Data point 1
b = (4, 5, 6) # Data point 2
print sqrt(sum( (a - b)**2 for a, b in zip(a, b)))
Я нахожу функцию "dist" в matplotlib.mlab, но я не думаю, что это достаточно удобно.
Я размещаю его здесь только для справки.
import numpy as np
import matplotlib as plt
a = np.array([1, 2, 3])
b = np.array([2, 3, 4])
# Distance between a and b
dis = plt.mlab.dist(a, b)
Начиная с Python 3.8, модуль math напрямую предоставляет функцию dist, которая возвращает евклидово расстояние между двумя точками (в виде кортежей или списков координат):
from math import dist
dist((1, 2, 6), (-2, 3, 2)) # 5.0990195135927845
А если вы работаете со списками:
dist([1, 2, 6], [-2, 3, 2]) # 5.0990195135927845
Вы можете просто вычесть векторы, а затем innerproduct.
Следуя вашему примеру,
a = numpy.array((xa, ya, za))
b = numpy.array((xb, yb, zb))
tmp = a - b
sum_squared = numpy.dot(tmp.T, tmp)
result sqrt(sum_squared)
Это простой код и его легко понять.
Мне нравится np.dot (точка продукта):
a = numpy.array((xa,ya,za))
b = numpy.array((xb,yb,zb))
distance = (np.dot(a-b,a-b))**.5
Хороший однострочный:
dist = numpy.linalg.norm(a-b)
Однако, если скорость вызывает беспокойство, я бы рекомендовал экспериментировать на вашем компьютере. Я обнаружил, что использование math библиотеки sqrt с оператором ** для квадрата намного быстрее на моей машине, чем однострочное решение NumPy.
Я провел тесты, используя эту простую программу:
#!/usr/bin/python
import math
import numpy
from random import uniform
def fastest_calc_dist(p1,p2):
return math.sqrt((p2[0] - p1[0]) ** 2 +
(p2[1] - p1[1]) ** 2 +
(p2[2] - p1[2]) ** 2)
def math_calc_dist(p1,p2):
return math.sqrt(math.pow((p2[0] - p1[0]), 2) +
math.pow((p2[1] - p1[1]), 2) +
math.pow((p2[2] - p1[2]), 2))
def numpy_calc_dist(p1,p2):
return numpy.linalg.norm(numpy.array(p1)-numpy.array(p2))
TOTAL_LOCATIONS = 1000
p1 = dict()
p2 = dict()
for i in range(0, TOTAL_LOCATIONS):
p1[i] = (uniform(0,1000),uniform(0,1000),uniform(0,1000))
p2[i] = (uniform(0,1000),uniform(0,1000),uniform(0,1000))
total_dist = 0
for i in range(0, TOTAL_LOCATIONS):
for j in range(0, TOTAL_LOCATIONS):
dist = fastest_calc_dist(p1[i], p2[j]) #change this line for testing
total_dist += dist
print total_dist
На моей машине math_calc_dist работает намного быстрее, чем numpy_calc_dist: 1,5 секунды против 23,5 секунд.
Чтобы получить измеримую разницу между fastest_calc_dist и math_calc_dist мне пришлось увеличить TOTAL_LOCATIONS до 6000. Затем fastest_calc_dist занимает ~ 50 секунд, а math_calc_dist занимает ~ 60 секунд.
Вы также можете экспериментировать с numpy.sqrt и numpy.square хотя оба они были медленнее, чем math альтернативы на моей машине.
Мои тесты выполнялись с помощью Python 2.6.6.
Имея a и b, как вы их определили, вы также можете использовать:
distance = np.sqrt(np.sum((a-b)**2))
Здесь некоторый краткий код для евклидова расстояния в Python, учитывая две точки, представленные в виде списков в Python.
def distance(v1,v2):
return sum([(x-y)**2 for (x,y) in zip(v1,v2)])**(0.5)
Вычислить евклидово расстояние для многомерного пространства:
import math
x = [1, 2, 6]
y = [-2, 3, 2]
dist = math.sqrt(sum([(xi-yi)**2 for xi,yi in zip(x, y)]))
5.0990195135927845
import numpy as np
from scipy.spatial import distance
input_arr = np.array([[0,3,0],[2,0,0],[0,1,3],[0,1,2],[-1,0,1],[1,1,1]])
test_case = np.array([0,0,0])
dst=[]
for i in range(0,6):
temp = distance.euclidean(test_case,input_arr[i])
dst.append(temp)
print(dst)
import math
dist = math.hypot(math.hypot(xa-xb, ya-yb), za-zb)
Вы можете легко использовать формулу
distance = np.sqrt(np.sum(np.square(a-b)))
что фактически не что иное, как использование теоремы Пифагора для вычисления расстояния, путем добавления квадратов Δx, Δy и Δz и укоренения результата.
Если вы хотите найти расстояние от определенной точки от первой из сокращений, которую вы можете использовать, плюс вы можете сделать это с такими размерами, сколько хотите.
import numpy as np
A = [3,4]
Dis = np.sqrt(A[0]**2 + A[1]**2)
Сначала найдите разницу двух матриц. Затем примените умножение элемента с умножением на numpy. После этого найдите суммирование элемента умноженной новой матрицы. Наконец, найдите квадратный корень суммирования.
def findEuclideanDistance(a, b):
euclidean_distance = a - b
euclidean_distance = np.sum(np.multiply(euclidean_distance, euclidean_distance))
euclidean_distance = np.sqrt(euclidean_distance)
return euclidean_distance
Начиная с Python 3.8 модуль math включает функцию math.dist().
Смотрите здесь https://docs.python.org/3.8/library/math.html#math.dist.
math.dist(p1, p2)
Вернуть евклидово расстояние между двумя точками p1 и p2, каждый из которых представлен в виде последовательности (или итерируемой) координат.
import math
print( math.dist( (0,0), (1,1) )) # sqrt(2) -> 1.4142
print( math.dist( (0,0,0), (1,1,1) )) # sqrt(3) -> 1.7321