lấy chỉ mục của giá trị âm cuối cùng trong mảng 2d trên mỗi cột

Question

Tôi đang cố gắng lấy chỉ mục của giá trị âm cuối cùng của một mảng trên mỗi cột (để cắt nó sau). một ví dụ làm việc đơn giản trên một vector 1d là:

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] 

Bây giờ tôi muốn làm điều tương tự trên mỗi cột của một mảng 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]] 

Và tôi muốn để có được:

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

nhưng tôi không thể tìm ra cách dịch câu lệnh max/where thành mảng 2d này ...

Answer 1

Bạn đã có câu trả lời hay, nhưng tôi muốn đề xuất một biến thể có khả năng nhanh hơn bằng cách sử dụng hàm np.maximum.accumulate. Vì phương pháp của bạn cho mảng 1D sử dụng max/where, bạn cũng có thể thấy phương pháp này khá trực quan. (Chỉnh sửa: triển khai Cython nhanh hơn được thêm vào bên dưới).

Cách tiếp cận tổng thể rất giống với các phương pháp khác; mặt nạ được tạo ra với:

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

Dòng này của mã này như sau:

• (A2 < 0) tạo ra một mảng Boolean, cho biết một giá trị tiêu cực hay không. Chỉ số [:, ::-1] lật từ trái sang phải.

• np.maximum.accumulate được sử dụng để trả lại giá trị tối đa tích lũy dọc theo mỗi hàng (ví dụ: axis=1). Ví dụ: [False, True, False] sẽ trở thành [False, True, True].

• Thao tác lập chỉ mục cuối cùng [:, ::-1] lật mảng Boolean mới này sang trái sang phải.

Sau đó, tất cả những gì còn lại cần làm là sử dụng mảng Boolean làm mặt nạ để đặt giá trị True thành 0.

---

Vay phương pháp thời gian và hai chức năng từ @Divakar's answer, đây là điểm chuẩn cho phương pháp đề xuất của tôi:

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

Các timings là:

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 

Vì vậy, sử dụng np.maximum.accumulate có thể lên nhanh hơn 30% so với giải pháp nhanh nhất tiếp theo cho các mảng có kích thước và hình dạng này.

---

Là @tom10 points out, mỗi hoạt động NumPy xử lý toàn bộ mảng, điều này có thể không hiệu quả khi cần nhiều thao tác để có kết quả. Một cách tiếp cận lặp đi lặp lại hoạt động thông qua mảng chỉ một lần có thể tốt hơn.

Dưới đây là một chức năng ngây thơ được viết bằng Cython có thể nhanh hơn gấp đôi phương pháp NumPy thuần túy.

Chức năng này có thể được tăng tốc thêm bằng cách sử dụng 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 

Chức năng này hoạt động ngược qua mỗi hàng và bắt đầu đặt giá trị thành 0 khi giá trị âm.

Testing nó hoạt động:

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

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

So sánh việc thực hiện các chức năng:

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

Bạn có thể truy cập vào hàng cá nhân:

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

Answer 3

Tìm người đầu tiên thường là dễ dàng hơn và nhanh hơn so với việc tìm kiếm cuối cùng, vì vậy ở đây tôi đảo ngược mảng và sau đó tìm ra tiêu cực đầu tiên (sử dụng phiên bản của OP của 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 

---

Ngoài ra, tuy nhiên, lưu ý rằng nếu bạn có mảng lớn với số lượng nhiều tiêu cực, nó thực sự có thể nhanh hơn để sử dụng một cách tiếp cận phi numPy để bạn có thể làm chập mạch các tìm kiếm. Điều đó có nghĩa là tính toán trên toàn bộ mảng, vì vậy nếu bạn có 10000 phần tử trong một hàng nhưng thường sẽ đạt số âm trong 10 phần tử đầu tiên (tìm kiếm ngược), phương pháp Python thuần túy có thể sẽ nhanh hơn .

Nhìn chung, việc lặp lại các hàng có thể nhanh hơn cho các hoạt động tiếp theo. Ví dụ, nếu bước tiếp theo của bạn là phép nhân, nó có thể nhanh hơn để nhân các lát ở đầu kết thúc là số không, hoặc có thể tìm thấy phần dài nhất khác 0 và chỉ đối phó với mảng bị cắt ngắn.

Điều này về cơ bản là số lượng âm mỗi hàng. Nếu bạn có 1000 âm bản trên mỗi hàng bạn sẽ ở mức trung bình có các phân đoạn không phải là số không bằng 1/1000 chiều dài hàng đầy đủ của bạn, do đó bạn có thể tăng tốc 1000x bằng cách chỉ nhìn vào các đầu. Ví dụ ngắn được đưa ra trong câu hỏi là rất tốt cho sự hiểu biết và trả lời các câu hỏi cơ bản, nhưng tôi sẽ không mất thời gian kiểm tra quá nghiêm trọng khi ứng dụng cuối cùng của bạn là một trường hợp sử dụng rất khác nhau; đặc biệt là kể từ khi tiết kiệm thời gian phân đoạn của bạn bằng cách sử dụng lặp đi lặp lại được cải thiện theo tỷ lệ mảng (giả sử một tỷ lệ cố định và phân phối ngẫu nhiên các số âm).

Answer 4

Giả sử bạn đang tìm kiếm để đặt tất cả các yếu tố cho mỗi hàng cho đến khi các yếu tố tiêu cực cuối cùng được thiết lập để không (theo sản lượng dự kiến ​​niêm yết trong câu hỏi cho một trường hợp mẫu), hai cách tiếp cận có thể được gợi ý ở đây.

Approach # 1

một này được dựa trên np.cumsum để tạo ra một mặt nạ của các yếu tố được thiết lập để số không như liệt kê bên cạnh -

# 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 

mẫu chạy -

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

Phương pháp tiếp cận # 2

Điều này bắt đầu với ý tưởng tìm các chỉ số phần tử âm cuối cùng từ @tom10's answer và phát triển thành phương pháp tìm kiếm mặt nạ bằng cách sử dụng broadcasting để cho chúng tôi kết quả mong muốn, tương tự như 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 

---

kiểm tra Runtime -

Chức năng 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 

kiểm chứng kết quả -

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