Python-計算矩陣每個單元格之間曼哈頓距離的有效方法？

我正在嘗試使用 Python在以下矩陣中找到從一個單元格w的值到另一個單元格的值的最小躍點數。vX

有沒有一種有效的方法來做到這一點？

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

我嘗試按如下方式實作它，但它似乎很慢。

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

有沒有辦法加快這個計算？

uj5u.com熱心網友回復：

使用cdist計算所有成對距離，找到價值指數使用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))

輸出

1.0
1.0
2.0
4.0

uj5u.com熱心網友回復：

只需添加不同矩陣大小的時間即可向 OP 表明 @Dani Mesejo 的答案確實要快得多。對于小矩陣，差異當然很小。

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


def manhattan_distance_ugen(X, 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


def gen_data(matrix_size):
    return np.random.randint(0, matrix_size, (matrix_size, matrix_size), dtype=np.int32)

for matrix_size in [5, 50, 500]:
    print('Matrix size: {}'.format(matrix_size))
    X = gen_data(matrix_size)
    print('ugen: ', timeit.timeit("manhattan_distance_ugen(X, np.random.randint(0, matrix_size), np.random.randint(0, matrix_size))",
                        "from __main__ import manhattan_distance_ugen, X, matrix_size; import numpy as np",
                        number=10))
    print('dani masejo: ', timeit.timeit("manhattan_distance_dani_masejo(X, np.random.randint(0, matrix_size), np.random.randint(0, matrix_size))",
                        "from __main__ import manhattan_distance_dani_masejo, X, matrix_size; import numpy as np",
                        number=10))

結果：

Matrix size: 5
ugen:  0.0019634239999999914
dani masejo:  0.0006071939999999776
Matrix size: 50
ugen:  0.093326557
dani masejo:  0.0008874660000000034
Matrix size: 500
ugen:  9.112327058
dani masejo:  0.027754558000001595

標籤：Python 表现 麻木的 启发式

上一篇：使用numpy避免3個for回圈以獲得更高效的代碼

下一篇：基于語言環境的Nuxt構建速度非常慢