Warum sparse matrix computing auf Python zu langsam ist

Question

Das Format, das ich verwendet habe, ist die CSR-Sparse-Matrix, die empfohlen wird, die schnellste Sparse-Struktur für Add-und Dotoperator zu sein. Ich habe seine Leistung mit dem add- und dot-Operator von np.array verglichen. Es erscheint jedoch sehr seltsam, dass die Berechnung für die dünn besetzte Matrix viel langsamer ist als im Fall des dichten Formats. Warum ist es? Und gibt es eine effizientere Möglichkeit, Spared Computing zu implementieren?

import numpy as np 
import scipy.sparse as sp 
import random 

#%% generate dense vector 
vector_length = 10000 
nonzero_term = 200 

x = np.zeros((vector_length,)) 
y = np.zeros((vector_length,)) 

index = random.sample(range(vector_length), nonzero_term) 
x[index] = np.random.rand(nonzero_term) 
index = random.sample(range(vector_length), nonzero_term) 
y[index] = np.random.rand(nonzero_term) 

#%% transform to sparse vector 
x_sp = sp.csr_matrix(x) 
y_sp = sp.csr_matrix(y) 

#%% test 

# dense add 
%timeit [x + y] 
# sparse add 
%timeit [x_sp + y_sp]  
# dense dot 
%timeit [x.dot(y)] 
# sparse dot 
%timeit [x_sp.dot(y_sp.T)] 

und das Ergebnis zeigt

100000 loops, best of 3: 6.06 µs per loop 
10000 loops, best of 3: 97.8 µs per loop 
100000 loops, best of 3: 3.45 µs per loop 
1000 loops, best of 3: 225 µs per loop 

Answer 1

Beide Sätze von Operationen kompilierten Code verwenden. Aber die Daten sind sehr unterschiedlich gespeichert.

x.shape ist (10000,); y ebenfalls. x+y muss nur ein Array mit der gleichen Form zuweisen, und effizient in c Schritt durch die 3 Datenpuffer.

x_sp 200 Nicht-Null-Wert hat, sind die Werte in x_sp.data und deren Spaltenindizes in x_sp.indices. Es gibt ein drittes Array, x_sp.indptr, aber mit nur 2 Werten. Ähnlich für y_sp. Aber um sie hinzuzufügen, muss sie 4 Arrays durchlaufen und zwei Arrays Werte zuweisen. Auch wenn es in c codiert ist, gibt es viel mehr Arbeit. In meinem Testfall x_sp+y_sp hat 397 Werte ungleich Null.

Bei diesen 1D-Arrays (1-reihige Matrizen) beinhaltet der dot die gleiche Art von Werten, die nur durch einen Wert summiert werden.

Wenn die Dichte der Matrizen niedrig genug ist, können spärliche Berechnungen schneller sein. Das ist wahr, denke ich, Matrixmultiplikation mehr als Addition.

In der Summe ist die Berechnung pro Element mit spärlichen Matrizen komplizierter. Selbst wenn es wenige Elemente gibt, neigt die Gesamtzeit dazu, länger zu sein.