Проверка неравенства треугольника в массивной матрице NumPy

Question

У меня есть симметричная матрица NumPy D неотрицательных чисел с плавающей точкой. Число в строке i и столбце j представляют расстояние между объектами i и j, какими бы они ни были. Матрица большая (~ 10000 строк / столбцов). Я хотел бы проверить, подчиняются ли все расстояния в матрице неравенству треугольника, то есть: D[i,j]<=D[i,k]+D[k,j] для всех i, j, k.

Проблема может быть решена весьма неэффективно с помощью тройного вложенного цикла. Но есть ли более быстрое векторизованное решение?

Answer 1

Вы, конечно, можете легко векторизовать самый внутренний цикл с помощью (не проверено):

for i in range(N):
    for j in range(i):
        assert all(D[i,j] <= D[i,:] + D[:,j])

Для двойной векторизации вы можете просмотреть k (также не проверено):

for k in range(N):
    row = D[k,:].reshape(1, N)
    col = D[:,k].reshape(N, 1)
    assert all(D <= row + col)

(row + col генерирует квадратную матрицу того же размера, что и D)