获取每列2d数组中最后一个负值的索引

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 :

我正在尝试获取每列数组的最后一个负值的索引（以便在之后对其进行切片）。 1d向量上的一个简单的工作示例是：

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 :

现在我想在2D数组的每一列上做同样的事情：

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...

但我无法弄清楚如何将max / where语句转换为这个2d数组...

4 个解决方案

#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).

您已经有了很好的答案，但我想使用函数np.maximum.accumulate建议一个更快的变化。由于您的1D阵列方法使用max / where，您可能也会发现这种方法非常直观。 （编辑：下面添加的更快的Cython实现）。

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.

  （A2 <0）创建一个布尔数组，指示值是否为负数。索引[：，:: - 1]从左到右翻转。

• 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].

  np.maximum.accumulate用于返回沿每行的累积最大值（即，轴= 1）。例如[False，True，False]将变为[False，True，True]。

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

  最终的索引操作[：，:: - 1]从左到右翻转这个新的布尔数组。

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

然后剩下要做的就是使用布尔数组作为掩码将True值设置为零。

---

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

借用时间方法和@Divakar的答案中的两个函数，这里是我提出的方法的基准：

# 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.

因此，对于这种尺寸和形状的阵列，使用np.maximum.accumulate可以比下一个最快的解决方案快30％。

---

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.

正如@ tom10指出的那样，每个NumPy操作都完整地处理数组，当需要多个操作来获得结果时，这可能是低效的。只需一次通过阵列的迭代方法可能会更好。

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

下面是一个用Cython编写的简单函数，其速度可能是纯NumPy方法的两倍。

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

#2

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

方法＃1

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

这个基于np.cumsum来生成要设置为零的元素掩码，如下所示 -

# 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

方法＃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.

这个开始于从@ tom10的答案中找到最后的负面元素索引并开发成使用广播的掩模查找方法来获得所需的输出，类似于方法＃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

#3

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

找到第一个通常比找到最后一个更容易和更快，所以在这里我反转数组然后找到第一个负数（使用OP的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).

这基本上归结为每行的负数。如果你每行有1000个负数，你平均会有非零段，它们是你整行长度的1/1000，所以只需查看两端就可以获得1000倍的加速度。问题中提供的简短示例非常适合理解和回答基本问题，但是当您的最终应用程序是一个非常不同的用例时，我不会太认真地对时间测试进行考虑;特别是因为通过使用迭代节省的分数时间与数组大小成比例地增加（假设恒定比率和负数的随机分布）。

#4

You can access individual rows:

您可以访问各行：

A2[0] == array([-5, -4,  2, -2, -1,  0,  1,  2,  3,  4])