使用Python移动最小值 [英] Shifting minimum values using Python

问题描述

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

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)

当前输出：

所需输出：

推荐答案

您可以使用一个简单的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)

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

这篇关于使用Python移动最小值的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！