Vettorizzazione di funzionamento indice per una matrice scipy.sparse

Question

Il seguente codice viene eseguito troppo lentamente, anche se tutto sembra essere vettorializzare.

from numpy import *
from scipy.sparse import *

n = 100000;
i = xrange(n); j = xrange(n);
data = ones(n);

A=csr_matrix((data,(i,j)));

x = A[i,j]

Il problema sembra essere che l'operazione di indicizzazione è implementata come una funzione pitone, e invocando risultati A[i,j] nell'output seguente profilatura

         500033 function calls in 8.718 CPU seconds

   Ordered by: internal time

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
   100000    7.933    0.000    8.156    0.000 csr.py:265(_get_single_element)
        1    0.271    0.271    8.705    8.705 csr.py:177(__getitem__)
(...)

In particolare, la funzione di pitone _get_single_element viene chiamata 100000 volte che è davvero inefficiente. Perché non è questo implementata in puro C? Qualcuno sa di un modo per aggirare questa limitazione, e accelerando il codice di cui sopra? Dovrei usare un diverso tipo di matrice sparsa?

Answer 1

È possibile utilizzare A.diagonal() per recuperare i diagonale molto più velocemente (0,0009 secondi contro 3,8 secondi sulla mia macchina). Tuttavia, se si vuole fare l'indicizzazione arbitrario allora che è una domanda più complicata, perché non si utilizza fette così tanto come un elenco di indici. La funzione _get_single_element viene chiamata 100000 volte perché semplicemente scorrendo le iteratori (iej) che passato ad esso. Una fetta sarebbe un [30: 60,10] o qualcosa di simile a questo.

Inoltre, vorrei usare csr_matrix(eye(n,n)) per fare la stessa matrice che hai fatto con iteratori solo per semplicità.

Aggiornamento:

Ok, dal momento che la tua domanda è davvero di essere in grado di accedere a un sacco di elementi casuali in fretta, io risponderò alle vostre domande nel miglior modo possibile.

• Perché non è questo implementata in puro C?

La risposta è semplice: nessuno ha ottenuto intorno ad esso. C'è ancora un sacco di lavoro da fare nella rada zona moduli a matrice di SciPy da quello che ho visto. Una parte implementata in C sono le conversioni tra diversi formati matrice sparsa.

• Qualcuno sa di un modo per aggirare questa limitazione, e accelerando il codice di cui sopra?

Si può provare in realtà le immersioni nei moduli matrici sparse e cercando di accelerare in su. Ho fatto così e stato in grado di ottenere il tempo fino a meno di un terzo degli originali quando si cerca il codice qui sopra per accessi casuali usando matrici di CSR. Ho dovuto accedere direttamente _get_single_element e snellire il codice in modo significativo per farlo compresa l'adozione di controlli legati.

Tuttavia, è stato ancora più veloce di utilizzare un lil_matrix (anche se più lenta per inizializzare la matrice), ma ho dovuto fare l'Accesso con una lista di comprensione perché le matrici lil non sono impostati per il tipo di indicizzazione che si sta facendo. Usando una lista di comprensione per il csr_matrix lascia ancora il metodo della matrice lil strada da percorrere per la via. In definitiva, la matrice lil è più veloce per accedere agli elementi casuali perché non è compresso.

Uso della lil_matrix nella sua forma originale viene eseguito in circa un quinto del tempo del codice che hai elencato sopra. Se prendo alcuni controlli legati e chiamare il metodo _get1 () di lil_matrix direttamente, posso portare il tempo verso il basso ulteriormente circa il 7% del tempo originale. Per chiarezza che è una velocità-up da 3,4-3,8 secondi a circa 0,261 secondi.

Infine, ho provato a fare la mia propria funzione che accede direttamente i dati del matrice lil ed evita le ripetute chiamate di funzione. Il tempo per questo è stato di circa 0,136 secondi. Questo non si è avvalsa dei dati da ordinare che è un altro potenziale di ottimizzazione (in particolare se si sta accedendo un sacco di elementi che sono sulle stesse righe).

Se si desidera più veloce di quello, allora si dovrà scrivere il proprio codice C implementazione matrice sparsa probabilmente.

• Dovrei usare un altro tipo di matrice sparsa?

Bene, suggerisco la matrice lil se il vostro intento è quello di accedere a tutta una serie di elementi, ma tutto dipende da ciò che è necessario fare. Avete anche necessario moltiplicare le matrici, per esempio? Basta ricordare che cambiare tra matrici può almeno volte (in alcuni casi) è abbastanza veloce quindi non escludono cambiare in un formato matrice diverso per eseguire operazioni diverse.

Se non c'è bisogno di fare effettivamente fare qualsiasi operazione di algebra sulla matrice, allora forse si dovrebbe semplicemente utilizzare un defaultdict o qualcosa di simile. Il pericolo con defaultdicts è che ogni volta che un elemento viene chiesto che non si trova nel dizionario, si pone l'elemento al default e lo memorizza in modo che potrebbe essere problematico.

Answer 2

Credo _get_single_element viene chiamato solo quando viene utilizzata la DTYPE predefinito di 'oggetto'. Hai provato fornendo un DTYPE, come ad esempio csr_matrix((data, (i,j)), dtype=int32)