Darstellen einer 100K X 100K-Matrix in Java

Die Colt -Bibliothek hat eine spärliche Matrix-Implementierung für Java.

Sie können auch Berkeley DB als Speichermodul verwenden.

Wenn Ihr Computer jetzt über genügend tatsächlichen Arbeitsspeicher verfügt (mindestens 9 Gigabyte frei), können Sie die Größe des Heapspeichers in der Java-Befehlszeile erhöhen.

Wenn die überwiegende Mehrheit der Einträge in Ihrer Matrix Null ist (oder sogar ein anderer konstanter Wert), ist eine dünne Matrix geeignet. Andernfalls könnte es möglich sein, den Algorithmus neu zu schreiben, so dass die gesamte Matrix nicht gleichzeitig existiert. Sie können z. B. jeweils eine Zeile erstellen und konsumieren.

100.000 x 100.000 = 10.000.000.000 (10 Milliarden) Einträge. Selbst wenn Sie Einzelbyte-Einträge speichern, ist dies immer noch in der Nähe von 10 GB - hat Ihr Computer sogar so viel physischen Speicher, geschweige denn einen Willen, so viel zu einem einzigen Prozess zuzuweisen?

Vermutlich müssen Sie einen Weg finden, nur einen Teil der Matrix zu einem bestimmten Zeitpunkt im Speicher zu behalten und den Rest auf der Festplatte zwischenzuspeichern.

Es gibt eine Anzahl möglicher Lösungen, abhängig davon, wie viel Speicher Sie haben, wie dünn das Array tatsächlich ist und wie die Zugriffsmuster aussehen.

Wenn die Berechnung von 100K * 100K * 8 kleiner ist als die Menge an physischem Speicher auf Ihrer Maschine zur Verwendung durch die JVM, ist eine einfache nicht-spärliche Anordnung eine brauchbare Lösung.

Wenn das Array spärlich ist und z. B. 75% oder mehr der Elemente null sind, können Sie Speicherplatz sparen, indem Sie eine Sparse-Array-Bibliothek verwenden. Es wurden verschiedene Alternativen vorgeschlagen, aber in jedem Fall müssen Sie noch herausfinden, ob Sie dadurch genügend gespart haben. Finden Sie heraus, wie viele Elemente ungleich Null sein werden, multiplizieren Sie diese mit 8 (um Ihnen Doppel zu geben) und (sagen wir Sie) 4, um die Gemeinkosten des Sparse-Arrays zu berücksichtigen. Wenn das weniger ist als die Menge an physischem Speicher, die Sie der JVM zur Verfügung stellen können, dann sind Sparse-Arrays eine brauchbare Lösung.

Wenn sparse und nicht-spärliche Arrays (im Speicher) nicht funktionieren, werden die Dinge komplizierter und die Machbarkeit einer Lösung hängt von den Zugriffsmustern für die Array-Daten ab.

• Ein Ansatz besteht darin, das Array als eine Datei darzustellen, die in Form eines MappedByteBuffer in den Speicher abgebildet wird. Angenommen, Sie haben nicht genug physischen Speicher, um die gesamte Datei im Speicher zu speichern, werden Sie das virtuelle Speichersystem hart treffen. Daher ist es am besten, wenn Ihr Algorithmus zu jedem Zeitpunkt nur auf zusammenhängenden Teilen des Arrays arbeiten muss. Andernfalls werden Sie wahrscheinlich durch den Austausch sterben.

• Ein zweiter Ansatz ist eine Variation des ersten. Ordnen Sie das Array / die Datei Abschnitt für Abschnitt zu und wenn Sie fertig sind, heben Sie die Zuordnung auf und wechseln Sie zum nächsten Abschnitt. Dies funktioniert nur, wenn der Algorithmus in Abschnitten auf dem Array arbeitet.

• Ein dritter Ansatz besteht darin, das Array unter Verwendung einer Datenbank mit geringem Gewicht wie BDB darzustellen. Dies ist langsamer als bei jeder In-Memory-Lösung, da das Lesen von Array-Elementen in Disc-Zugriffe umgesetzt wird. Aber wenn Sie es falsch verstehen, wird es nicht das System wie die Memory-Map-Ansatz wird töten. (Und wenn Sie dies unter Linux / Unix tun, beschleunigt der Disk-Block-Cache des Systems möglicherweise die Geschwindigkeit, je nach dem Array-Zugriffsmuster Ihres Algorithmus)

• Ein vierter Ansatz besteht darin, einen verteilten Speichercache zu verwenden. Dies ersetzt Disc-I / O durch Netzwerk-I / O, und es ist schwer zu sagen, ob dies eine gute oder schlechte Sache ist.

• Ein fünfter Ansatz besteht darin, Ihren Algorithmus zu analysieren und zu prüfen, ob er als verteilter Algorithmus implementiert werden kann; z.B. mit Abschnitten des Arrays und entsprechenden Teilen des Algorithmus auf verschiedenen Maschinen.

Sie können auf dieses System aktualisieren:

Ссылка

864 Prozessorkerne und 768 GB Speicher kostet nur ein Einfamilienhaus irgendwo.

Nun, ich schlage vor, dass Sie die Speicherkapazität in Ihrem jvm erhöhen, aber Sie werden eine Menge Speicher benötigen, da Sie über 10 Milliarden Elemente sprechen. Es ist (kaum) möglich mit viel Speicher oder einem gruppierten jvm, aber das ist wahrscheinlich die falsche Antwort.

• Sie erhalten den outOfmemory, denn wenn Sie int [1000] deklarieren, wird der Speicher sofort zugewiesen (zusätzlich verdoppelt sich der Speicherplatzbedarf mehr als ints - eine int-Repräsentation spart auch Platz). Vielleicht können Sie eine effizientere Implementierung Ihres Arrays ersetzen (wenn Sie viele leere Einträge haben, suchen Sie nach "spärlichen Matrix" -Darstellungen).

• Sie können Teile in einem externen System speichern, z. B. Memcached- oder Memory-Mapped-Puffer.

Es gibt viele gute Vorschläge hier, vielleicht, wenn Sie eine ausführlichere Beschreibung des Problems, das Sie versuchen zu lösen, könnten die Menschen spezifischer sein.

Sie sollten ein "externes" Paket ausprobieren, um mit Matrizen umzugehen, das habe ich aber nie gemacht, vielleicht etwas wie jama .

Wenn Sie nicht 100K x 100K x 8 ~ 80GB Speicher haben, können Sie diese Matrix nicht im Speicher erstellen. Sie können diese Matrix auf dem Datenträger erstellen und mit Speicherzuordnung darauf zugreifen. Die Verwendung dieses Ansatzes wird jedoch sehr langsam sein.

Was versuchst du zu tun? Sie können feststellen, dass die Darstellung Ihrer Daten auf eine andere Weise viel effizienter ist.