python - over - Elementos de contenedor por fila: Conteo de contenedores 2D vectorizado para NumPy

numpy vectorize

Question

Tengo una matriz NumPy con valores enteros. Los valores de la matriz varían de 0 a max elemento en matriz (en otras palabras, todos los números de 0 a max elemento de datos presentados en ella). Necesito crear un método efectivo ( efectivo significa una solución rápida y completamente vectorizada ) para buscar el número de elementos en cada fila y codificarlos de acuerdo con los valores de la matriz.

No pude encontrar una pregunta similar, o una pregunta que de alguna manera ayudó a resolver esto.

Entonces, si tengo estos data en la entrada:

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

la salida deseada es:

# 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

Sé cómo resolver esto simplemente contando valores únicos en cada fila de data iterando uno por uno, y luego combinando resultados teniendo en cuenta todos los valores posibles en data matriz de data .

Mientras usa NumPy para vectorizar esto, el problema clave es que la búsqueda de cada número uno por uno es lenta y suponiendo que se presenten muchos números únicos, esta no puede ser una solución efectiva. En general, el recuento de N y números únicos es bastante grande (por cierto, N parece ser mayor que el recuento de números únicos).

¿Alguien tiene grandes ideas?)

Answer 1

Bueno, eso es básicamente lo que hace np.bincount con matrices 1D . Pero, necesitamos usarlo en cada fila de forma iterativa (pensando simplemente). Para hacerlo vectorizado, podríamos compensar cada fila por ese número máximo. La idea es tener diferentes contenedores para cada fila de modo que no se vean afectados por otros elementos de fila con los mismos números.

Por lo tanto, la implementación sería:

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

Ejecución de muestra:

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

Ajustes de Numba

Podemos traer numba para nuevas aceleraciones. Ahora, numba permite algunos ajustes.

• En primer lugar, permite la compilación JIT.

• Además, recientemente habían introducido un parallel experimental que parallel automáticamente las operaciones en la función que se sabe que tiene una semántica paralela.

• El ajuste final sería usar prange como un sustituto para el range . Los documentos indican que esto ejecuta bucles en paralelo, similar al paralelo de OpenMP para bucles y la distribución de Cython. prange funciona bien con conjuntos de datos más grandes, lo que probablemente se deba a la sobrecarga necesaria para configurar el trabajo paralelo.

Entonces, con estos dos nuevos ajustes junto con el njit para el modo sin Python, tendríamos tres 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

Para completar y probar más adelante, la versión en bucle sería:

# 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 

Prueba de tiempo de ejecución

Caso 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

Caso # 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

Caso # 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

Parece que las variantes de numba están funcionando muy bien. Elegir una de las tres variantes dependerá de los parámetros de forma de la matriz de entrada y, en cierta medida, de la cantidad de elementos únicos que contiene.