Iterieren durch einen scipy.sparse Vektor (oder Matrix)

Question

Ich frage mich, was der beste Weg ist, nicht Null Einträge von Sparse-Matrizen mit scipy.sparse zu iterieren. Zum Beispiel, wenn ich die folgenden:

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 

die Ausgabe

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 

so scheint es, das Iterator jedes Element berührt, nicht nur die von Null verschiedenen Einträgen. Ich habe einen Blick auf die um ein bisschen

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

und suchten

API hatte, aber ich kann nicht eine Lösung zu finden scheinen, die funktioniert.

Answer 1

Bearbeiten: bbtrb's method (mit coo_matrix) ist viel schneller als mein ursprünglicher Vorschlag, mit nonzero. Sven Marnachs Vorschlag, itertools.izip zu verwenden, verbessert ebenfalls die Geschwindigkeit. Aktuelle schnellste ist 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) 

diese timeit Ergebnisse liefert:

% 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

Versuchen Sie filter(lambda x:x, x) anstelle von x.

Answer 3

auf eine Der schnellste Weg sollte coo_matrix durch Umwandlung:

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

Ich hatte das gleiche Problem und tatsächlich, Wenn es nur um Geschwindigkeit geht, ist der schnellste Weg (mehr als eine Größenordnung schneller), die dünne Matrix in eine dichte Matrix zu konvertieren (x.todense()) und Iterieren über die Nicht-Null-Elemente in der dichten Matrix. (Obwohl natürlich erfordert dieser Ansatz viel mehr Speicher)

Answer 5

tocoo() materialisiert die gesamte Matrix in eine andere Struktur, die nicht die bevorzugte MO für Python 3 ist. Sie können auch diesen Iterator, der besonders ist nützlich für große Matrizen.

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) 

Ich muss zugeben, dass ich eine Menge von Python-Konstrukte bin mit, die möglicherweise durch numpy-Konstrukte ersetzt werden sollten (vor allem aufzuzählen).

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> 

Also ja, aufzuzählen ist etwas langsam (ish)

Für den Iterator:

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 

So entscheiden Sie, ob dieser Aufwand akzeptabel ist, in mein Fall der Tocoo verursachte MemoryOverflows 's.

IMHO: ein solcher Iterator sollte ein Teil der csr_matrix Schnittstelle, ähnlich wie Artikel() in einem dict() :)

Answer 6

Um Schleife eine Vielzahl von schwach besetzte Matrizen aus dem scipy.sparse Codeabschnitt sein, die ich dieses kleine verwenden würde Wrapper-Funktion (beachten Sie, dass für Python-2 Sie xrange und izip für eine bessere Leistung bei großen Matrizen zu verwenden, werden ermutigt):

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