Znajdowanie pierwszej niezerowej wartości wzdłuż osi sortowanej dwuwymiarowej tablicy numpy

Question

Próbuję znaleźć najszybszy sposób znalezienia pierwszej niezerowej wartości dla każdego wiersza dwuwymiarowej posortowanej tablicy. Technicznie jedynymi wartościami w tablicy są zera i jedynki, które są "sortowane".

Na przykład tablica może wyglądać następująco:

V =

0 0 0 1 1 1 1 
0 0 0 1 1 1 1 
0 0 0 0 1 1 1 
0 0 0 0 0 0 1 
0 0 0 0 0 0 1 
0 0 0 0 0 0 1 
0 0 0 0 0 0 0 

może używać argmax funkcji

argmax(v, axis=1)) 

znalezienie, kiedy zmienia się od zera do jednej , ale uważam, że w każdym wierszu przeprowadzono by wyczerpujące wyszukiwanie. Moja macierz będzie miała rozsądne rozmiary (~ 2000x2000). Czy argmax nadal będzie lepszy od zwykłego wyszukiwania dla każdego wiersza w pętli for, czy jest lepsza alternatywa?

Ponadto, tablica zawsze będzie taka, że ​​pierwsza pozycja dla wiersza będzie zawsze> = pierwsza pozycja w rzędzie nad tym rzędem (ale nie ma gwarancji, że znajdzie się jedna z nich) kilka ostatnich wierszy). Mógłbym to wykorzystać za pomocą pętli for i "początkowej wartości indeksu" dla każdego wiersza równej pozycji pierwszego 1 z poprzedniego wiersza, ale czy mam rację sądząc, że funkcja numpy argmax nadal będzie przewyższać pętlę zapisaną w pythonie .

Chciałbym po prostu porównać te alternatywy, ale długość krawędzi tablicy może się nieco zmienić (od 250 do 10 000).

Answer 1

Jest dość szybki w użyciu np.where:

>>> a 
array([[0, 0, 0, 1, 1, 1, 1], 
     [0, 0, 0, 1, 1, 1, 1], 
     [0, 0, 0, 0, 1, 1, 1], 
     [0, 0, 0, 0, 0, 0, 1], 
     [0, 0, 0, 0, 0, 0, 1], 
     [0, 0, 0, 0, 0, 0, 1], 
     [0, 0, 0, 0, 0, 0, 0]]) 
>>> np.where(a>0) 
(array([0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 3, 4, 5]), array([3, 4, 5, 6, 3, 4, 5, 6, 4, 5, 6, 6, 6, 6])) 

który zapewnia krotki ze współrzędnymi do wartości większych niż 0.

Można również użyć NP.gdzie na każdego sub tablicy:

def first_true1(a): 
    """ return a dict of row: index with value in row > 0 """ 
    di={} 
    for i in range(len(a)): 
     idx=np.where(a[i]>0) 
     try: 
      di[i]=idx[0][0] 
     except IndexError: 
      di[i]=None  

    return di  

reprodukcje:

{0: 3, 1: 3, 2: 4, 3: 6, 4: 6, 5: 6, 6: None} 

czyli rzędu 0: wskaźnik 3> 0; wiersz 4: indeks 4> 0; Wiersz 6: brak indeksu większa niż 0

Jak można podejrzewać, argmax może być szybszy:

def first_true2(): 
    di={} 
    for i in range(len(a)): 
     idx=np.argmax(a[i]) 
     if idx>0: 
      di[i]=idx 
     else: 
      di[i]=None  

    return di  
    # same dict is returned... 

Jeśli masz do czynienia z logiką nie ma None dla rzędów wszystkich naughts, to jeszcze szybciej :

def first_true3(): 
    di={} 
    for i, j in zip(*np.where(a>0)): 
     if i in di: 
      continue 
     else: 
      di[i]=j 

    return di  

I tu jest wersja, która wykorzystuje oś w argmax (jak sugeruje się w swoich komentarzach):

def first_true4(): 
    di={} 
    for i, ele in enumerate(np.argmax(a,axis=1)): 
     if ele==0 and a[i][0]==0: 
      di[i]=None 
     else: 
      di[i]=ele 

    return di   

Dla porównania prędkości (na przykładowej tablicy), otrzymuję to:

  rate/sec usec/pass first_true1 first_true2 first_true3 first_true4 
first_true1 23,818 41.986   --  -34.5%  -63.1%  -70.0% 
first_true2 36,377 27.490  52.7%   --  -43.6%  -54.1% 
first_true3 64,528 15.497  170.9%  77.4%   --  -18.6% 
first_true4 79,287 12.612  232.9%  118.0%  22.9%   -- 

Gdybym skalować że do NP tablicy 2000 x 2000, oto co mam:

  rate/sec usec/pass first_true3 first_true1 first_true2 first_true4 
first_true3  3 354380.107   --  -0.3%  -74.7%  -87.8% 
first_true1  3 353327.084  0.3%   --  -74.6%  -87.7% 
first_true2  11 89754.200  294.8%  293.7%   --  -51.7% 
first_true4  23 43306.494  718.3%  715.9%  107.3%   -- 

Answer 2

argmax() użyć C pętlę poziomie, to znacznie szybciej niż pętli Pythona, więc myślę, że nawet można napisać inteligentny algorytm w Pythonie, to trudno pokonać argmax(), można użyć Cython do przyspieszenia:

@cython.boundscheck(False) 
@cython.wraparound(False) 
def find(int[:,:] a): 
    cdef int h = a.shape[0] 
    cdef int w = a.shape[1] 
    cdef int i, j 
    cdef int idx = 0 
    cdef list r = [] 
    for i in range(h): 
     for j in range(idx, w): 
      if a[i, j] == 1: 
       idx = j 
       r.append(idx) 
       break 
     else: 
      r.append(-1) 
    return r 

Na moim komputerze dla matrycy 2000x2000, jest to 100us vs 3ms.