Kompression dünnbesetzer Matrizen (sparse matrices)

[Besserwissend]

Hallo,

Ich habe einige Matrizen die (mehr oder weniger zufällig) relativ dünn besetzt sind.
Die Dinger sind nicht besonders groß (max. 1000x1000).

Da ich häufig auf die Werte zugreifen muß, sollte der Zugriff auf die Werte sehr schnell (also keine großartigen Transformationen) von Statten gehen.
Die Kompression an sich kann ruhig komplex sein.
Bisher hab ich das mit "row displacement dispatch tables"
gelöst, die erzielte Platzersparnis ist jedoch eher "suboptimal".
Gibts da noch was Besseres?

[rotalever]

Da ich häufig auf die Werte zugreifen muß, sollte der Zugriff auf die Werte sehr schnell (also keine großartigen Transformationen) von Statten gehen.
Die Kompression an sich kann ruhig komplex sein.
Widerspricht sich das nicht irgendwie?

[Besserwissend]

Widerspricht sich das nicht irgendwie?
Ich meinte das ungefähr so:

Transformation Matrix -> "komprimierte Matrix"/Datenstruktur (schreiben): mit komplexen Operationen ("teuer", "variabel", O(n^x) etc. )

komprimierte Matrix -> Inhalt der Matrixzellen der Ursprungsmatrix (lesen): mit einfachen Operationen ("billig", "konstant", O(1) etc. )

Was mir noch eingefallen ist, ist die ganze Geschichte mit einer geeigneten Funktion 2 dimensional zu Hashen .
Das Problem ist, daß die Daten einfach keine "Struktur" haben, die man irgendwie ausnutzen kann.

[Madgen]

Je nach dem was du machst könntest du direkt Hashtabellen benutzen. Um schnell an den Schlüssel für den ursprünglichen Index zu kommen kannst du dir die 1000*1000 möglichen Schlüssel in eine Matrix schreiben ;)

[Eruphus]

Je nach dem was du machst könntest du direkt Hashtabellen benutzen. Um schnell an den Schlüssel für den ursprünglichen Index zu kommen kannst du dir die 1000*1000 möglichen Schlüssel in eine Matrix schreiben ;)

Würde ich auch machen.

Mit einem unsigned INT (max 2^32-1) dürftest ohne Probleme eine Matrix von 65536x65536 verhashen können.
Mit unsigned LONG (max 2^64-1) sogar 2^32 x 2^32.

Dabei würde ich aber nicht auf eine bestehende HASH implementation alà M$ (MFC) zurückgreifen sondern eine alternative suchen oder selbst etwas implementieren.

MFG
Eruphus


//edit :

o = breite der Matrize
p = höhe der Matrize

wenn n die durchschnittliche Anzahl der gespeicherten Elemente
und m die "toleranz" für die Berechnung ist,

dann kann mann den Hashtable auf nxm reduzieren...
Dann erstelle auf eine Array mit (nxm) Elementen...
dann is die der Hashwert (((o*y+x)%n)+1)*m und speicher den wert dort.
sollte der wert (dieser Arrayplatz) schon vergeben sein, dann benütze +-(m-1) Werte um deinen Hashwert
um die freien Plätze zu belegen.

du kannst auch 2 Matrizen benützen um in einem eine Art "Zeiger" zu verwalten und in der andern
die eigentliche Speicherung zu realisieren.


Angaben ohne gewähr....
Morgen mehr, wenn ich wieder nüchtern bin .)

[transstilben]

Hallo,

Ich habe einige Matrizen die (mehr oder weniger zufällig) relativ dünn besetzt sind.
Die Dinger sind nicht besonders groß (max. 1000x1000).

Was heißt denn relativ dünn ? Zu < 2 % besetzt oder zu < 20 % ?
Zur Lösung von sehr dünn besetzten sehr großen Bedingungsmatrizen hat mich beispielsweise die Kompression im Rahmen des DLX-Algorithmus von Donald E. Knuth sehr beeindruckt.

[Besserwissend]

Ich habe die Dancing Links-Sache (DLX) mal überflogen.
Was heißt denn relativ dünn ? Zu < 2 % besetzt oder zu < 20 % ?
in der Regel <4%; in (seltenen) Ausnahmefällen mal mehr.

Zur Lösung von sehr dünn besetzten sehr großen Bedingungsmatrizen hat mich beispielsweise die Kompression im Rahmen des DLX-Algorithmus von Donald E. Knuth sehr beeindruckt.

Die doppelt verketteten Listen? Da ist der Zugriff fast ein bischen zu teuer.
Das geht dann nur gut für auserordentlich dünn besetzte Matrizen.

Mit dem Exact Cover des DLX Algorithmus sieht die Sache gar nicht mal so schlecht aus.
Jetzt muß ich nur schauen wie man die ganze Geschichte auf das Exact Cover Problem abbilden kann, da die Elemente meiner m*n Matrix <=m sind. Wenn ich den DLX-Algorithmus "out-of the box" laufen lasse, bekomme ich ja nur eine minimale??? Anzahl von Matrixzeilen, die andere Zeilen unabängig vom Inhalt der Zellen überdecken.
Davon abgesehen, es muß doch gar keine Lösung für das Exact Cover-Problem geben?

[transstilben]

Ich habe die Dancing Links-Sache (DLX) mal überflogen.

in der Regel <4%; in (seltenen) Ausnahmefällen mal mehr.


Die doppelt verketteten Listen? Da ist der Zugriff fast ein bischen zu teuer.
Das geht dann nur gut für auserordentlich dünn besetzte Matrizen.


Genau und deshalb kam meine Nachfrage was "relativ dünn" in Deinem Kontext bedeutet. Ich hatte es z.B. mit einer Matrix mit 7733 Spalten und ca. 1320000 Zeilen zu tun und 0.48 % der Matrixelemente waren
besetzt. Die Matrix hat in der Darstellung als doppelt verkettete Liste mit ca. 750 MB gerade so eben noch in meinen Hauptspeicher gepaßt.