Uzyskaj indeks ostatniej wartości ujemnej w tablicy 2d na kolumnę

Question

Próbuję uzyskać indeks ostatniej wartości ujemnej tablicy na kolumnę (aby ją pokroić po). prosty przykład działa na 1d wektora jest:

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] 

Teraz chcę zrobić to samo na każdej kolumnie 2D tablicy:

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

I chciałbym uzyskać:

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

ale nie mogę sobie poradzić z tym, jak przetłumaczyć instrukcję max/where na tę tablicę 2d ...

Answer 1

Masz już dobre odpowiedzi, ale chciałem zaproponować potencjalnie szybszą zmianę za pomocą funkcji np.maximum.accumulate. Ponieważ twoja metoda dla tablicy 1D używa max/where, możesz również znaleźć to podejście dość intuicyjne. (Edycja: szybsza implementacja Cython dodana poniżej).

Ogólne podejście jest bardzo podobne do innych; maska ​​jest tworzony z:

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

ta linia kodu wykonuje następujące operacje:

• (A2 < 0) tworzy logiczną tablicę, co wskazuje, czy wartość jest ujemna, czy nie. Indeks [:, ::-1] zmienia to od lewej do prawej.

• np.maximum.accumulate służy do zwrotu skumulowanego maksimum wzdłuż każdego rzędu (tj. axis=1). Na przykład [False, True, False] stanie się [False, True, True].

• Końcowa operacja indeksowania [:, ::-1] odwraca tę nową tablicę typu Boolean od lewej do prawej.

Wtedy wszystko, co pozostało do zrobienia jest użycie logiczną tablicę jako maska ​​do ustawionej wartości True do zera.

---

Pożyczanie metodologię rozrządu i dwie funkcje od @Divakar's answer, są tu odniesienia do mojego proponowanej metody:

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

Te czasy są:

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 

Więc za pomocą np.maximum.accumulate może być tak o 30% szybciej niż kolejne najszybsze rozwiązanie dla macierzy tego rozmiaru i kształtu.

---

@tom10 points out Jak każda operacja NumPy przetwarza tablic w całości, które mogą być nieskuteczne, gdy są potrzebne wielokrotne operacje, aby uzyskać wynik. Iteracyjne podejście, które działa tylko raz, może lepiej.

Poniżej znajduje się naiwna funkcja napisana w języku Cython, która może być ponad dwukrotnie szybsza od czystej metody NumPy.

Ta funkcja może być dalej zwiększana za pomocą 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 

Ta funkcja działa wstecz w każdym wierszu i rozpoczyna ustawianie wartości na zero, gdy pojawi się wartość ujemna.

Testowanie to działa:

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

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

Porównując działanie funkcji:

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

można przejść poszczególne rzędy:

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

Answer 3

Znalezienie pierwsza jest zwykle prostsze i szybsze niż znalezienie ostatni, więc tutaj mogę odwrócić tablicę, a następnie znaleźć pierwszy negatywny (używając wersji OP z dnia 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 

---

także, choć należy pamiętać, że jeśli masz duże tablice z wieloma negatywnymi numerów, to może faktycznie być szybsze w użyciu non-numpy podejście, dzięki czemu można zwarcie wyszukiwania. Oznacza to, że numpy wykona obliczenia na całej tablicy, więc jeśli masz 10000 elementów z rzędu, ale zazwyczaj trafisz liczbę ujemną w pierwszych 10 elementach (wyszukiwania wstecznego), podejście czystego Pythona może okazać się szybsze. .

Ogólnie, powtarzanie wierszy może być szybsze również w przypadku kolejnych operacji. Na przykład, jeśli następnym krokiem jest mnożenie, może być szybciej, aby pomnożyć plasterki na końcach, które nie są zerami, lub może znaleźć najdłuższą niezerową sekcję i poradzić sobie z obciętą tablicą.

To zasadniczo sprowadza się do liczby negatywów w rzędzie. Jeśli masz 1000 wykluczeń na wiersz, średnio będziesz mieć segmenty niezerowe, które wynoszą 1/1000 twojej pełnej długości wiersza, więc możesz uzyskać 1000-krotne przyspieszenie, patrząc tylko na końce. Krótki przykład podany w pytaniu jest świetny do zrozumienia i odpowiedzi na podstawowe pytanie, ale nie brałbym zbyt poważnych testów czasowych, gdy twoja aplikacja końcowa jest zupełnie innym przypadkiem użycia; zwłaszcza, że ​​twoje ułamkowe oszczędności czasu dzięki zastosowaniu iteracji poprawiają się proporcjonalnie do rozmiaru tablicy (przyjmując stały stosunek i losowy rozkład liczb ujemnych).

Answer 4

Zakładając, że chcesz ustawić wszystkie elementy dla każdego wiersza, aż ostatni ujemny element zostanie ustawiony na zero (zgodnie z oczekiwanymi wynikami podanymi w pytaniu dla przykładowego przypadku), można zaproponować dwa podejścia.

Metoda 1

ten bazuje na np.cumsum celu wytworzenia maski elementów być ustawione na wartości zero w wymienionych dalej -

# 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 

próbki 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]]) 

Podejście nr 2

Ten zaczyna się od znalezienia ostatnich indeksów elementów ujemnych z @tom10's answer i rozwija się w metodę wyszukiwania maski przy użyciu broadcasting, aby uzyskać pożądany wynik, podobny do 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 testy -

defintions funkcyjne:

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 

Weryfikuj wyniki -

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