Shifting minimum values using Python

Question

The code calculates the minimum value at each row and picks the next minimum by scanning the nearby element on the same and the next row. Instead, I want the code to start with minimum value of the first row and then progress by scanning the nearby elements. I don't want it to calculate the minimum value for each row. The outputs are attached.

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)

Present Output:

Desired Output:

Answer 1

You can solve this using a simple while loop: for a given current location, each step of the loop iterates over the neighborhood to find the smallest value amongst all the valid next locations and then update/write it.

Since this can be pretty inefficient in pure Numpy, you can use Numba so the code can be executed efficiently. Here is the implementation:

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)

The algorithm is relatively fast as it succeeds to find the result of a path of length 141_855 in a Pe array of shape (100_000, 1_000) in only 15 ms on my machine (although it can be optimized). The same code using only CPython (ie. without the Numba JIT) takes 591 ms.