ускорить поиск ближайших точек и сортировку их в питоне - PullRequest
Новая
       26

ускорить поиск ближайших точек и сортировку их в питоне

0 голосов
/ 18 марта 2019

У меня есть N точек в 2D-пространстве (N строка, 2 столбца), и я хочу найти ближайшие k точек для каждой точки (x_n,y_n) в наборе точек, а затем отсортировать их.Вот коды для этой цели.Я хочу ускорить следующие коды: 

def nearst_sort(x,y,k):
    N = len(x)    
    A = np.zeros((N,k))
    R = np.zeros((N,N))
    R = (x - x[np.newaxis].transpose())**2 + (y -y[np.newaxis].transpose())**2
    ix = np.argsort(R, kind='stable')
    ix = ix.transpose()
    A=ix[0:k,:].transpose()
    return A

Мой пример данных выглядит следующим образом: 

x   y
0   0
0   0.5
0   1
0.5 0
0.5 0.5
0.5 1
1   0
1   0.5
1   1

Я также пробовал функции из scipy.spatial.KDTree, но не смог получить хорошийРезультаты.Любая помощь будет оценена.

1 Ответ

0 голосов
/ 18 марта 2019

Для меня KDTree намного быстрее: 

>>> import numpy as np
>>> from scipy.spatial import cKDTree as KDTree
>>> from timeit import timeit
>>> 
>>> z = np.random.randn(1000, 2)
>>> k = 5
>>> 
>>> KDTree(z).query(z, k)
(array([[0.        , 0.21130505, 0.22903208, 0.32009477, 0.38000444],
       [0.        , 0.03969915, 0.06698214, 0.08423566, 0.10740011],
       [0.        , 0.04964421, 0.08194808, 0.11576068, 0.12022531],
       ...,
       [0.        , 0.00721785, 0.03346301, 0.03617199, 0.04193239],
       [0.        , 0.05147871, 0.05619545, 0.08028866, 0.08744349],
       [0.        , 0.03733766, 0.06359033, 0.06861222, 0.0698981 ]]), array([[  0, 391, 134, 462, 575],
       [  1,  87, 879, 846, 122],
       [  2, 793, 314, 564, 483],
       ...,
       [997, 390, 432, 165, 952],
       [998, 194, 457, 775, 629],
       [999, 158, 522, 862, 791]]))
>>> nearst_sort(*z.T, k)
array([[  0., 391., 134., 462., 575.],
       [  1.,  87., 879., 846., 122.],
       [  2., 793., 314., 564., 483.],
       ...,
       [997., 390., 432., 165., 952.],
       [998., 194., 457., 775., 629.],
       [999., 158., 522., 862., 791.]])
>>> timeit(lambda: KDTree(z).query(z, k), number=100)
0.12790076900273561
>>> timeit(lambda: nearst_sort(*z.T, k), number=100)
6.5285790269990684

Это 50-кратный коэффициент. Может зависеть от примера.

...