рассчитать расстояние от всех точек в массиве numpy до одной точки на основе индекса

Question

Предположим, что 2d-массив задан как:

arr = array([[1, 1, 1],
             [4, 5, 8],
             [2, 6, 9]])

если задано point=array([1,1]), тогда я хочу вычислить евклидово расстояние от всех индексов arr до точки (1,1). Результат должен быть

array([[1.41  , 1.        , 1.41],
       [1.    , 0.        , 1.  ],
       [1.41  , 1.        , 1.41]])

Поскольку l oop слишком медленный для выполнения этих вычислений. Есть ли более быстрый способ добиться этого с помощью numpy или scipy?

Спасибо !!!

Answer 1

Помимо хороших решений @ Divakar, если вы ищете что-то абстрактное, вы можете использовать:

np.linalg.norm(np.indices(arr.shape, sparse=True)-point)

Обратите внимание, что он работает с numpy 1.17+ (аргумент sparse добавляется в версии 1.17+ из numpy). Обновите свой numpy и наслаждайтесь. Если у вас более старая версия numpy, чем 1.17, вы можете добавить размеры к своему point, используя это:

np.linalg.norm(np.indices(arr.shape)-point[:,None,None], axis=0)

вывод для point=np.array([1,1]) и заданный массив:

[[1.41421356 1.         1.41421356]
 [1.         0.         1.        ]
 [1.41421356 1.         1.41421356]]

Answer 2

Подход №1

Вы можете использовать scipy.ndimage.morphology.distance_transform_edt -

def distmat(a, index):
    mask = np.ones(a.shape, dtype=bool)
    mask[index[0],index[1]] = False
    return distance_transform_edt(mask)

Подход №2

Другой с NumPy - собственными инструментами -

def distmat_v2(a, index):
    i,j = np.indices(a.shape, sparse=True)
    return np.sqrt((i-index[0])**2 + (j-index[1])**2)

Пробный прогон -

In [60]: a
Out[60]: 
array([[1, 1, 1],
       [4, 5, 8],
       [2, 6, 9]])

In [61]: distmat(a, index=[1,1])
Out[61]: 
array([[1.41421356, 1.        , 1.41421356],
       [1.        , 0.        , 1.        ],
       [1.41421356, 1.        , 1.41421356]])

In [62]: distmat_v2(a, index=[1,1])
Out[62]: 
array([[1.41421356, 1.        , 1.41421356],
       [1.        , 0.        , 1.        ],
       [1.41421356, 1.        , 1.41421356]])

Бенчмаркинг

Другие предлагаемые решения: 1023 *

# https://stackoverflow.com/a/61629292/3293881 @Ehsan
def norm_method(arr, point):
    point = np.asarray(point)
    return np.linalg.norm(np.indices(arr.shape, sparse=True)-point)

Использование пакета benchit (несколько инструментов тестирования собраны вместе; отказ от ответственности: я являюсь его автором) для тестирования предлагаемых решений.

In [66]: import benchit

In [76]: funcs = [distmat, distmat_v2, norm_method]

In [77]: inputs = {n:(np.random.rand(n,n),[1,1]) for n in [3,10,50,100,500,1000,2000,5000]}

In [83]: T = benchit.timings(funcs, inputs, multivar=True, input_name='Length')

In [84]: In [33]: T.plot(logx=True, colormap='Dark2', savepath='plot.png')

Итак, distmat_v2, похоже, работает очень хорошо. Мы можем улучшить его, используя numexpr.

---

Extend в массив индексов

Мы могли бы расширить перечисленные решения, чтобы охватить общий / больший случай списка / массива индексов, относительно которых нам нужно получить евклидовы расстояния в остальных позициях, например:

def distmat_indices(a, indices):
    indices = np.atleast_2d(indices)
    mask = np.ones(a.shape, dtype=bool)
    mask[indices[:,0],indices[:,1]] = False
    return distance_transform_edt(mask)

def distmat_indices_v2(a, indices):
    indices = np.atleast_2d(indices)
    i,j = np.indices(a.shape, sparse=True)
    return np.sqrt(((i-indices[:,0])[...,None])**2 + (j-indices[:,1,None])**2).min(1)

Пробный прогон -

In [143]: a = np.random.rand(4,5)

In [144]: distmat_indices(a, indices=[[2,2],[0,3]])
Out[144]: 
array([[2.82842712, 2.        , 1.        , 0.        , 1.        ],
       [2.23606798, 1.41421356, 1.        , 1.        , 1.41421356],
       [2.        , 1.        , 0.        , 1.        , 2.        ],
       [2.23606798, 1.41421356, 1.        , 1.41421356, 2.23606798]])