Dynamische wachsende Matrix speichern

bauherr007

Grünschnabel
Hallo zusammen !

Ich suche eine Möglichkeit eine dyamisch wachsende
Matrix abzuspeichern. Ich habe das mit Vektoren versucht,
was aber bei Matrizen mit 20000 Unbekannten schon
zu lange dauert.

Beispiel:

fertige Matrix wäre z.B. :

0 6 8
2 2 9
3 5 0

Ich brauche die Matrix in folgender Form gespeichert:

Ein Feld für die eigentlichen Werte (ohne Nullen), ein Feld für die Anzahl der Einträge in jeder Spalte (aufsummiert) und ein Feld für die Position in der jeweiligen Spalte. Diese Informationen müssen sortiert vorliegen.

Für die Matrix oben wäre das dann:

iSumColumEntries[] = {2 3 2}

Einträge Spalte 0 -> 2 Einträge
Einträge Spalte 1 -> 3 Einträge
...

Diese Einträge stehen an der Position:

IColPosition [ ] = {1 2 0 1 2 0 1 }

Hier stehen also Werte in der ersten Spalte an Position 1 und 2
Hier stehen also Werte in der zweiten Spalte an Position 0,1 und 2
....

Diese Werte MÜSSEN leider sortiert sein. Es muss also Spalte für
Spalte und darin Zeile für Zeile gespeichert werden (wenn Wert vorhanden).

Mit dieser Information hat man den Wert aus:

dMatrixEntries [] = { 2 3 6 2 5 8 9 }

Das ist das Ziel.

Leider setzt sich die Matrix stückweise zusammen.
D.h. ich weiß zwar, wie lang die Matrix bzw. die rechte Seite ist, aber ich
weiß nicht wie viele Einträge sie am Schluß hat (dynamsiche Felder, die sich entsprechend anpassen sind nötig). Die Einträge an der jeweiligen Position setzten sich dabei auch stückwiese zusammen. Das heißt der Wert z.B. an der
Position [0,3] (hier 8) kann sich nach und nach aus kleinen Werten zusammensetzten. Manche Werte können sich aber auch zu Null ergeben, so
daß diese wieder rausgefiltert werden müssen.

Ich habe mir als erstes überlegt zunächst alle Werte als Paare in 3 Arrays zu speichern, die ich mit realloc vergrößern könnte. Hier speichere ich alle Paare
zunächst ab.

I 1 0 2 1 1 0 0 ....
J 1 2 2 2 1 0 0 ....
Wert 1 8 0 9 1 -1 1 .....

Danach summiere ich alle doppelten Einträge auf, dann alle Nullen löschen
und dann sortieren. Leider ist das nicht so gut, weil die Matrix z.B. 100000
Zahlenpaare hat, aber nach dem summieren und löschen der Nullen nur noch
5000 wirkliche Einträge hat.

Dann habe ich 2D Vektoren genommen, die sich dynamisch aufziehen.
Ich habe mit Iteratoren direkt sortieren lassen( wenn neuer Eintrag)
und summieren lassen, wenn bekannt. Hat auch prima funktioniert, aber
leider viel zu langsam. Die Matrizen, die ich letztendlich löse, haben
ca. 3-4 Millionen Einträge.

Ich dacht an Listen oder ähnliches ....

Wer hat ein gute effiziente und schnelle Lösung ?

Für Eure Hilfe Vielen Dank

Markus
 

Neue Beiträge

Zurück