7

オブジェクト (私の場合はエッジ) に整数を割り当てるために使用できる実装済みのデータ構造はありますか? ファイルからグラフを読み取り、10 ミルの頂点、60 ミルのエッジ、マップ (cost.put(e,cost)) を使用して各エッジにコストを割り当てます。

この方法でコスト マップを作成します。

costs = new HashMap<Edge,Integer>();

それが与える例外は次のとおりです。

java.lang.OutOfMemoryError: Java heap space
    at java.util.HashMap.resize(Unknown Source)
    at java.util.HashMap.addEntry(Unknown Source)
    at java.util.HashMap.put(Unknown Source)
4

8 に答える 8

6

HashMap基本的な の正しいデータ構造ですMap。あなたが抱えている問題は、ファイルの内容をメモリに保持するのに十分なスペースを予約するように JVM に指示されていないことです。-Xmxフラグを指定して JVM を開始します。たとえば、-Xmx1Gパラメーターにより、1 ギガバイトのメモリを使用できます。

于 2012-10-31T09:17:28.410 に答える
6

6e7 のエッジがあります。プレーン オブジェクトは 24 バイト (64 ビット HotSpot) を必要とするため、1.44e9 バイト (1.5 GB) になります。ここで、6e7 参照と 6e7Integerオブジェクトのみを追加して、想像できる最も効率的なマップを紹介します。これは、refs 用にさらに 2.4e8 バイト、Integers 用に 1.44e9 バイトです。さらに 1.5 GB、合計で 3 GB になりました。これが問題の理論的な下限です (モジュロ キャッシング、以下を参照)。

これに基づいて、Edgeクラスを別のintフィールドで拡張することをお勧めします。これにより、メモリ フットプリントが大幅に削減されます。

ただし、これがオプションでない場合、および:

  • すべての整数が 2 桁を超えることはめったにありません。
  • あなたは決して使用しないように注意していますnew IntegerがInteger.valueOf、オートボクシングなど、
  • あなたはJava 7を使用し、

組み込みの小さい整数キャッシュを自動的に利用できます。整数がより広い範囲の値を想定しているが、それでも多くの重複がある場合は、カスタム キャッシュを強くお勧めします。

于 2012-10-31T09:24:57.093 に答える
3

さらに、jvms メモリ設定を変更することHashMapで、初期容量とロード バランスを使用してメモリ管理を微調整できます。

Javadoc の抜粋:

HashMap のインスタンスには、そのパフォーマンスに影響を与える 2 つのパラメーターがあります。初期容量と負荷係数です。容量はハッシュ テーブル内のバケットの数であり、初期容量は単にハッシュ テーブルが作成された時点の容量です。負荷率は、容量が自動的に増加する前に、ハッシュ テーブルがどれだけいっぱいになることができるかの尺度です。ハッシュ テーブルのエントリ数が負荷係数と現在の容量の積を超えると、ハッシュ テーブルが再ハッシュされ (つまり、内部データ構造が再構築され)、ハッシュ テーブルのバケット数が約 2 倍になります。

于 2012-10-31T09:20:48.983 に答える
3

作成する代わりにHashMap

costs = new HashMap<Edge,Integer>();

オブジェクト内にコストを格納できEdgeます。

class Edge
{
    Vertex a;
    Vertex b;
    int cost;
}

このようにして、システムのメモリを節約できます。

于 2012-10-31T09:21:23.257 に答える
2

元の問題に戻ります。エッジがあり、それにはコストがあります。グラフがまばらなので、疎行列を使用しないのはなぜですか? オブジェクトから整数へのマッピングは、本当に必要であり、望んでいるものではないかもしれません。apache.commons.math を見ることができます。疎行列があると思います。また、適切なスパース形式 (列ベースのランレングス エンコーディング / 行ベースの rle など) を選択するために、アルゴリズムでコストにアクセスする方法について考える必要があります。または、気にせず、いずれかを使用しますが、アルゴリズムの最初に変換する必要があります。

于 2012-10-31T09:22:59.737 に答える
1

これには大量の RAMが必要であることに気付きましたか? heap size を増やしてみてください。問題ありません...

そして、元の質問に答えるには:はい、それがMapの目的です...

于 2012-10-31T09:17:00.157 に答える
1

プロジェクトごとに、プロジェクトが必要とするヒープ領域を指定する必要があります

この手順に従うことができると思います：

Right mouse click - Run As - Run Configuration - Arguments - Vm Arguments, then add this -Xmx2048m
于 2012-10-31T09:18:59.300 に答える
1

おそらく、あなたが探しているのはTObjectIntHashMap です。HashMap<Edge, Integer>これは、 をプリミティブとして保存することを除いて、intメモリを節約できる可能性があることを除いて 似ています。このコレクションは、コレクションが大きい場合にもわずかに高速になる可能性があります (キャッシュにうまく収まるため)。

TObjectIntHashMap<Edge> costs = new TObjectIntHashMap<Edge>();

costs.put(e, cost); // cost is stored as a primitive not its wrapper object.
于 2012-10-31T09:46:10.433 に答える