python - barplot - pandas plot

Operación de suma extremadamente lenta en la matriz LIL dispersa en Python

Question

He escrito este código en Python que está dando los resultados esperados pero es extremadamente extremadamente lento. El cuello de botella es la suma de múltiples filas de scipy.sparse.lil_matrix. ¿Cómo puedo hacerlo rápido?

# D1 is a 1.5M x 1.3M sparse matrix, read as scipy.sparse.lil_matrix.
# D2 is a 1.5M x 111 matrix, read as numpy.array
# F1 is a csv file, read using csv.reader

for row in F1:
    user_id = row[0]
    clust = D2[user_id, 110]
    neighbors = D2[ D2[:, 110] == clust][:,1]
    score = np.zeros(1300000)

    for neigh in neighbors:
        score = score + D1 [neigh, :] # the most expensive operation

    toBeWritten = np.argsort(score)[:,::-1].A[0,:]

Por favor, avíseme si hay algo más que no sea muy óptimo.

Answer 1

Primero una demostración con una matriz muy pequeña

In [523]: idx=np.arange(0,8,2)
In [526]: D=np.arange(24).reshape(8,3)
In [527]: Dll=sparse.lil_matrix(D)

In [528]: D[idx,:].sum(axis=0)
Out[528]: array([36, 40, 44])

In [529]: Dll[idx,:].sum(axis=0)
Out[529]: matrix([[36, 40, 44]], dtype=int32)

In [530]: timeit D[idx,:].sum(axis=0)
100000 loops, best of 3: 17.3 µs per loop

In [531]: timeit Dll[idx,:].sum(axis=0)
1000 loops, best of 3: 1.16 ms per loop

In [532]: score=np.zeros(3)      # your looping version
In [533]: for i in idx:
   .....:     score = score + Dll[i,:]

In [534]: score
Out[534]: matrix([[ 36.,  40.,  44.]])

In [535]: %%timeit
   .....: score=np.zeros(3)
   .....: for i in idx:
    score = score + Dll[i,:]
   .....: 
100 loops, best of 3: 2.76 ms per loop

Para algunas operaciones, el formato csr es más rápido:

In [537]: timeit Dll.tocsr()[idx,:].sum(axis=0)
1000 loops, best of 3: 955 µs per loop

o si preconvierto a csr:

In [538]: Dcsr=Dll.tocsr()

In [539]: timeit Dcsr[idx,:].sum(axis=0)
1000 loops, best of 3: 724 µs per loop

Todavía lento en comparación con denso.

Iba a hablar sobre trabajar con los atributos de datos de la matriz dispersa como una forma de seleccionar filas más rápido. Pero si el único propósito para seleccionar estas filas es sumar sus valores, no es necesario que hagamos eso.

Las matrices dispersas suman en filas o columnas haciendo un producto de matriz con una columna o una matriz de fila de unos. Y acabo de responder otra pregunta con la misma respuesta.

https://.com/a/37120235/901925 Efficiently compute columnwise sum of sparse array where every non-zero element is 1

Por ejemplo:

In [588]: I=np.asmatrix(np.zeros((1,Dll.shape[0])))    
In [589]: I[:,idx]=1
In [590]: I
Out[590]: matrix([[ 1.,  0.,  1.,  0.,  1.,  0.,  1.,  0.]])
In [591]: I*Dll
Out[591]: matrix([[ 36.,  40.,  44.]])

In [592]: %%timeit 
I=np.asmatrix(np.zeros((1,Dll.shape[0])))
I[:,idx]=1
I*Dll
   .....: 
1000 loops, best of 3: 919 µs per loop

Para esta pequeña matriz no ayudó a la velocidad, pero con el tiempo de Dcsr reduce a 215 µs (es mucho mejor para las matemáticas). Con matrices grandes, esta versión del producto mejorará.

=================

Acabo de descubrir, en otra pregunta, que una selección de fila A_csr[[1,1,0,3],:] se realiza realmente con un producto de matriz. Construye una matriz csr ''extractor'' que se parece a

matrix([[0, 1, 0, 0],
       [0, 1, 0, 0],
       [1, 0, 0, 0],
       [0, 0, 0, 1]])

https://.com/a/37245105/901925