Recording Smallest-So-Far Values in NumPy Array

Question

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?

Can you clarify what your expected output would be? Because your current gets a single value and its index, but your explanation seems to imply several values being in the output. — Henry Ecker
– Henry Ecker ♦, Commented May 22, 2021 at 17:46

Mad Physicist · Accepted Answer · 2022-01-18 17:10:46Z

2

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]))

edited Jan 18, 2022 at 17:10

answered May 22, 2021 at 18:33

Mad Physicist

116k29 gold badges202 silver badges292 bronze badges

Sign up to request clarification or add additional context in comments.

9 Comments

slaw Over a year ago

Maybe I'm misunderstanding something but left_mins(x) appears to only return (array([1.]), array([0])) when I supply the same x as in the question. Instead, left_mins needs to return (array([5, 3, 2, 1]), array([7, 4, 3, 0])).

Tls Chris Over a year ago

@slaw The functions need to be applied to the relevant section of the array. right_mins( [x[:10] ) and left_mins( [ x[10:] ). Both then need the inf values and corresponding indices removing. np.inf is the min when it's first found.

Mad Physicist Over a year ago

@slaw. I've added a couple of examples showing how to run your exact use-cases. If you want to subset the array, you need to add the offset of the leftmost index to the result

Mad Physicist Over a year ago

@slaw. Do you have a particular usecase for the edit you suggested? Let's discuss before you modify the code.

CJR Over a year ago

idx = np.insert(y[1:] != y[:-1], 0, True) and return x[idx], np.where(idx)[0] also an option to avoid > comparisons which might not be well-defined.

|

shortorian · Accepted Answer · 2021-05-22 18:10:52Z

0

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.

edited May 22, 2021 at 18:10

answered May 22, 2021 at 17:51

shortorian

1,2221 gold badge13 silver badges22 bronze badges

3 Comments

Mad Physicist Over a year ago

Pythonic maybe, but certainly not numpythonic

hpaulj Over a year ago

@MadPhysicist, given the sequential nature of this problem, "numpythonic" (ugg!) may not be possible. np.minimum.accumulate gets the minimum of various ranges, but I don't think there's an accumulate version of argmin.

Mad Physicist Over a year ago

@hpaulj. I've posted an answer with a pretty vectorized solution. Sure there's no argmin.accumulate, but the usual diff trick works just fine after minimum.accumulate

Collectives™ on Stack Overflow

Recording Smallest-So-Far Values in NumPy Array

2 Answers 2

9 Comments

3 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

9 Comments

3 Comments

Your Answer

Sign up or log in

Post as a guest

Related