[FIXED] Python - Efficient way to calculate the Manhattan distance between each cell of a matrix?

Issue

I am trying to find the minimum number of hops to get from the value of one cell w to the value of another cell v in the following matrix X using Python.

Is there an efficient way to do this?

import numpy as np
from numpy.typing import NDArray 


def manhattan_distance(X: NDArray[int], w: int, v: int) -> int:
     # something
     return distance
    

X = np.array([
    [1, 2, 2, 3, 3],
    [1, 2, 2, 4, 4],
    [5, 5, 6, 6, 6],
    [7, 8, 9, 9, 9],
    [10, 10, 10, 10, 10],
]).astype(np.int_)


# Expected result
manhattan_distance(X, 1, 2) # ①
-> 1
manhattan_distance(X, 2, 3) # ②
-> 1
manhattan_distance(X, 3, 6) # ③
-> 2
manhattan_distance(X, 3, 5) # ④
-> 4

I tried to implement it as follows, but it seems to be quite slow.

import numpy as np
from numpy.typing import NDArray 

def manhattan_distance(X: NDArray[int], w: int, v: int) -> int:
    xx, yy = np.where(X == w)
    xx_, yy_ = np.where(X == v)
    distance = int(min_dist(xx, xx_) + min_dist(yy, yy_))
    return distance
  
def min_dist(xx, xx_):
    min_dist = np.inf
    for i in xx:
        for j in xx_:
            dist = np.sqrt((i - j)**2)
            min_dist = dist if dist < min_dist else min_dist
    return min_dist

Is there any way to speed this calculation up?

Solution

Use cdist to compute all pairwise distances, to find the values' indices use np.argwhere

from scipy.spatial.distance import cdist
import numpy as np
from numpy.typing import NDArray

X = np.array([
    [1, 2, 2, 3, 3],
    [1, 2, 2, 4, 4],
    [5, 5, 6, 6, 6],
    [7, 8, 9, 9, 9],
    [10, 10, 10, 10, 10],
]).astype(np.int32)


def manhattan_distance(X: NDArray[int], w: int, v: int) -> int:
    return cdist(np.argwhere(X == w), np.argwhere(X == v), "cityblock").min()


print(manhattan_distance(X, 1, 2))
print(manhattan_distance(X, 2, 3))
print(manhattan_distance(X, 3, 6))
print(manhattan_distance(X, 3, 5))

Output

1.0
1.0
2.0
4.0

Answered By - Dani Mesejo