get the index of the last negative value in a 2d array per column

Question

I'm trying to get the index of the last negative value of an array per column (in order to slice it after). a simple working example on a 1d vector is :

import numpy as np

A = np.arange(10) - 5
A[2] = 2
print A # [-5 -4  2 -2 -1  0  1  2  3  4]

idx = np.max(np.where(A <= 0)[0])
print idx # 5

A[:idx] = 0
print A # [0 0 0 0 0 0 1 2 3 4]

Now I wanna do the same thing on each column of a 2D array :

A = np.arange(10) - 5
A[2] = 2
A2 = np.tile(A, 3).reshape((3, 10)) - np.array([0, 2, -1]).reshape((3, 1))
print A2
# [[-5 -4  2 -2 -1  0  1  2  3  4]
#  [-7 -6  0 -4 -3 -2 -1  0  1  2]
#  [-4 -3  3 -1  0  1  2  3  4  5]]

And I would like to obtain :

print A2
# [[0 0 0 0 0 0 1 2 3 4]
#  [0 0 0 0 0 0 0 0 1 2]
#  [0 0 0 0 0 1 2 3 4 5]]

but I can't manage to figure out how to translate the max/where statement to the this 2d array...

Answer 1

You already have good answers, but I wanted to propose a potentially quicker variation using the function np.maximum.accumulate. Since your method for a 1D array uses max/where, you may also find this approach quite intuitive. (Edit: quicker Cython implementation added below).

The overall approach is very similar to the others; the mask is created with:

np.maximum.accumulate((A2 < 0)[:, ::-1], axis=1)[:, ::-1]

This line of code does the following:

• (A2 < 0) creates a Boolean array, indicating whether a value is negative or not. The index [:, ::-1] flips this left-to-right.

• np.maximum.accumulate is used to return the cumulative maximum along each row (i.e. axis=1). For example [False, True, False] would become [False, True, True].

• The final indexing operation [:, ::-1] flips this new Boolean array left-to-right.

Then all that's left to do is to use the Boolean array as a mask to set the True values to zero.

---

Borrowing the timing methodology and two functions from @Divakar's answer, here are the benchmarks for my proposed method:

# method using np.maximum.accumulate
def accumulate_based(A2):
    A2[np.maximum.accumulate((A2 < 0)[:, ::-1], axis=1)[:, ::-1]] = 0
    return A2

# large sample array
A2 = np.random.randint(-4, 10, size=(100000, 100))
A2c = A2.copy()
A2c2 = A2.copy()

The timings are:

In [47]: %timeit broadcasting_based(A2)
10 loops, best of 3: 61.7 ms per loop

In [48]: %timeit cumsum_based(A2c)
10 loops, best of 3: 127 ms per loop

In [49]: %timeit accumulate_based(A2c2) # quickest
10 loops, best of 3: 43.2 ms per loop

So using np.maximum.accumulate can be as much as 30% faster than the next fastest solution for arrays of this size and shape.

---

As @tom10 points out, each NumPy operation processes arrays in their entirety, which can be inefficient when multiple operations are needed to get a result. An iterative approach which works through the array just once may fare better.

Below is a naive function written in Cython which could more than twice as fast as a pure NumPy approach.

This function may be able to be sped up further using memory views.

cimport cython
import numpy as np
cimport numpy as np

@cython.boundscheck(False)
@cython.wraparound(False)
@cython.nonecheck(False)
def cython_based(np.ndarray[long, ndim=2, mode="c"] array):
    cdef int rows, cols, i, j, seen_neg
    rows = array.shape[0]
    cols = array.shape[1]
    for i in range(rows):
        seen_neg = 0
        for j in range(cols-1, -1, -1):
            if seen_neg or array[i, j] < 0:
                seen_neg = 1
                array[i, j] = 0
    return array

This function works backwards through each row and starts setting values to zero once it has seen a negative value.

Testing it works:

A2 = np.random.randint(-4, 10, size=(100000, 100))
A2c = A2.copy()

np.array_equal(accumulate_based(A2), cython_based(A2c))
# True

Comparing the performance of the function:

In [52]: %timeit accumulate_based(A2)
10 loops, best of 3: 49.8 ms per loop

In [53]: %timeit cython_based(A2c)
100 loops, best of 3: 18.6 ms per loop

Answer 2

Finding the first is usually easier and faster than finding the last, so here I reverse the array and then find the first negative (using the OP's version of A2):

im = A2.shape[1] - 1 - np.argmax(A2[:,::-1]<0, axis=1)

# [4 6 3]      # which are the indices of the last negative in A2

---

Also, though, note that if you have large arrays with many negative numbers, it might actually be faster to use a non-numpy approach so you can short circuit the search. That is, numpy will do the calculation on the entire array, so if you have 10000 elements in a row but typically will hit a negative number in the first 10 elements (of a reverse search), a pure Python approach might end up being faster.

Overall, iterating the rows might be faster for subsequent operations as well. For example, if your next step is multiplication, it could be faster to just multiply the slices at the ends that are non-zeros, or maybe find that longest non-zero section and just deal with the truncated array.

This basically comes down to number of negatives per row. If you have 1000 negatives per row you'll on average have non-zeros segments that are 1/1000th of your full row length, so you could get a 1000x speed-up by just looking at the ends. The short example given in the question is great for understanding and answering the basic question, but I wouldn't take timing tests too seriously when your end application is a very different use case; especially since your fractional time savings by using iteration improves in proportion to array size (assuming a constant ratio and random distribution of negative numbers).

Answer 3

Assuming that you are looking to set all elements for each row until the last negative element to be set to zero (as per the expected output listed in the question for a sample case), two approaches could be suggested here.

Approach #1

This one is based on np.cumsum to generate a mask of elements to be set to zeros as listed next -

# Get boolean mask with TRUEs for each row starting at the first element and 
# ending at the last negative element
mask = (np.cumsum(A2[:,::-1]<0,1)>0)[:,::-1]

# Use mask to set all such al TRUEs to zeros as per the expected output in OP 
A2[mask] = 0

Sample run -

In [280]: A2 = np.random.randint(-4,10,(6,7)) # Random input 2D array

In [281]: A2
Out[281]: 
array([[-2,  9,  8, -3,  2,  0,  5],
       [-1,  9,  5,  1, -3, -3, -2],
       [ 3, -3,  3,  5,  5,  2,  9],
       [ 4,  6, -1,  6,  1,  2,  2],
       [ 4,  4,  6, -3,  7, -3, -3],
       [ 0,  2, -2, -3,  9,  4,  3]])

In [282]: A2[(np.cumsum(A2[:,::-1]<0,1)>0)[:,::-1]] = 0 # Use mask to set zeros

In [283]: A2
Out[283]: 
array([[0, 0, 0, 0, 2, 0, 5],
       [0, 0, 0, 0, 0, 0, 0],
       [0, 0, 3, 5, 5, 2, 9],
       [0, 0, 0, 6, 1, 2, 2],
       [0, 0, 0, 0, 0, 0, 0],
       [0, 0, 0, 0, 9, 4, 3]])

Approach #2

This one starts with the idea of finding the last negative element indices from @tom10's answer and develops into a mask finding method using broadcasting to get us the desired output, similar to approach #1.

# Find last negative index for each row
last_idx = A2.shape[1] - 1 - np.argmax(A2[:,::-1]<0, axis=1)

# Find the invalid indices (rows with no negative indices)
invalid_idx = A2[np.arange(A2.shape[0]),last_idx]>=0

# Set the indices for invalid ones to "-1"
last_idx[invalid_idx] = -1

# Boolean mask with each row starting with TRUE as the first element 
# and ending at the last negative element
mask = np.arange(A2.shape[1]) < (last_idx[:,None] + 1)

# Set masked elements to zeros, for the desired output
A2[mask] = 0

---

Runtime tests -

Function defintions:

def broadcasting_based(A2):
    last_idx = A2.shape[1] - 1 - np.argmax(A2[:,::-1]<0, axis=1)
    last_idx[A2[np.arange(A2.shape[0]),last_idx]>=0] = -1
    A2[np.arange(A2.shape[1]) < (last_idx[:,None] + 1)] = 0
    return A2

def cumsum_based(A2):    
    A2[(np.cumsum(A2[:,::-1]<0,1)>0)[:,::-1]] = 0    
    return A2

Runtimes:

In [379]: A2 = np.random.randint(-4,10,(100000,100))
     ...: A2c = A2.copy()
     ...: 

In [380]: %timeit broadcasting_based(A2)
10 loops, best of 3: 106 ms per loop

In [381]: %timeit cumsum_based(A2c)
1 loops, best of 3: 167 ms per loop

Verify results -

In [384]: A2 = np.random.randint(-4,10,(100000,100))
     ...: A2c = A2.copy()
     ...: 

In [385]: np.array_equal(broadcasting_based(A2),cumsum_based(A2c))
Out[385]: True