Ricerca del primo valore diverso da zero lungo l'asse di un array numpy bidimensionale ordinato

Question

Sto cercando di trovare il modo più veloce per trovare il primo valore diverso da zero per ogni riga di un array ordinato bidimensionale. Tecnicamente, gli unici valori nella matrice sono zero e uno, ed è "ordinato".

Per esempio, la matrice potrebbe essere simile al seguente:

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 

ho potuto utilizzare la funzione argmax

argmax(v, axis=1)) 

da trovare quando si passa da zero a uno , ma credo che farebbe una ricerca esauriente lungo ogni riga. Il mio array avrà dimensioni ragionevoli (~ 2000x2000). Argmax potrebbe ancora sovraperformare solo facendo un approccio di ricerca per ogni riga all'interno di un ciclo for, o c'è un'alternativa migliore?

Inoltre, la matrice sarà sempre tale che la prima posizione di una per una riga è sempre> = la prima posizione di una nella riga sopra di essa (ma non è garantito che ci sarà uno in le ultime poche righe). Potrei sfruttare questo con un ciclo for e un "valore indice iniziale" per ogni riga uguale alla posizione del primo 1 della riga precedente, ma sono corretto nel pensare che la funzione numma argmax continuerà a sovraperformare un ciclo scritto in python .

Vorrei solo confrontare le alternative, ma la lunghezza del bordo della matrice potrebbe cambiare un po '(da 250 a 10.000).

Answer 1

E 'abbastanza veloce da usare 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])) 

che offre tuple con alle coordinate dei valori superiori a 0.

È inoltre possibile utilizzare np.dove testare ogni sub matrice:

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  

stampe:

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

esempio, riga 0: indice 3> 0; riga 4: indice 4> 0; riga 6: nessun indice maggiore di 0

Come si sospetta, argmax può essere più veloce:

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

Se si riesce a fare con la logica di non avere una None per le righe di tutti i naughts, questo è più veloce ancora :

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

    return di  

E qui è una versione che utilizza asse in argmax (come suggerito nei commenti):

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   

Per i confronti di velocità (sul tuo esempio di matrice), ottengo questo:

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

Se mi scala che a un array np 2000 x 2000, ecco cosa ottengo:

  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() utilizzare ciclo di livello C, è molto più veloce di Python ciclo, quindi penso che anche voi scrivere un algoritmo intelligente in Python, è difficile da battere argmax(), è possibile utilizzare Cython per accelerare:

@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 

Sul mio PC per matrice 2000x2000, è 100us contro 3ms.