Recording Smallest-So-Far Values in NumPy Array

user_2955541 0
Viewed 103

Let's say I have a NumPy array like:

import numpy as np

x = np.array([1, 5, 4, 2, 3, 6, 7, 5, np.inf, np.inf, np.inf, 4, 2, 8, 3, 5, 9, 2, 3, 4])

And starting at i = 9, I want to traverse each element toward i = 0 and then to record the "smallest-so-far" numbers along the way along with the index of those numbers. In this example:

left_val = []
left_idx = []
min_so_far = np.inf
for i in range(9, -1, -1):
    if x[i] < min_so_far:
        left_val.append(x[i])
        left_idx.append(i)
        min_so_far = x[i]

The left min-so-far values are [5, 3, 2, 1] and they are located at indices [7, 4, 3, 0].

You can also traverse toward the right:

right_val = []
right_idx = []
min_so_far = np.inf
for i in range(9, x.shape[0]):
    if x[i] < min_so_far:
        right_val.append(x[i])
        right_idx.append(i)
        min_so_far = x[i]

The right min-so-far values are [4, 2] and they are located at index [11, 12]

Is there a faster way to do this min_so_far search when the length of x is much larger?

numpy arrays python
2 Answers

You can do something like this:

def right_mins(x):
    # To avoid leading infs, truncate some more
    start = np.argmax(np.isfinite(x))
    y = np.minimum.accumulate(x[start:])
    idx = np.r_[0, np.flatnonzero(np.diff(y)) + 1] + start
    return x[idx], idx

def left_mins(x):
    y, idx = right_mins(x[::-1])
    return y, x.size - 1 - idx

You can apply these functions directly to the slices that you want, e.g.:

>>> left_mins(x[:10])
(array([5., 3., 2., 1.]), array([7, 4, 3, 0]))
>>> n, i = right_mins(x[9:])
>>> n, i + 9
(array([4., 2.]), array([11, 12]))
user_29887300

This isn't quite what you want, but it'll give you minima for all sublists as you traverse the array. It's pythonic but it'll be slow for reasonably sized numpy arrays.

right_going = [min(x[n:i]) for i in range(n, len (x))]
left_going = [min(x[(n-i):n]) for i in range(n)]

the array index at which values are minima is then n + list_index in the first case and just the index of the list in the second case. You could then do exactly what you want by getting the indices and values of the first (or last) occurrence of repeat values in these lists.

user_8753430
Related