Ich arbeite an einer Java-Anwendung, die an sehr großen Matrizen arbeiten muss. Zum Beispiel Multiplikation von zwei 10 Millionen * 10 Millionen Matrizen! Natürlich hat der Java-Heap nicht genug Platz, um eine dieser Matrizen zu speichern. Was soll ich tun? Sollte ich Datenbanken verwenden, um meine Matrizen zu speichern und jedes benötigte Teil in den Speicher zu bringen und es nach dem anderen zu multiplizieren?Handle große Datenstruktur in Java
betrachten mit einem Speicher db wie http://hsqldb.org/
Dies ist ein RDB. Du meinst, ich kann jedes RDB für diesen Mittelwert benutzen ... zum Beispiel MySQL? Ist es effizient, eine DB zu verwenden? Ich meine, gibt es eine bessere Lösung (mit Speicherplatz oder ...). – user78564
Ich würde sagen "eingebettete" DB, weil HSQLDB kann viel mehr als reine In-Memory-Datenbanken. –
@unknown: Ja, ein RDB ist wahrscheinlich eine gute Idee dafür, da es entwickelt wurde, um große Datenmengen zu behandeln. Abhängig von Ihren genauen Anforderungen benötigen Sie möglicherweise speziellere Software, aber nach dem, was Sie geschrieben haben, würde ich eine relationale Datenbank vorschlagen. –
Nun, wenn Sie gezwungen sind, Java zu verwenden und den Code nicht schreiben kann, die mit dieser als native Methoden behandelt (das heißt, von Java sagen, stattdessen einige C-Code aufzurufen) wäre es am effizientesten, eine einfache Binärdatei zu verwenden. Ich würde in diesem Fall von Datenbanken fern bleiben, weil sie langsamer als der direkte Dateizugriff sind und Sie die von ihnen angebotenen Funktionen nicht benötigen.
Die Komplexität der Matrixmultiplikation ist, wenn sie naiv ausgeführt wird, O (n^3), aber effizientere Algorithmen existieren. Wie auch immer, für eine 10 Millionen * 10 Millionen Matrix wird dies eine sehr lange Zeit benötigen und Sie werden wahrscheinlich mit der gleichen Rekursionsproblematik konfrontiert werden.
Wenn Sie in komplexen Mathe sind, finden Sie möglicherweise Tool, um Ihnen in this article zu helfen.
Werfen Sie einen Blick auf hadoop.
Da dies eine so große Berechnung ist, werden Sie neben Ihren Speicherproblemen auch Leistungsprobleme bekommen. Also würde ich versuchen, dieses Problem zu parallelisieren und mehrere Maschinen/Kerne zu bekommen, um eine Teilmenge von Daten zu verarbeiten.
Zum Glück wird sich eine Matrixmultiplikationslösung natürlich zersetzen. Aber ich würde eine Form von Grid oder verteilter Computerlösung suchen.
Verwenden Sie den Sparse-Matrix-Algorithmus, der auf Ihre Daten angewendet wird. (unter der Annahme, dass Sie nicht 2,4 PB Speicherplatz haben, um 3 von 10^8 quadratischen nicht-dünn besetzten Matrizen von Doppel zu halten, geschweige denn so viel RAM für eine In-Memory-Datenbank - Blue Gene/Q 'nur' 1,6 PB.)
Werfen sie einen Blick auf CGL-MapReduce http://www.cs.indiana.edu/~jekanaya/cglmr.html#Matrix_Multiplication
Versuchen Memory Mapped File mit durch alle Ihre Daten in einer externen Datei zu speichern und den Zugriff darauf über Filechannel-Objekt.
Überprüfen Sie this article für eine kurze Einführung in MMF.
Zunächst einmal ist eine 10 Millionen x 10 Millionen Matrix einfach riesig. Unter der Voraussetzung, dass für jede Zelle verdoppelt und kein Speicher überholt wird, wird jedes dieser Dinge 800 Terabyte betragen. Jede Zelle einmal aus dem Hauptspeicher zu lesen (sollte es irgendwie magisch passen, was eindeutig nicht passiert), würde Tage dauern. Es ist wahrscheinlicher, Monate von irgendeinem plausiblen SAN zu machen (wir werden es auf 10GbE setzen). Und keine Matrix multipliziert hat O (n) Komplexität - die normalen Ansätze sind O (n^3). Also ... machen Sie das nicht mit Memory-Mapped-Dateien, gewöhnlichen Datenbanken oder irgendetwas dergleichen.
Code, der so etwas tut, wird auf Cache-Effizienz leben oder sterben, wobei "Cache" die Verwendung von Hauptspeicher, lokalen Festplattenlaufwerken beinhaltet. Da jede Storage-Schnittstelle, die mehr als eine 800-Terabyte-Matrix enthält, ein SAN irgendeiner Art sein muss, sind Sie fast sicher, dass mehrere Server verschiedene Teile davon lesen und bearbeiten.
Es gibt viele bekannte Wege Matrixmultiplikation (im Wesentlichen multiplizieren verschiedene Größe Untermatrizen und dann Kombinieren der Ergebnisse) parallelisieren und Layout zu verschieben, so dass die Zugriffsmuster angemessenen Cache Ort haben, indem die Daten um space-filling curves organisieren anstelle von Zeilen-/Spaltenanordnungen. Sie werden sicherlich die klassische LAPACK Schnittstellen und Design, Intel's MKL, GotoBLAS als Implementierungen der BLAS-Funktionen auf bestimmte moderne Hardware abgestimmt aussehen, und danach werden Sie wahrscheinlich in unerforschtes Gebiet wagen :-)
ist die Matrix spärlich durch Zufall? – TrayMan
ja. es kann in vielen Fällen sein. aber wir können nicht sicher sein. – user78564
Was versuchen Sie zu erreichen? Wahrscheinlich ist das nicht der richtige Weg. – starblue