python - Éléments bin par ligne-Bincount 2D vectorisé pour NumPy



performance matrix (1)

J'ai un tableau NumPy avec des valeurs entières. Les valeurs de la matrice vont de 0 à max élément dans la matrice (autrement dit, tous les nombres de 0 à max élément de données présenté dans celle-ci). Je dois construire une solution efficace ( solution efficace entièrement vectorisée rapide ) pour rechercher un nombre d'éléments dans chaque ligne et les encoder en fonction des valeurs de la matrice.

Je ne pouvais pas trouver une question similaire, ou une question qui en quelque sorte aidé à résoudre ce problème.

Donc, si j'ai ces data en entrée:

# shape is (N0=4, m0=4) 
1   1   0   4
2   4   2   1
1   2   3   5
4   4   4   1

la sortie souhaitée est:

# shape(N=N0, m=data.max()+1):
1   2   0   0   1   0
0   1   2   0   1   0
0   1   1   1   0   1
0   1   0   0   3   0

Je sais comment résoudre ce problème en comptant simplement les valeurs uniques dans chaque ligne de data itérant une par une, puis en combinant les résultats en tenant compte de toutes les valeurs possibles du tableau de data .

Lors de l'utilisation de NumPy pour vectoriser ceci, le problème clé est que la recherche de chaque numéro un par un est lente et que si l'on suppose qu'il y a beaucoup de nombres uniques présentés, cela ne peut pas être une solution efficace. Généralement, le nombre de N et de nombres uniques est plutôt grand (en passant, N semble être plus grand que le nombre de nombres uniques).

Quelqu'un a-t-il de bonnes idées?)


Eh bien, c’est essentiellement ce que fait np.bincount avec les tableaux 1D . Mais nous devons l’utiliser de manière itérative sur chaque rangée (en y pensant simplement). Pour le rendre vectorisé, nous pourrions décaler chaque ligne de ce nombre maximum. L'idée est d'avoir différents emplacements pour chaque ligne afin qu'ils ne soient pas affectés par d'autres éléments de ligne portant les mêmes numéros.

Par conséquent, la mise en œuvre serait -

# Vectorized solution
def bincount2D_vectorized(a):    
    N = a.max()+1
    a_offs = a + np.arange(a.shape[0])[:,None]*N
    return np.bincount(a_offs.ravel(), minlength=a.shape[0]*N).reshape(-1,N)

Exemple de cycle -

In [189]: a
Out[189]: 
array([[1, 1, 0, 4],
       [2, 4, 2, 1],
       [1, 2, 3, 5],
       [4, 4, 4, 1]])

In [190]: bincount2D_vectorized(a)
Out[190]: 
array([[1, 2, 0, 0, 1, 0],
       [0, 1, 2, 0, 1, 0],
       [0, 1, 1, 1, 0, 1],
       [0, 1, 0, 0, 3, 0]])

Numba Tweaks

Nous pouvons faire numba à numba pour accélérer encore les choses. Maintenant, numba permet quelques ajustements.

  • Tout d'abord, il permet la compilation JIT.

  • De plus, ils ont récemment introduit le parallel expérimental qui parallel automatiquement les opérations de la fonction connue pour avoir une sémantique parallèle.

  • Le tweak final consisterait à utiliser prange tant que substitut de range . Les documents indiquent que cela exécute des boucles en parallèle, de la même manière que OpenMP parallel pour les boucles et le style de Cython. prange fonctionne bien avec des jeux de données plus volumineux, ce qui est probablement dû à la surcharge nécessaire à la configuration du travail en parallèle.

Donc, avec ces deux nouveaux réglages et le njit pour le mode sans Python, nous aurions trois variantes -

# Numba solutions
def bincount2D_numba(a, use_parallel=False, use_prange=False):
    N = a.max()+1
    m,n = a.shape
    out = np.zeros((m,N),dtype=int)

    # Choose fucntion based on args
    func = bincount2D_numba_func0
    if use_parallel:
        if use_prange:
            func = bincount2D_numba_func2
        else:
            func = bincount2D_numba_func1
    # Run chosen function on input data and output
    func(a, out, m, n)
    return out

@njit
def bincount2D_numba_func0(a, out, m, n):
    for i in range(m):
        for j in range(n):
            out[i,a[i,j]] += 1

@njit(parallel=True)
def bincount2D_numba_func1(a, out, m, n):
    for i in range(m):
        for j in range(n):
            out[i,a[i,j]] += 1

@njit(parallel=True)
def bincount2D_numba_func2(a, out, m, n):
    for i in prange(m):
        for j in prange(n):
            out[i,a[i,j]] += 1

Pour être complet et tester plus tard, la version en boucle serait -

# Loopy solution
def bincount2D_loopy(a):
    N = a.max()+1
    m,n = a.shape
    out = np.zeros((m,N),dtype=int)
    for i in range(m):
        out[i] = np.bincount(a[i], minlength=N)
    return out 

Test d'exécution

Cas 1 :

In [312]: a = np.random.randint(0,100,(100,100))

In [313]: %timeit bincount2D_loopy(a)
     ...: %timeit bincount2D_vectorized(a)
     ...: %timeit bincount2D_numba(a, use_parallel=False, use_prange=False)
     ...: %timeit bincount2D_numba(a, use_parallel=True, use_prange=False)
     ...: %timeit bincount2D_numba(a, use_parallel=True, use_prange=True)
10000 loops, best of 3: 115 µs per loop
10000 loops, best of 3: 36.7 µs per loop
10000 loops, best of 3: 22.6 µs per loop
10000 loops, best of 3: 22.7 µs per loop
10000 loops, best of 3: 39.9 µs per loop

Cas n ° 2:

In [316]: a = np.random.randint(0,100,(1000,1000))

In [317]: %timeit bincount2D_loopy(a)
     ...: %timeit bincount2D_vectorized(a)
     ...: %timeit bincount2D_numba(a, use_parallel=False, use_prange=False)
     ...: %timeit bincount2D_numba(a, use_parallel=True, use_prange=False)
     ...: %timeit bincount2D_numba(a, use_parallel=True, use_prange=True)
100 loops, best of 3: 2.97 ms per loop
100 loops, best of 3: 3.54 ms per loop
1000 loops, best of 3: 1.83 ms per loop
100 loops, best of 3: 1.78 ms per loop
1000 loops, best of 3: 1.4 ms per loop

Cas n ° 3:

In [318]: a = np.random.randint(0,1000,(1000,1000))

In [319]: %timeit bincount2D_loopy(a)
     ...: %timeit bincount2D_vectorized(a)
     ...: %timeit bincount2D_numba(a, use_parallel=False, use_prange=False)
     ...: %timeit bincount2D_numba(a, use_parallel=True, use_prange=False)
     ...: %timeit bincount2D_numba(a, use_parallel=True, use_prange=True)
100 loops, best of 3: 4.01 ms per loop
100 loops, best of 3: 4.86 ms per loop
100 loops, best of 3: 3.21 ms per loop
100 loops, best of 3: 3.18 ms per loop
100 loops, best of 3: 2.45 ms per loop

On dirait que les variantes numba fonctionnent très bien. Le choix d'une des trois variantes dépend des paramètres de forme du tableau en entrée et, dans une certaine mesure, du nombre d'éléments uniques qu'il contient.





vectorization