Iteración a través de un vector scipy.sparse (o matriz)

Question

Me pregunto cuál es la mejor manera de iterar entradas distintas de cero de matrices dispersas con scipy.sparse. Por ejemplo, si hago lo siguiente:

from scipy.sparse import lil_matrix 

x = lil_matrix((20,1)) 
x[13,0] = 1 
x[15,0] = 2 

c = 0 
for i in x: 
    print c, i 
    c = c+1 

la salida es

0 
1 
2 
3 
4 
5 
6 
7 
8 
9 
10 
11 
12 
13 (0, 0) 1.0 
14 
15 (0, 0) 2.0 
16 
17 
18 
19 

por lo que parece el iterador está en contacto con todos los elementos, no sólo los elementos no nulos. He echado un vistazo a la API

http://docs.scipy.org/doc/scipy/reference/generated/scipy.sparse.lil_matrix.html

y busqué un poco, pero me parece que no puede encontrar una solución que funcione.

Answer 1

Editar: bbtrb's method (usando coo_matrix) es mucho más rápido que mi sugerencia original, usando nonzero. La sugerencia de Sven Marnach de usar itertools.izip también mejora la velocidad. Actual más rápido es using_tocoo_izip:

import scipy.sparse 
import random 
import itertools 

def using_nonzero(x): 
    rows,cols = x.nonzero() 
    for row,col in zip(rows,cols): 
     ((row,col), x[row,col]) 

def using_coo(x): 
    cx = scipy.sparse.coo_matrix(x)  
    for i,j,v in zip(cx.row, cx.col, cx.data): 
     (i,j,v) 

def using_tocoo(x): 
    cx = x.tocoo()  
    for i,j,v in zip(cx.row, cx.col, cx.data): 
     (i,j,v) 

def using_tocoo_izip(x): 
    cx = x.tocoo()  
    for i,j,v in itertools.izip(cx.row, cx.col, cx.data): 
     (i,j,v) 

N=200 
x = scipy.sparse.lil_matrix((N,N)) 
for _ in xrange(N): 
    x[random.randint(0,N-1),random.randint(0,N-1)]=random.randint(1,100) 

produce estos timeit resultados:

% python -mtimeit -s'import test' 'test.using_tocoo_izip(test.x)' 
1000 loops, best of 3: 670 usec per loop 
% python -mtimeit -s'import test' 'test.using_tocoo(test.x)' 
1000 loops, best of 3: 706 usec per loop 
% python -mtimeit -s'import test' 'test.using_coo(test.x)' 
1000 loops, best of 3: 802 usec per loop 
% python -mtimeit -s'import test' 'test.using_nonzero(test.x)' 
100 loops, best of 3: 5.25 msec per loop 

Answer 2

Pruebe filter(lambda x:x, x) en lugar de x.

Answer 3

La forma más rápida debe ser mediante la conversión a un coo_matrix:

cx = scipy.sparse.coo_matrix(x) 

for i,j,v in zip(cx.row, cx.col, cx.data): 
    print "(%d, %d), %s" % (i,j,v) 

Answer 4

que tenían el mismo problema y, de hecho, si su preocupación es solo la velocidad, la manera más rápida (más de 1 orden de magnitud más rápido) es convertir la matriz dispersa en una densa (x.todense()) e iterando sobre los elementos distintos de cero en la matriz densa. (Aunque, por supuesto, este enfoque requiere mucha más memoria)

Answer 5

tocoo() materializa toda la matriz en una estructura diferente, que no es el MO preferido para python 3. También puede considerar este iterador, que es especialmente útil para matrices grandes.

from itertools import chain, repeat 
def iter_csr(matrix): 
    for (row, col, val) in zip(
    chain(*(
      repeat(i, r) 
      for (i,r) in enumerate(comparisons.indptr[1:] - comparisons.indptr[:-1]) 
    )), 
    matrix.indices, 
    matrix.data 
): 
    yield (row, col, val) 

Tengo que admitir que estoy usando un montón de python-construcciones que posiblemente debería sustituirse por numpy constructos (especialmente enumerar).

NB:

In [43]: t=time.time(); sum(1 for x in rather_dense_sparse_matrix.data); print(time.time()-t) 
52.48686504364014 
In [44]: t=time.time(); sum(1 for x in enumerate(rather_dense_sparse_matrix.data)); print(time.time()-t) 
70.19013023376465 
In [45]: rather_dense_sparse_matrix 
<99829x99829 sparse matrix of type '<class 'numpy.float16'>' 
with 757622819 stored elements in Compressed Sparse Row format> 

Así que sí, enumerar es algo lento (más o menos)

Para el iterador:

In [47]: it = iter_csr(rather_dense_sparse_matrix) 
In [48]: t=time.time(); sum(1 for x in it); print(time.time()-t) 
113.something something 

por lo que decide si esta sobrecarga es aceptable, en mi caso el tocoo causó MemoryOverflows.

mi humilde opinión: un iterador tal debe ser parte de la interfaz de csr_matrix, similar a los elementos() en un dict() :)

Answer 6

Para bucle de una variedad de matrices dispersas de la sección scipy.sparse código me gustaría utilizar esta pequeña función de contenedor (tenga en cuenta que para Python-2 se le anima a utilizar xrange y izip para un mejor rendimiento en grandes matrices):

from scipy.sparse import * 
def iter_spmatrix(matrix): 
    """ Iterator for iterating the elements in a ``scipy.sparse.*_matrix`` 

    This will always return: 
    >>> (row, column, matrix-element) 

    Currently this can iterate `coo`, `csc`, `lil` and `csr`, others may easily be added. 

    Parameters 
    ---------- 
    matrix : ``scipy.sparse.sp_matrix`` 
     the sparse matrix to iterate non-zero elements 
    """ 
    if isspmatrix_coo(matrix): 
     for r, c, m in zip(matrix.row, matrix.col, matrix.data): 
      yield r, c, m 

    elif isspmatrix_csc(matrix): 
     for c in range(matrix.shape[1]): 
      for ind in range(matrix.indptr[c], matrix.indptr[c+1]): 
       yield matrix.indices[ind], c, matrix.data[ind] 

    elif isspmatrix_csr(matrix): 
     for r in range(matrix.shape[0]): 
      for ind in range(matrix.indptr[r], matrix.indptr[r+1]): 
       yield r, matrix.indices[ind], matrix.data[ind] 

    elif isspmatrix_lil(matrix): 
     for r in range(matrix.shape[0]): 
      for c, d in zip(matrix.rows[r], matrix.data[r]): 
       yield r, c, d 

    else: 
     raise NotImplementedError("The iterator for this sparse matrix has not been implemented")