32678 個の頂点を持つ完全なグラフのランダム エッジを生成しています。つまり、5 億 + 値です。
HashMap を使用して、エッジをキーとして使用し、ランダムなエッジの重みを値として使用しています。私は遭遇し続けます：
スレッド「メイン」の例外 java.lang.OutOfMemoryError: java.lang.StringBuilder.toString(StringBuilder.java:430) の Java ヒープ領域 pa1.Graph.(Graph.java:60) の pa1.Main.main(Main)ジャバ:19)
このグラフは、最小スパニング ツリーを構築するために使用されます。
より良いデータ構造またはアプローチに関するアイデアはありますか?
より多くのメモリを割り当てるためのオーバーライドがあることは知っていますが、そのまま機能するソリューションを好みます。
AHashMapは非常に大きくなりDoublesます。これは、8 バイトよりもかなり大きい (大文字の D を含む) が含まれるためです。（言うまでもなくEntry）実装とCPUチップに依存しますが、少なくともそれぞれ16バイト、おそらくそれ以上だと思いますか？
一次データを巨大に保つことを検討する必要があると思いますdouble[]（または、ある程度の精度を確保できる場合は、 a float[]）。これにより、メモリ使用量が簡単に 2 倍または 4 倍削減されます。(500M float は「単なる」2GB です) 次に、この配列に整数インデックスを使用して、エッジと頂点を実装します。たとえば、エッジは int[2] である可能性があります。これは OO とはほど遠いものであり、深刻な手を振っています。（そして、あなたがやろうとしていることのすべてのニュアンスを理解していません）
スタイルは非常に「昔ながら」ですが、必要なメモリははるかに少なくなります。
修正 - エッジは int[4]、頂点は int[2] である可能性があると思います。しかし、あなたはその考えを理解します。実際には、エッジと頂点の場合、少数のオブジェクトがあり、それらにはおそらく「実際の」オブジェクト、マップなどを使用できます...
完全なグラフなので、エッジが何であるかに疑いはありません。これらのエッジのラベルを、特定の順序で並べられた単純なリストに保存するのはどうですか? たとえば、ノードが 5 つある場合、エッジの重みは次のように並べられます{1,2}, {1,3} {1,4} {1,5} {2,3} {2,4} {2,5} {3,4} {3,5} {4,5}。
ただし、@BillyO'Neal が指摘したように、これはまだ 8 GB のスペースを占有する可能性があります。このリストを複数のファイルに分割し、これらのファイルのインデックスを同時に維持して、1 つのファイル内の 1 つの重みのセットがどこで終わり、次の重みのセットがどこで始まるかを示すことができます。
さらに、グラフの MST を見つけているので、次の論文も参照してください: http://cvit.iiit.ac.in/papers/Vibhav09Fast.pdf。この論文は、Boruvka のアルゴリズムに基づいているようです ( http://en.wikipedia.org/wiki/Bor%C5%AFvka 's_algorithm; http://iss.ices.utexas.edu/?p=projects/galois/benchmarks /mst )。