Как я могу оптимизировать расстояние между 2 точками (x, y, z) и двумя массивами

Question

Мне нужно рассчитать расстояние между каждым пикселем и каждым центроидом.

Аргументы:

• X (numpy массив): PxD 1-й набор точек данных (обычно данные точки)
• C (* массив 1019 *): KxD 2-й набор точек данных (обычно точки центроидов кластера)

Возвращает:

• dist: PxK numpy позиция массива ij - это расстояние между i-й точкой первого набора и j-й точкой второго набора

def distance(X, C):

    dist = numpy.empty((X.shape[0], C.shape[0]))

    for i,x in enumerate(X):
        for y,c in enumerate(C):
            dist[i][y] = euclidean_dist(x,c)

    return dist

def euclidean_dist(x, y):
    x1, y1, z1 = x
    x2, y2, z2 = y
    return math.sqrt((x1-x2)**2 + (y1-y2)**2 + (z1-z2)**2)

Answer 1

Если вы можете добавить зависимость scipy, то это уже реализовано в scipy.spatial.distance.cdist . В противном случае мы можем использовать numpy .broadcasting и numpy .linalg.norm :

Реализация Scipy

from scipy.spatial import distance
distance.cdist(X, C, 'euclidean')

Numpy Реализация

import numpy as np
np.linalg.norm(X[:,None,:] - C, axis=2)

Производительность

P = 100_000
K = 10_00
D = 3

X = np.random.randint(0,10, (P,D))
C = np.random.randint(0,10, (K,D))

%timeit distance.cdist(X, C, 'euclidean')
1.06 s ± 57 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

%timeit np.linalg.norm(X[:,None,:] - C, axis=2)
15 s ± 2.18 s per loop (mean ± std. dev. of 7 runs, 1 loop each)

Мы видим, что для больших размеров X и C Реализация scipy намного быстрее.