python - 使用 Python 移动最小值

Question

代码计算每一行的最小值，并通过扫描同一行和下一行的附近元素来选择下一个最小值。相反，我希望代码从第一行的最小值开始，然后通过扫描附近的元素来进行。我不希望它计算每一行的最小值。附上输出。

import numpy as np
from scipy.ndimage import minimum_filter as mf

Pe = np.random.rand(5,5) 



b = np.zeros((Pe.shape[0], 2))

#the footprint of the window, i.e., we do not consider the value itself or value in the row above
ft = np.asarray([[0, 0, 0],
                 [1, 0, 1],
                 [1, 1, 1]])
#applying scipy's minimum filter
#mode defines what should be considered as values at the edges
#setting the edges to INF
Pe_min = mf(Pe, footprint=ft, mode="constant", cval=np.inf)

#finding rowwise index of minimum value
idx = Pe.argmin(axis=1)

#retrieving minimum values and filtered values
b[:, 0] = np.take_along_axis(Pe, idx[None].T, 1).T[0]
b[:, 1] = np.take_along_axis(Pe_min, idx[None].T, 1).T[0]

print(b)

当前输出:

期望的输出:

Answer 1

您可以使用一个简单的 while 循环来解决这个问题:对于给定的当前位置，循环的每一步都会遍历邻域以在所有有效的下一个位置中找到最小值，然后更新/写吧。

由于这在纯 Numpy 中效率很低，您可以使用 Numba 以便代码可以高效执行。这是实现:

import numpy as np
import numba as nb

Pe = np.random.rand(5,5)
# array([[0.58268917, 0.99645225, 0.06229945, 0.5741654 , 0.41407074],
#        [0.4933553 , 0.93253261, 0.1485588 , 0.00133828, 0.09301049],
#        [0.49055436, 0.53794993, 0.81358814, 0.25031136, 0.76174586],
#        [0.69885908, 0.90878292, 0.25387689, 0.25735301, 0.63913838],
#        [0.33781117, 0.99406778, 0.49133067, 0.95026241, 0.14237322]])

@nb.njit('int_[:,:](float64[:,::1])', boundscheck=True)
def minValues(arr):
    n, m = arr.shape
    assert n >= 1 and m >= 2
    res = []
    i, j = 0, np.argmin(arr[0,:])
    res.append((i, j))
    iPrev = jPrev = -1
    while iPrev < n-1:
        cases = [(i, j-1), (i, j+1), (i+1, j-1), (i+1, j), (i+1, j+1)]
        minVal = np.inf
        iMin = jMin = -1
        # Find the best candidate (smalest value)
        for (i2, j2) in cases:
            if i2 == iPrev and j2 == jPrev: # No cycles
                continue
            if i2 < 0 or i2 >= n or j2 < 0 or j2 >= m: # No out-of-bounds
                continue
            if arr[i2, j2] < minVal:
                iMin, jMin = i2, j2
                minVal = arr[i2, j2]
        assert not np.isinf(minVal)
        # Store it and update the values
        res.append((iMin, jMin))
        iPrev, jPrev = i, j
        i, j = iMin, jMin
    return np.array(res)

minValues(Pe)
# array([[0, 2],
#        [1, 3],
#        [1, 4],
#        [2, 3],
#        [3, 2],
#        [3, 3],
#        [4, 4],
#        [4, 3]], dtype=int32)

该算法相对较快，因为它成功地在形状为 (100_000, 1_000) 的 Pe 数组中找到长度为 141_855 的路径的结果，仅需 15 毫秒在我的机器上(虽然它可以优化)。仅使用 CPython(即没有 Numba JIT)的相同代码需要 591 毫秒。