Wir haben eine Anwendung, die eine dünn besetzte Matrix speichert. Diese Matrix enthält Einträge, die hauptsächlich um die Hauptdiagonale der Matrix existieren. Ich habe mich gefragt, ob es effiziente Algorithmen (oder existierende Bibliotheken) gibt, die solche spärlichen Matrizen effizient handhaben können? Vorzugsweise wäre dies eine generische Implementierung, bei der jeder Matrixeintrag ein benutzerdefinierter Typ sein kann.
Bearbeite als Antwort auf eine Frage / Antwort:
Wenn ich hauptsächlich über die Hauptdiagonale sage, meine ich, dass die Merkmale der meisten Matrizen darin bestehen, dass die meisten Einträge außerhalb der Hauptdiagonalen gruppiert sind, aber Nullen in der Nähe der Diagonalen vorhanden sein können und Werte ungleich Null sein können weit weg von der Diagonale. Ich möchte etwas effizientes für die meisten Fälle hier.
Wofür werde ich das verwenden? Ich brauche einen effizienten Zugriff auf alle Werte in einer Zeile oder auf alle Werte in einer Spalte. Die gespeicherten Werte wären boolesche Werte. Ein Beispiel wäre:
Dies wurde bisher nur mit verketteten Listen gemacht, war aber sehr verwirrend zu implementieren. Ich hatte gehofft, dass ich mit einer spärlichen Matrix den Algorithmus verbessern könnte, aber es hat sich als schwierig erwiesen, den "richtigen" Typ des Sparse-Matrix-Algorithmus zu finden.
ps. Danke für die Antworten bisher
Sie könnten einen Index basierend auf der [row, col] der Zelle verwenden. Da die Daten auf einer Diagonale liegen, ist der typische Ansatz zum Speichern des Zeilenindex und der zugehörigen Spalten-Indices mit Daten nicht optimal. Hier ist ein Code, den Sie verwenden könnten:
%Vor% Beachten Sie, dass Sie, wenn T eine Struktur ist, möglicherweise die IsCellEmpty aufrufen müssen, da der Inhalt einer Zelle nicht null ist und den Standardwert für diesen Typ hat. Sie können den Code auch erweitern, um Ihnen eine schnelle "SparseRatio" basierend auf der Size Eigenschaft und _cells.Count zu geben.
BEARBEITEN:
Nun, wenn Sie interessant sind, ist Geschwindigkeit, können Sie den Kompromiss von Raum gegen Geschwindigkeit tun. Anstatt nur ein Wörterbuch zu haben, habe drei! Es verdreifacht deinen Raum, aber es macht das Aufzählen in jeder Weise, die du willst, wirklich einfach. Hier ist ein neuer Code, der folgendes zeigt:
%Vor% Wenn Sie über alle Einträge iterieren möchten, verwenden Sie _cells . Wenn Sie alle Zeilen für eine bestimmte Spalte verwenden möchten, verwenden Sie _columns . Wenn Sie alle Spalten in einer bestimmten Zeile verwenden möchten, verwenden Sie _rows .
Wenn Sie in sortierter Reihenfolge iterieren möchten, können Sie LINQ in den Mix einfügen und / oder eine sortierte Liste mit einer inneren Klasse verwenden, die einen Eintrag kapselt (der die Zeile oder Spalte speichern und% co_de implementieren müsste) %, damit die Sortierung funktioniert.)
Ich denke, ein Dictionary<int, Dictionary<int, object >> würde ausreichen.
Ich habe es nicht benutzt, aber NMath Matrix behandelt diese (nicht frei).
Auch Extreme Optimization Numerical Libraries für .NET (nicht kostenlos).
Hier ist ein kostenloses: Math.NET-Projekt (speziell MathNet.Numerics.LinearAlgebra.Sparse-Namespace )
Hier sind zwei Fragen:
"Meist um die Hauptdiagonale" ist zu vage. Wenn die Elemente in Bändern liegen, dann verwenden Sie die Bandspeicherung der Bänder selbst als Vektoren, die von der Hauptdiagonalen versetzt sind. Wenn die Elemente in der Nähe der Hauptdiagonalen zufällig verteilt sind, verwenden Sie entweder eine gebänderte Form, die einige Nullen in den Bändern enthalten kann, oder verwenden Sie eine reine, dünne Form, die nur die Elemente und ihre Positionen im Array speichert.
>Was machen Sie mit der Matrix? Wenn Ihr Ziel lediglich eine effiziente Speicherung ist, ist eine gebänderte Form effizient und bietet schnellen Zugriff auf jedes Element. Wenn Sie lineare Algebra mit der Matrix machen, aber niemals mehr als Matrix Vektor multipliziert, dann wird die gebänderte Form immer noch prächtig funktionieren. Wenn Sie mit Matrix -Matrix-Multiplikationen oder Matrix-Faktorisierungen arbeiten, wobei Fill-In zu einem Problem wird, dann kann eine reine Sparse-Form geeigneter sein. Zum Beispiel wird das Produkt von zwei gebänderten Matrizen zusätzliche Banden haben, so dass das Produkt von zwei tridiagonalen Matrizen pentadiagonal ist. Für eine Faktorisierung sind Umordnungen manchmal nützlich, um das Ausfüllen zu minimieren. (AMD ist eine Wahlmöglichkeit, Ungefähre Minimum-Grad-Permutation, aber es gibt andere Schemata.)
Ich denke, dies könnte durch Verwendung einer Klasse durchgeführt werden, die ein einfaches Array hält, wobei der horizontale Offset gespeichert wird, der zwischen den Matrixzeilen angewendet wird und der Streifen einer Zeile definiert wird, z. die Anzahl der gültigen Einträge. Für eine große Matrix, in der nur diagonale und zwei benachbarte Elemente definiert sind, würden Sie ein Array aus 3 * Anzahl von Zeilen erstellen und 3 als Stripe-Breite speichern. Der Offset hängt von der Größe der Matrix ab.
Ich bin mir nicht bewusst, was frei ist, was das schon tut.
Hier finden Sie eine Liste allgemeiner Datenstrukturschemas . Jede hat ihre Vor- und Nachteile und eignet sich für leicht unterschiedliche Probleme, bei denen dünne Matrizen entstehen. Sie möchten sie wahrscheinlich über vorhandene Datenstrukturen wie List & lt; & gt; und Wörterbuch & lt; & gt ;.
Tags und Links .net performance sparse-matrix