Маленькие массивы
Для двух массивов x и y формы (n,) и (m,), соответственно, вы можете векторизовать вычисления расстояния и затем получить минимальное расстояние:
import numpy as np
n = 10
m = 20
x = np.random.random(n)
y = np.random.random(m)
# Using squared distance matrix and taking the
# square root at the minimum value
distance_matrix = (x[:,None]-y[None,:])**2
minimum_distance_sum = np.sum(np.sqrt(np.min(distance_matrix, axis=1)))
Для массивов формы (n,l) и (m,l) вам просто нужно вычислить distance_matrix как:
distance_matrix = np.sum((x[:,None]-y[None,:])**2, axis=2)
В качестве альтернативы вы можете использовать np.linalg.norm, scipy.spatial.distance.cdist, np.einsum и т. Д., Но во многих случаях они не быстрее.
Большие массивы
Если значения l, n и m выше слишком велики для того, чтобы вы могли хранить в памяти distance_matrix, вы можете использовать математическую нижнюю и верхнюю границу евклидова расстояния, чтобы увеличить скорость (см. этот документ . Так как он основан на циклах, он будет очень медленным, но можно обернуть функции с помощью numba, чтобы противостоять этому:
import numpy as np
import numba
@numba.jit(nopython=True, fastmath=True)
def get_squared_distance(a,b):
return np.sum((a-b)**2)
def get_minimum_distance_sum(x,y):
n = x.shape[0]
m = y.shape[0]
l = x.shape[1]
# Calculate mean and standard deviation of both arrays
mx = np.mean(x, axis=1)
my = np.mean(y, axis=1)
sx = np.std(x, axis=1)
sy = np.std(y, axis=1)
return _get_minimum_distance_sum(x,y,n,m,l,mx,my,sx,sy)
@numba.jit(nopython=True, fastmath=True)
def _get_minimum_distance_sum(x,y,n,m,l,mx,my,sx,sy):
min_distance_sum = 0
for i in range(n):
min_distance = get_squared_distance(x[i], y[0])
for j in range(1,m):
if i == 0 and j == 0:
continue
lower_bound = l * ((mx[i] - my[j])**2 + (sx[i] - sy[j])**2)
if lower_bound >= min_distance:
continue
distance = get_squared_distance(x[i], y[j])
if distance < min_distance:
min_distance = distance
min_distance_sum += np.sqrt(min_distance)
return min_distance_sum
def test_minimum_distance_sum():
# Will likely be much larger for this to be faster than the other method
n = 10
m = 20
l = 100
x = np.random.random((n,l))
y = np.random.random((m,l))
return get_minimum_distance_sum(x,y)
Этот подход должен быть быстрее, чем прежний подход с увеличенным размером массива. Алгоритм может быть немного улучшен, как описано в статье, но любое ускорение будет сильно зависеть от формы массивов.
Задержка
На моем ноутбуке на двух массивах формы (1000,100) ваш подход занимает ~ 1 мин, подход "маленьких массивов" занимает 690 мс, а подход "больших массивов" занимает 288 мс. Для двух массивов формы (100, 3) ваш подход занимает 28 мс, подход "маленьких массивов" - 429 мкс, а подход "больших массивов" - 578 мкс.