Duży Numpy scipy CSR Matrix, wiersz mądry operacja

Question

Chcę iteracyjne nad rzędami CSR Matrix i podzielić każdy element o sumę rzędu, podobny do tego tutaj:

numpy divide row by row sum

Mój problem jest to, że mam do czynienia z dużą matrycą: (96582, 350138)

I kiedy stosuję operację z połączonego postu, to on wyostrza moją pamięć, ponieważ zwrócona macierz jest gęsta.

Więc tutaj jest moja pierwsza próba:

for row in counts: 
    row = row/row.sum() 

Niestety to nie wpływa na matrycę w ogóle, więc wpadłem na pomysł z drugiej stworzyć nową matrycę CSR i concat wierszy przy użyciu vstack:

from scipy import sparse 
import time 

start_time = curr_time = time.time() 
mtx = sparse.csr_matrix((0, counts.shape[1])) 
for i, row in enumerate(counts): 
    prob_row = row/row.sum() 
    mtx = sparse.vstack([mtx, prob_row]) 
    if i % 1000 == 0: 
     delta_time = time.time() - curr_time 
     total_time = time.time() - start_time 
     curr_time = time.time() 
     print('step: %i, total time: %i, delta_time: %i' % (i, total_time, delta_time)) 

działa to dobrze, ale po kilku iteracjach robi się coraz wolniej:

step: 0, total time: 0, delta_time: 0 
step: 1000, total time: 1, delta_time: 1 
step: 2000, total time: 5, delta_time: 4 
step: 3000, total time: 12, delta_time: 6 
step: 4000, total time: 23, delta_time: 11 
step: 5000, total time: 38, delta_time: 14 
step: 6000, total time: 55, delta_time: 17 
step: 7000, total time: 88, delta_time: 32 
step: 8000, total time: 136, delta_time: 47 
step: 9000, total time: 190, delta_time: 53 
step: 10000, total time: 250, delta_time: 59 
step: 11000, total time: 315, delta_time: 65 
step: 12000, total time: 386, delta_time: 70 
step: 13000, total time: 462, delta_time: 76 
step: 14000, total time: 543, delta_time: 81 
step: 15000, total time: 630, delta_time: 86 
step: 16000, total time: 722, delta_time: 92 
step: 17000, total time: 820, delta_time: 97 

Jakieś sugestie? Masz pomysł, dlaczego vstack działa wolniej i wolniej?

Answer 1

vstack jest operacją O(n), ponieważ musi przydzielić pamięć dla wyniku, a następnie skopiować zawartość wszystkich tablic przekazanych jako argumenty do tablicy wyników.

można po prostu użyć multiply zrobić operację:

>>> res = counts.multiply(1/counts.sum(1)) # multiply with inverse 
>>> res.todense() 
matrix([[ 0.33333333, 0.  , 0.66666667], 
     [ 0.  , 0.  , 1.  ], 
     [ 0.26666667, 0.33333333, 0.4  ]]) 

---

Ale jest to również bardzo proste w użyciu np.lib.stride_tricks.as_strided zrobić operację, którą chcesz (względnie wydajnych). Ta funkcja as_strided pozwala również na bardziej skomplikowane operacje na macierzy (jeśli nie ma metody lub funkcji dla twojego przypadku).

Na przykład stosując przykładową CSR w scipy documentation:

>>> from scipy.sparse import csr_matrix 
>>> import numpy as np 
>>> row = np.array([0,0,1,2,2,2]) 
>>> col = np.array([0,2,2,0,1,2]) 
>>> data = np.array([1.,2,3,4,5,6]) 
>>> counts = csr_matrix((data,(row,col)), shape=(3,3)) 
>>> counts.todense() 
matrix([[ 1., 0., 2.], 
     [ 0., 0., 3.], 
     [ 4., 5., 6.]]) 

Można podzielić każdy wiersz przez nią to suma tak:

>>> row_start_stop = np.lib.stride_tricks.as_strided(counts.indptr, 
                shape=(counts.shape[0], 2), 
                strides=2*counts.indptr.strides) 
>>> for start, stop in row_start_stop: 
... row = counts.data[start:stop] 
... row /= row.sum() 
>>> counts.todense() 
matrix([[ 0.33333333, 0.  , 0.66666667], 
     [ 0.  , 0.  , 1.  ], 
     [ 0.26666667, 0.33333333, 0.4  ]]) 

Answer 2

Edit

@MSeifert odpowiedź jest o wiele bardziej wydajny, a które powinny być właściwym sposobem prowadzenia. Myślę, że pisanie counts[i, :] implikuje pewne cięcie kolumn, którego nie zdawałem sobie sprawy. Dokumentacja wyraźnie mówi, że są to naprawdę nieefektywne operacje na csr_matrix. Droga rzeczywiście ma tego dobry przykład.

Odpowiedź

Doc mówi wiersz krojenie jest wydajny, myślę, że należy zrobić

for i in range(counts.shape[0]): 
    counts[i,:] /= counts[i,:].sum() 

ten sposób można edytować swoje matrycę w miejscu, pozostaje skromny i nie trzeba używać vstack . Nie jestem pewien, że jest to najbardziej efektywne działanie, ale przynajmniej nie powinien mieć problemów z pamięcią, i nie ma powolny efekt dół jak wiersze są obliczane:

import time() 
s = time.time() 
for i in range(counts.shape[0]): 
    counts[i, :] /= (counts[i, :].sum() + 1) 
    if i % 1000 == 0: 
     e = time.time() 
     if i > 0: 
      print i, e-s 
     s = time.time() 

Spektakle:

1000 6.00199794769 2000 6.02894091606 3000 7.44459486008 4000 7.10011601448 5000 6.16998195648 6000 7.79510307312 7000 7.00139117241 8000 7.37821507454 9000 7.28075814247 ...

Przedstawienia dla odpowiedzi MSeifert za:

row_start_stop = np.lib.stride_tricks.as_strided(counts.indptr, shape=(counts.shape[0], 2), 
               strides=2*counts.indptr.strides) 
for i, (start, stop) in enumerate(row_start_stop): 
    row = counts.data[start:stop] 
    row /= row.sum() 
    if i % 1000 == 0: 
     e = time.time() 
     if i > 0: 
      print i,e-s 
     s = time.time() 

1000 0.00735783576965 2000 0.0108380317688 3000 0.0102109909058 4000 0.0131571292877 5000 0.00670218467712 6000 0.00608897209167 7000 0.00663685798645 8000 0.0164499282837 9000 0.0061981678009 ... dlaczego używając vstack działa wolno, odpowiedź @MSeifert jest świetna.