Поиск ближайшей точки к списку точек

Я пытаюсь найти ближайшую точку (евклидово расстояние) от введенной пользователем точки до списка из 50 000 пунктов, которые у меня есть. Обратите внимание, что список точек изменяется все время. и самое близкое расстояние зависит от того, когда и где пользователь нажимает на точку.

#find the nearest point from a given point to a large list of points

import numpy as np

def distance(pt_1, pt_2):
    pt_1 = np.array((pt_1[0], pt_1[1]))
    pt_2 = np.array((pt_2[0], pt_2[1]))
    return np.linalg.norm(pt_1-pt_2)

def closest_node(node, nodes):
    pt = []
    dist = 9999999
    for n in nodes:
        if distance(node, n) <= dist:
            dist = distance(node, n)
            pt = n
    return pt

a = []
for x in range(50000):
    a.append((np.random.randint(0,1000),np.random.randint(0,1000)))

some_pt = (1, 2)

closest_node(some_pt, a)
33 голоса | спросил dassouki 7 J000000Sunday13 2013, 00:19:34

2 ответа


26

Это будет, безусловно, быстрее, если вы векторизовать вычисления расстояния:

def closest_node(node, nodes):
    nodes = np.asarray(nodes)
    dist_2 = np.sum((nodes - node)**2, axis=1)
    return np.argmin(dist_2)

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

def closest_node(node, nodes):
    nodes = np.asarray(nodes)
    deltas = nodes - node
    dist_2 = np.einsum('ij,ij->i', deltas, deltas)
    return np.argmin(dist_2)

В идеале у вас уже будет свой список точек в массиве, а не в списке, что значительно ускорит процесс.

ответил Jaime 7 J000000Sunday13 2013, 03:25:23
16

Весь ваш код можно переписать как:

from numpy import random
from scipy.spatial import distance

def closest_node(node, nodes):
    closest_index = distance.cdist([node], nodes).argmin()
    return nodes[closest_index]

a = random.randint(1000, size=(50000, 2))

some_pt = (1, 2)

closest_node(some_pt, a)

Вы можете просто написать randint(1000) вместо randint(0, 1000), документацию randint говорит:

  

Если high - None (по умолчанию), то результаты получены из [0, low).

Вы можете использовать аргумент size для randint вместо цикла и двух вызовов функций. Итак:

a = []
for x in range(50000):
    a.append((np.random.randint(0,1000),np.random.randint(0,1000)))

становится:

a = np.random.randint(1000, size=(50000, 2))

Это также намного быстрее (двадцать раз быстрее в моих тестах).


Более того, scipy имеет модуль scipy.spatial.distance, который содержит cdist :

  

cdist(XA, XB, metric='euclidean', p=2, V=None, VI=None, w=None)

     

Вычисляет расстояние между каждой парой двух наборов входов.

Поэтому вычисление distance в цикле больше не требуется.

Вы также используете цикл for, чтобы найти положение минимума, но это можно сделать с помощью argmin метод объекта ndarray.

Следовательно, ваша функция closest_node может быть определена просто как:

from scipy.spatial.distance import cdist

def closest_node(node, nodes):
    return nodes[cdist([node], nodes).argmin()]

Я сравнивал время выполнения всех функций closest_node, определенных в этом вопросе:

Original:
1 loop, best of 3: 1.01 sec per loop

Jaime v1:
100 loops, best of 3: 3.32 msec per loop

Jaime v2:
1000 loops, best of 3: 1.62 msec per loop

Mine:
100 loops, best of 3: 2.07 msec per loop

Все векторизованные функции выполняются в сотни раз быстрее, чем исходное решение.

cdist превосходит только вторую функцию Хайме, но только незначительно. Конечно, cdist является самым простым.

ответил arekolek 15 J000000Friday16 2016, 01:58:57

Похожие вопросы

Популярные теги

security × 330linux × 316macos × 2827 × 268performance × 244command-line × 241sql-server × 235joomla-3.x × 222java × 189c++ × 186windows × 180cisco × 168bash × 158c# × 142gmail × 139arduino-uno × 139javascript × 134ssh × 133seo × 132mysql × 132