Эффективно вычислять средние пары расстояния в массиве ⇐ Python

[Anonymous]

Предположим, у нас есть наблюдения $ \ {y_i \} _ {i = 1}^{n} $ . Я хотел бы вычислить среднее парное расстояние, определенное:
$$ d = \ frac {1} {n^2} \ sum_ {i = 1}^{n} \ sum_ {j = 1}^{n} | y_i - y_j | $$ < /span>
Это вычисление выполняется неоднократно в цикле, поэтому важно оптимизировать его для скорости. In my application, each $y_i$ is an array of shape (n, p, k), where the final result of $D$ should be averaged across the first dimension - resulting in an array of shape (p, k).

Самый простой способ сделать это наивным для петли: < /p>

Код: Выделить всё

Y # Array of shape (n, p, k)
D = 0
for i in range(n):
for j in range(n):
D += np.abs(Y[i, :, :] - Y[j, :, :])
D = D / n**2
< /code>
Однако это, конечно, очень медленно. Мое текущее решение использует трансляцию/векторизацию формы и очень быстро: 
D = np.mean(
np.abs(
np.expand_dims(Y, axis=0) - np.expand_dims(Y, axis=1)
),
axis=[0,1]
)

Однако проблема, с которой я столкнулся, заключается в том, что я быстро попадаю в ошибки вне памяти, поскольку она требует хранения двух промежуточных результатов форм (n, n, p, k) . Например, если n = 100, p = 100, k = 300 < /code>, это уже два массива более 6 млн. Точек. < /P>

Любые предложения о том, как вычислить $ d $ < /span>, как более эффективно память, но и быстро? Можем ли мы переписать $ d $ каким-то образом с точки зрения статистики выборки?

Подробнее здесь: https://stackoverflow.com/questions/796 ... n-an-array