非常に大きなマトリックスで作業する必要がある Java アプリケーションに取り組んでいます。たとえば、2 つの 1000 万 * 1000 万の行列を乗算します。もちろん、Java ヒープには、これらの行列の 1 つを格納するだけでも十分なスペースがありません。私は何をすべきか？データベースを使用して行列を保存し、必要なすべての部分をメモリに取り込み、それを次々と乗算する必要がありますか?
8052 次
9 に答える
8
First off, a 10 million x 10 million matrix is simply enormous. Assuming doubles for each cell and no storage overhaed, each one of these things is going to be 800 terabytes. Just reading each cell once over from main memory (should it somehow magically fit there, which clearly isn't happening), would take days. Doing it from any sort of plausible SAN (we'll put it on 10GbE) is more likely to be months. And no matrix multiply has O(n) complexity - the normal approaches are O(n^3). So... you aren't doing this with memory mapped files, common databases, or anything of that sort.
Code doing something like this is going to live or die on cache efficiency, where "cache" includes making good use of main memory, local disk drives. Since any storage interface holding more than one 800 terabyte matrix is bound to be a SAN of some sort, you almost certainly involve multiple servers reading and working on different parts of it, too.
There are lots of well-known ways to parallelise matrix multiplication (essentially multiply various-sized sub-matrices and then combining the results), and shift layout so that the access patterns have reasonable cache locality by organizing the data around space-filling curves instead of row/column arrangements. You're certainly going to want to look at the classic LAPACK interfaces and design, Intel's MKL, GotoBLAS as implementations of the BLAS functions tuned to specific modern hardware, and after that you're probably venturing into unexplored territory :-)
于 2009-03-18T04:38:56.260 に答える
3
単純に実行した場合の行列乗算の複雑さは O(n^3) ですが、より効率的なアルゴリズムが存在します。とにかく、1000万 * 1000万のマトリックスの場合、これには非常に長い時間がかかり、同じヒープの問題に直面する可能性がありますが、再帰性があります。
複雑な数学に興味がある場合は、この記事で役立つツールを見つけることができます。
于 2009-03-16T12:53:00.153 に答える
2
http://hsqldb.org/のようなメモリ データベースの使用を検討してください。
于 2009-03-16T12:44:31.343 に答える
2
これは非常に膨大な計算であるため、ストレージの問題と並んでパフォーマンスの問題が発生すると思います。したがって、この問題を並列化し、複数のマシン/コアでデータのサブセットを処理することを検討します。
幸いなことに、行列乗算ソリューションは自然に分解されます。しかし、私は何らかの形のグリッドまたは分散コンピューティング ソリューションを検討しています。
于 2009-03-16T12:56:03.233 に答える
2
データに適用される疎行列アルゴリズムを使用します。(メモリ内データベース用の RAM は言うまでもなく、10^8 平方の double の非スパース行列を 3 つ保持するための 2.4 PB のディスク領域がないという前提で - Blue Gene/Q は「のみ」持っています1.6 PB )
于 2009-03-16T12:58:03.837 に答える
1
すべてのデータを外部ファイルに保存し、FileChannel オブジェクトを介してアクセスすることで、Memory Mapped Fileを使用してみてください。
MMF の簡単な紹介については、この記事を参照してください。
于 2009-03-16T16:32:10.953 に答える
1
Java を使用せざるを得ず、これをネイティブ メソッドとして処理するコードを作成できない場合 (つまり、代わりに C コードを呼び出すように Java に指示することによって)、最も効率的な方法は、単純なメソッドを適切に使用することです。バイナリーファイル。この場合、データベースは直接ファイルにアクセスするよりも遅く、データベースが提供する機能を必要としないため、データベースには近づきません。
于 2009-03-16T12:46:52.600 に答える
1
hadoopを見てください。
于 2009-03-16T12:54:02.193 に答える
0
于 2009-03-16T15:24:38.290 に答える