Nur speichern, was nicht null ist
Viele große Matrizen bestehen fast nur aus Nullen. Ein Gitter zur Optionsbewertung hat eine Zeile je Preisniveau, und jede Zeile berührt nur ihre zwei Nachbarn. Eine solche Matrix heißt dünnbesetzt. Jede Null zu speichern verschwendet Speicher und Zeit. scipy.sparse behält nur die Einträge ungleich null. Das Format csr_matrix (komprimierte dünnbesetzte Zeilen) nutzt drei Listen. data enthält die Nicht-Null-Werte zeilenweise, indices die Spalte jedes Werts, und indptr sagt, wo jede Zeile in data beginnt und endet: Zeile ist data[indptr[i]:indptr[i+1]]. Die letzte Zahl von indptr ist die Anzahl der Nicht-Nullen, nnz.
Verschiedene Formate passen zu verschiedenen Aufgaben. coo_matrix speichert einfache Tripel (Zeile, Spalte, Wert) und ist der einfache Weg, eine Matrix aufzubauen. csr_matrix ist schnell für Zeilenausschnitte und für das Produkt , das etwa nnz Multiplikationen statt kostet. csc_matrix ist dieselbe Idee spaltenweise, und dia_matrix speichert Diagonalen, ideal für Bandmatrizen. Für ein System nutzt sparse.linalg.spsolve die Nullen und ist viel schneller als ein dichtes Lösen. Dünnbesetzt ist nicht immer besser: Sind mehr als etwa ein Drittel der Einträge ungleich null, kostet die Buchführung mehr, als sie spart. In der Finanzwelt tritt Dünnbesetztheit in Bewertungsgittern auf, in Faktormodellen, in denen die meisten Ladungen null sind, und wenn man nur die starken Korrelationen behält.
data=[5,1,2,3,4], indices=[0,3,2,0,3] und indptr=[0,2,3,3,5]. Zeile ist leer, weil indptr[2]=indptr[3]=3, und nnz=5. Die Multiplikation mit addiert jede Zeile und ergibt mit nur Multiplikationen. Eine Tridiagonalmatrix mit , etwa ein Finite-Differenzen-Bewertungsgitter, hat Nicht-Nullen bei Einträgen, eine Dichte von . Sie braucht in CSR etwa KB gegenüber MB dicht. Bei echten Daten bilden die Korrelationen von Aktien aus der gemeinsamen Kursdatei eine -Matrix. Behält man nur Einträge mit , bleiben von übrig, , und die CSR-Kopie braucht KB gegenüber KB dicht. Bei bleiben nur .- Drei Listen:
data,indicesundindptrbeschreiben eine CSR-Matrix, undindptr[-1]ist die Zahl der Nicht-Nullen. - In COO bauen, in CSR rechnen: Tripel sind leicht zusammenzusetzen, zeilenweises Speichern ist schnell für Produkte und Lösungen.
- Dünnbesetzt lohnt sich nur bei überwiegend Nullen: Eine dichte Matrix ist besser, wenn viele Einträge ungleich null sind.
Lab: Was bewertet wird
- Nicht-Nullen zählen10 Pkt.
- Wie viele Werte in einer Zeile10 Pkt.
- Die Dichte eines Gitters10 Pkt.
- Ein dünnbesetztes Produkt15 Pkt.
- Welches Format für welche Aufgabe15 Pkt.
- Ein tridiagonales System10 Pkt.
- Wann dünnbesetzt sich lohnt und wann nicht30 Pkt.