CODEWITHSUNDEEP
pythonnumpyindexingmaxcumulative-sum
O.rka
O.rka

Reputation: 30717

How to get accumulative maximum indices with numpy in Python?

I'm trying to get x and y coordinates of all cumulative maximums in a vector. I wrote a naive for-loop but I have a feeling there is some way to do it with numpy that's more elegant.

Does anyone know of any functions, masking-technique, or one-liners in numpy that can do this?

The details should be described by the plot below:

# Generate data
x = np.abs(np.random.RandomState(0).normal(size=(100)))
y = np.linspace(0,1,x.size)
z = x*y

# Get maximiums
idx_max = list()
val_max = list()

current = 0
for i,v in enumerate(z):
    if v > current:
        idx_max.append(i)
        val_max.append(v)
        current = v

# Plot them
with plt.style.context("seaborn-white"):
    fig, ax = plt.subplots(figsize=(10,3), ncols=2)
    ax[0].plot(z)
    ax[1].plot(z, alpha=0.618)
    ax[1].scatter(idx_max, val_max, color="black", edgecolor="maroon", linewidth=1.618)

enter image description here

Upvotes: 6

Views: 1419

Answers (2)

Fernando Gomes
Fernando Gomes

Reputation: 21

I've been facing this same question for some time and the answer was still not satisfactory for the problem I needed to solve, because I needed the respective indices of the maximum values accumulated in an array with the same shape. That is, if a certain maximum value were to repeat n times, it would need n positions with that index value. My alternative answer follows:

# create sample array
a = np.array([5,4,8,1,4,9,5,3])

# generate index for the array
idx = np.indices(a.shape)

# calculate accumulate maximum values and
# the number of repetitions of that
acc = np.maximum.accumulate(a)
_, repeats = np.unique(acc, return_counts=True)

# relating the closest value to the indx with boolean values
close  = np.isclose(a, acc)

# this generate an array with 3 elements,
idx[0, close]

# but the original has 8
# so, we are able to repeat the max indices as simpla as this
np.repeat(idx[0, close], repeats)

# array([0, 0, 2, 2, 2, 5, 5, 5])

Upvotes: 0

Divakar
Divakar

Reputation: 221614

We could make use of np.maximum.accumulate -

idx_max = np.flatnonzero(np.isclose(np.maximum.accumulate(z),z))[1:]
val_max = z[idx_max]

The basic idea being that this accumulative max value when compared with the current element indicates which are the element positions responsible for "uplifting" the running max value. The responsible ones are the indices that we need as idx_max. Since, we are working with floating-pt numbers, we need to incorporate some tolerance with that np.isclose.

That [1:] part is because the starting current value was 0 and so was z[0]. So, that v > current part won't append that starting index into output. To be precisely correct about it, it should had been -

current = 0
idx = np.flatnonzero(np.isclose(np.maximum.accumulate(z),z))
idx = idx[z[idx] > current]

But, given the starting values, the assumption made earlier keeps our code easier/compact/short.

Upvotes: 6

Related Questions