Эффективное вычисление евклидовой матрицы расстояний с использованием Numpy

У меня есть набор точек в двумерном пространстве и вам нужно рассчитать расстояние от каждой точки до точки друг друга.

У меня относительно небольшое количество очков, может быть, не больше 100. Но поскольку мне нужно делать это часто и быстро, чтобы определить отношения между этими движущимися точками, и поскольку я знаю, что повторение через точки может быть таким же плохим как O (n ^ 2) сложность, я ищу способы использовать матричную магию numpy (или scipy).

Как и в моем коде, координаты каждого объекта хранятся в своем классе. Однако я могу обновить их в массиве numpy, когда я обновляю координату класса.

class Cell(object): """Represents one object in the field.""" def __init__(self,id,x=0,y=0): self.m_id = id self.m_x = x self.m_y = y 

Для меня возникает создание евклидовой матрицы расстояния для предотвращения дублирования, но, возможно, у вас есть более умная структура данных.

Я открыт для указателей на отличные алгоритмы.

Кроме того, я отмечаю, что есть аналогичные вопросы, касающиеся евклидова расстояния и numpy, но не нашли того, что непосредственно затрагивает этот вопрос об эффективном заполнении матрицы полного расстояния.

  • Какой лучший скелетный код модуля библиотеки Python?
  • Tornado IOLoop Исключение в обратном вызове Отсутствует у работника сельдерея
  • Функция для создания zip-файла в памяти и возврата в виде ответа HTTP
  • корректировка осей с помощью imshow
  • Почему декодер python заменяет более чем недопустимые байты из кодированной строки?
  • Вертикальная линия в конце гистограммы CDF с использованием matplotlib
  • Недопустимые синтаксические выражения
  • Как установить pip на macOS или OS X?
  • 3 Solutions collect form web for “Эффективное вычисление евклидовой матрицы расстояний с использованием Numpy”

    Вы можете воспользоваться complex типом:

     # build a complex array of your cells z = np.array([complex(c.m_x, c.m_y) for c in cells]) 

    Первое решение

     # mesh this array so that you will have all combinations m, n = np.meshgrid(z, z) # get the distance via the norm out = abs(mn) 

    Второе решение

    Сцепление – главная идея. Но numpy умный, поэтому вам не нужно генерировать m & n . Просто вычислите разницу, используя транспонированную версию z . Сетка выполняется автоматически:

     out = abs(z[..., np.newaxis] - z) 

    Третье решение

    И если z непосредственно задается как 2-мерный массив, вы можете использовать zT вместо странного z[..., np.newaxis] . Итак, ваш код будет выглядеть так:

     z = np.array([[complex(c.m_x, c.m_y) for c in cells]]) # notice the [[ ... ]] out = abs(zT-z) 

    пример

     >>> z = np.array([[0.+0.j, 2.+1.j, -1.+4.j]]) >>> abs(zT-z) array([[ 0. , 2.23606798, 4.12310563], [ 2.23606798, 0. , 4.24264069], [ 4.12310563, 4.24264069, 0. ]]) 

    В качестве дополнения вы можете захотеть удалить дубликаты после этого, взяв верхний треугольник:

     >>> np.triu(out) array([[ 0. , 2.23606798, 4.12310563], [ 0. , 0. , 4.24264069], [ 0. , 0. , 0. ]]) 

    Некоторые контрольные показатели

     >>> timeit.timeit('abs(zT-z)', setup='import numpy as np;z = np.array([[0.+0.j, 2.+1.j, -1.+4.j]])') 4.645645342274779 >>> timeit.timeit('abs(z[..., np.newaxis] - z)', setup='import numpy as np;z = np.array([0.+0.j, 2.+1.j, -1.+4.j])') 5.049334864854522 >>> timeit.timeit('m, n = np.meshgrid(z, z); abs(mn)', setup='import numpy as np;z = np.array([0.+0.j, 2.+1.j, -1.+4.j])') 22.489568296184686 

    Вот как вы можете это сделать, используя numpy:

     import numpy as np x = np.array([0,1,2]) y = np.array([2,4,6]) # take advantage of broadcasting, to make a 2dim array of diffs dx = x[..., np.newaxis] - x[np.newaxis, ...] dy = y[..., np.newaxis] - y[np.newaxis, ...] dx => array([[ 0, -1, -2], [ 1, 0, -1], [ 2, 1, 0]]) # stack in one array, to speed up calculations d = np.array([dx,dy]) d.shape => (2, 3, 3) 

    Теперь все осталось вычислять L2-норму вдоль оси О (как обсуждалось здесь ):

     (d**2).sum(axis=0)**0.5 => array([[ 0. , 2.23606798, 4.47213595], [ 2.23606798, 0. , 2.23606798], [ 4.47213595, 2.23606798, 0. ]]) 

    Если вам не нужна полная матрица расстояния, вам будет лучше использовать kd-дерево. Рассмотрим scipy.spatial.cKDTree или sklearn.neighbors.KDTree . Это связано с тем, что kd-дерево kan находит k-ближайших соседей в O (n log n) времени, и поэтому вы избегаете сложности O (n ** 2) вычисления всех n на n расстояний.

    Python - лучший язык программирования в мире.