Daten zu groß für Liste. Alternativen von Experten?

Hallo MyC#-Freunde,

Ich hab mal eine generelle Frage. Ich hab zwei Listen mit jeweils 2000 Elementen und ich möchte eine mathematische Operation zwischen beiden Listen machen. Ich erhalte also eine 2000x2000 Matrix (also 4 Mio Elemente). Leider komme ich an meine Rechnergrenzen damit, da dann der Speicher für eine Ergebnisliste zu groß wird.

Wie würdet ihr das Problem lösen? Ich selber hab keine Ahnung von Linq und suche eine Möglichkeit schnell auf einzelne Elemente zuzugreifen. Nach dem Motto: "Ich hab jetzt mal für Zelle [1000, 1000] den Wert X berechnet und möchte nur diesen einen Wert in Tabelle Y schreiben." und umgedreht "Welcher Wert befindet sich an Position [x, y]?". Das natürlich in maximaler Geschwindigkeit. Kleines Beispiel wär super.

Hi digi333,

was sind es denn für Eingabedaten ? (die beiden Listen) Wie groß sind die Einzelnen Elemente? Und was genau ist denn deine mathematische Operation?
Und vor allem: Was sind deine Ergebnisse? Also was für ein Typ?
Ich mein: 4Mio Bytes wäre ja nun nicht viel.
Und wie hängt die Ergebnisliste mit der Matrix zusammen?

Aber grundsätzlich:
Hier ist mal wieder ein Time-Space-Tradeoff.

Berechne einfach alle Werte "live", wenn darauf zugegriffen wird.
Damit sparst du dir die komplette Matrix, zum Preis einer schlechteren Performance.
Falls du mehrfach auf die selben Werte zugreifst, kannst du diese ja auch zwischenpuffern.
Abspeichern könntest du das ganze dann als dünnbesetzte (sparse) Matrix, wo nur die wichtigen Elemente (mit ihrer Position) gespeichert sind.

Den Index-Operator kannst du dann ja auch überladen, sodass das Feeling nach außen hin das selbe bleibt.

Das ganze klappt natürlich super, wenn die Berechnungen der Werte der einzelnen Matrix-Zellen komplett unabhängig voneinander sind. Also das Berechnen der ganzen Matrix auch n^2 mal so lange dauert wie von einem einzigen Wert.

Problematisch wirds nur wenn dass das Berechnen eines einzigen Wertes fast so lange dauert wie das Berechnen aller. (weil vielleicht alle mit einbgezogen werden) Das wär natürlich schlecht 😃
Aber vielleicht kann man auch an deiner Berechnung einige Schritte "entkoppeln", sodass das obige Verfahren dann doch wieder machbar wäre.

Also: rück mal mit ein paar Zusatzinfos raus.
beste Grüße
zommi

Ui, es gibt ein Wiki-Symbol, chic 😃

Die Matrix ist leider das Ergebnis. Heißt ich benötige schon komplett die Matrix. Einzelne Sachen berechnen dauert leider auch lange, da die Berechnung einer Zelle über mehrere Projekte hinweg geht. Es sind eigentlich nur 4 Mio Double-Werte. Die Ergebnismatrix möchte ich weiter mit Algorithmen optimieren und Berechnungen darauf ansetzen. Es handelt sich dabei um Cluster Analysen. Also eine neue Berechnung für jedes Element wäre sehr aufwändig.

Hallo digi333

Du wirst wohl dine Berechnung etwas detailierter beschreiben müssen. Grundsätzlich sind 4mio Berechnungen, wie bereits angedeutet, ja kein Problem.

Es sind eigentlich nur 4 Mio Double-Werte

Du sagst es 🙂 Stören dich nun die 30MB?

Leider komme ich an meine Rechnergrenzen damit, da dann der Speicher für eine Ergebnisliste zu groß wird.

Das versteh ich nun nicht ?!

Die 30MB sollten nun wahrlich nicht deinen PC in die Knie zwingen. Egal mit was für einer Möhre du arbeitest. 😉

Die Ergebnismatrix möchte ich weiter mit Algorithmen optimieren und Berechnungen darauf ansetzen.

Dabei solltest du nur darauf achten, dass die Algorithmen möglichst alle In-Place arbeiten. Also wenns geht alle auf dem Original. Ohne ständig zig Kopien anzulegen.

beste Grüße
zommi

Es sind eigentlich nur 4 Mio Double-Werte
Du sagst es 😃 Stören dich nun die 30MB?

Leider komme ich an meine Rechnergrenzen damit, da dann der Speicher für eine Ergebnisliste zu groß wird.
Das versteh ich nun nicht ?!

Die 30MB sollten nun wahrlich nicht deinen PC in die Knie zwingen. Egal mit was für einer Möhre du arbeitest. 😉

Sorry... Ich hab noch mal nachgeschaut. Ich rede von sehr viel größeren Matrizen. Der Speicher geht über meine 3 GB Arbeitsspeicher. Ich benötige definitiv eine Datenauslagerung in SQL, MySQL, Linq etc. Irgendwas wo ich halt gut und schnell "Get" und "Set" Methoden verwenden kann.

Hi digi333,

tja nagut dann brauchst du wohl wirklich eine Datenauslagerung 😉

Das Einfachste (+Beste) ist dann einfach eine Datei. Die Schreibst du und liest du.
Eventuell pufferst du noch Zusammenhängende Blöcke zwischen (um einen sequentiellen Zugriff zu beschleunigen)

Aber eine Datenbank bringt da nix.
Deine Daten sind eine Matrix. Die speicherst du zeilenweise ab.
Und dein Zugriff erfolgt über den Index, du weißt also sofort an welcher Position was liegt! Besser gehts nicht.

Du musst ja hier nicht anhand eines Schlüssels erst den Datensatz suchen
(=> Da wär Datenbank besser, die organisiert die Tabellen ja intern in cleveren Datenstrukturen die das Suchen blitzschnell machen, während man selbst wahrscheinlich Datensatz für Datensatz abklappert und die Schlüssel vergleicht)

Somit kanns du "SQL, MySQL, Linq etc." vergessen. Durch den Overhead KANN es nur langsamer werden, als mit einem direkten Dateizugriff.

Also zeilenweise abspeichern und mittels

(AktuelleZeile * Zeilenlänge + AktuelleSpalte)*sizeof(double)

die Seek-Position berechnen und lesen/schreiben.

Wie oben schon erwähnt lohnt sich es sich für den sequentiellen Zugriff gleich mehrere aufeinanderfolgende Werte zu lesen und zu puffern. (Quasi wie ein ProzessorCache - Prinzip der räumlichen Lokalität)

• Wobei Windows sowas ja schon intern macht, ist also fraglich ob ein eigener Buffer da noch was bringt.

Aber: noch ne andere Frage.
Bei deiner Matrix-Datenverarbeitung. Was kommt da ganz am Ende raus?
5GB an Ergebnisdaten? Wohl eher nicht.
Also vielleicht kannst du ja deine (reduzierenden) weiteren Verarbeitungsschritte gleich schon beginnen lassen, ++während ++ die Matrix aufgebaut wird.
Dann brauchst du sie zu keinem Zeitpunkt komplett und damit auch gar nicht erst abspeichern

beste Grüße
zommi

Danke