Trouver la première valeur non nulle le long de l'axe d'une triés en deux dimensions un tableau numpy

J'essaie de trouver le moyen le plus rapide pour trouver la première valeur non nulle pour chaque ligne de deux dimensions, tableau trié. Techniquement, les seules valeurs dans le tableau sont des zéros et des uns, et c'est "triés".

Par exemple, le tableau pourrait ressembler à ce qui suit:

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

Je pouvais utiliser le argmax fonction

argmax(v, axis=1))

à trouver quand il passe de zéro à un, mais je crois que ce serait faire une recherche exhaustive, le long de chaque ligne. Mon tableau sera de taille raisonnable (~2000x2000). Serait argmax toujours mieux faire juste un searchsorted approche pour chaque ligne dans une boucle for, ou est-il une meilleure alternative?

Aussi, le tableau sera toujours que la première position de l'un pour une ligne est toujours >= la première position de celui dans la ligne au-dessus (mais il n'est pas garanti qu'il y aura un dans les dernières lignes). J'ai pu exploiter cette avec une boucle for et un "indice de départ de la valeur" pour chaque ligne égale à la position de la première 1 de la rangée précédente, mais ai-je raison de penser que le numpy argmax fonction sera toujours mieux une boucle écrit en python.

Je voudrais juste comparer les alternatives, mais la longueur de l'arête de la matrice pourrait changer un peu (de 250 à 10 000).

J'attends la argmax fonction pour être plus rapide. Si elle est critique pour les performances que vous pourriez essayer de rédiger une extension en C

OriginalL'auteur user1554752 | 2012-07-31

Il est assez rapide à utiliser np.où:

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

Qui offre les tuples avec les coordonnées des valeurs supérieures à 0.

Vous pouvez également utiliser des np.où tester chaque sous-tableau:

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

Imprime:

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

c'est à dire, la ligne 0: indice 3>0; ligne 4: indice 4>0; ligne 6: pas d'indice supérieur à 0

Que vous pensez, argmax peut être plus rapide:

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

Si vous pouvez faire face à la logique de ne pas avoir de None pour les lignes de tous les naughts, c'est encore plus rapide:

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

    return di

Et ici est une version qui utilise l'axe en argmax (comme suggéré dans vos commentaires):

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

Pour la vitesse des comparaisons (sur votre tableau exemple), j'obtiens ceci:

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

Si je échelle que pour l'année 2000 X 2000 np tableau, voici ce que j'obtiens:

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

En fait, la grande chose au sujet argmax est vous pouvez spécifier un axe, c'est à dire argmax(a, axis=1) et il passe en boucle sur les lignes à l'aide d'une boucle écrit en C, donc vous n'avez pas à utiliser un python la boucle for, qui devrait être plus lente.
Oui, mais si vous utilisez argmax(a, axis=1) puis il y a une ambiguïté entre les lignes de a qui sont [1,x,x,x,] ou [0,0,0,0] depuis argmax(a, axis=1) serait de retour 0 pour les deux cas. Vous aurez toujours besoin d'une boucle sur le tableau qui argmax retourne pour tester cette ambiguïté, non?
C'est là où j'ai pu profiter de la répétition dans les données, où le premier 1 n'est jamais dans une position à la gauche de la première 1 dans la ligne au-dessus d'elle. Une fois que j'ai le tableau de argmax (appeler indx), je peux courir un argmin sur elle. Si elle renvoie une valeur de p != 0, alors toutes les lignes de p à la baisse ont été faites uniquement de zéros.

OriginalL'auteur dawg

argmax() utiliser C au niveau de la boucle, il est beaucoup plus rapide que la boucle Python, donc je pense que même vous écrire un algorithme intelligent en Python, il est difficile de battre argmax(), Vous pouvez utiliser Cython pour speedup:

@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

Sur mon PC pour 2000x2000 de la matrice, c'est 100us vs 3ms.

OriginalL'auteur HYRY

Vous devez vous connecter pour publier un commentaire.