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 machen? Sollte ich Datenbanken benutzen, um meine Matrizen zu speichern und jedes benötigte Teil in den Speicher zu bringen und es nach dem anderen zu multiplizieren?
Zunächst einmal ist eine 10 Millionen x 10 Millionen große 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 macht, wird mit der Cache-Effizienz leben oder sterben, wobei "Cache" das Verwenden von Hauptspeicher, lokalen Plattenlaufwerken, beinhaltet. Da jede Storage-Schnittstelle, die mehr als eine 800-Terabyte-Matrix enthält, ein SAN irgendeiner Art sein muss, involvieren Sie fast sicher mehrere Server, die an verschiedenen Stellen davon lesen und arbeiten.
Es gibt viele bekannte Möglichkeiten, die Matrixmultiplikation zu parallelisieren (im Wesentlichen Mehrfach-Submatrizen zu multiplizieren und dann die Ergebnisse zu kombinieren) und das Layout so zu verschieben, dass die Zugriffsmuster eine vernünftige Cache-Lokalität aufweisen, indem die Daten um raumfüllende Kurven anstelle von Zeilen / Spalten-Anordnungen. Sie werden sicherlich die klassischen LAPACK -Schnittstellen und -Design sehen wollen, Intels MKL , GotoBLAS als Implementierungen der BLAS-Funktionen, die auf bestimmte moderne Hardware abgestimmt sind, und danach wagt man sich wahrscheinlich in unerforschtes Gebiet: -)
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 sehr lange dauern und Sie werden wahrscheinlich mit der gleichen Rekursivität konfrontiert werden.
Wenn Sie sich mit komplexer Mathematik beschäftigen, finden Sie unter diesen Artikel , der Ihnen hilft.
>Da dies eine so große Kalkulation ist, werden Sie neben Ihren Speicherproblemen 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 auf irgendeine Form von Grid oder verteilter Rechenlösung schauen.
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.)
Nun, wenn Sie gezwungen sind, Java zu verwenden und den Code, der sich damit beschäftigt, nicht als native Methoden schreiben können (dh indem Sie Java anweisen, stattdessen C-Code aufzurufen), wäre es am effizientesten, dies zu tun Verwenden Sie eine einfache Binärdatei. 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.
Versuchen Sie es mit Memory Mapped File , indem Sie alle Ihre Daten in einer externen Datei speichern und über das FileChannel-Objekt darauf zugreifen.
Sehen Sie sich diesen Artikel für eine kurze Einführung in MMF an.