大きな地図をメモリに保存する

Question

まず、問題の文脈：私は非常に大きなグラフを保存するには約4GB必要です。約3Mのノードと34Mのエッジ。私のプログラムは、この大きなグラフを取り、そこから小さなグラフを再帰的に作成します。再帰の各レベルには、元のグラフとオリジナルから作成されたグラフという2つのグラフがあります。この再帰は、グラフが約10ノードという非常に小さなグラフに縮小されるまで続きます。

プログラムの実行全体にこれらのグラフが必要なので、メモリ効率は私のアプリケーションにとって非常に重要です。

は今ここに私は現在抱えている問題です： これは、1つの大きなから小さなグラフを作成するためのアルゴリズムである：私はこれを行うとき

public static Graph buildByTriples(Graph g, ArrayList<Integer> seeds) { 
    ArrayList<Edge> edges = new ArrayList(g.getEdgeCount()); 
    for (int i = 0; i < g.size(); i++) { 
     for (Edge e : g.adj(i)) { 
      int v = e.getEndpoint(i); 
      if (i < v) { 
       edges.add(e); 
      } 
     } 
    } 

    Table<Integer, Integer, Double> coarseEgdes = HashBasedTable.create(seeds.size(),seeds.size()); 
    //compute coarse weights 
    edges.stream().forEach((e) -> { 
     int v = e.getV(); 
     int u = e.getU(); 
     if (g.isC(u) && g.isC(v)) { 
      addToTable(coarseEgdes, u, v, e.getWeight()); 
     }else if(!g.isC(u) && g.isC(v)){ //F-C 
      for(Edge cEdge: g.cAdj(u)){//get coarse neighbors of the fine edges 
       int nb = cEdge.getEndpoint(u); 
       if(nb != v){ 
        addToTable(coarseEgdes, v, nb, cEdge.getPij() * e.getWeight()); 

       } 
      } 
     }else if(g.isC(u) && !g.isC(v)){//C-F 
      for(Edge cEdge: g.cAdj(v)){//get coarse neighbors of the fine edges 
       int nb = cEdge.getEndpoint(v); 
       if(nb != u){ 
        addToTable(coarseEgdes, u, nb, cEdge.getPij() * e.getWeight()); 
       } 
      } 
     }else{//F-F 
      for(Edge cEdgeU: g.cAdj(u)){//get coarse neighbors of the fine edges 
       int uNb = cEdgeU.getEndpoint(u); 
       for(Edge cEdgeV: g.cAdj(v)){ 
        int vNb = cEdgeV.getEndpoint(v); 
        if(uNb != vNb){ 
         addToTable(coarseEgdes, uNb, vNb, cEdgeU.getPij() * e.getWeight() * cEdgeV.getPij()); 
        } 
       } 
      } 
     } 
    }); 

    return createGraph(g, coarseEgdes); //use the edges to build new graph. Basically loops through coarseEdges and add edge and weight to the new graph. 
} 

private static void addToTable(Table<Integer, Integer,Double> tbl, int r, int c, double val){ 
    int mn = Math.min(r, c);//the smaller of the two nodeIds 
    int mx = Math.min(r, c);//the largest of the two nodeId 
    if(tbl.contains(mn, mx)){ 
     tbl.put(mn, mx, tbl.get(mn, mx) + val); 
    }else{ 
     tbl.put(mn, mx,val); 
    } 
} 

は今、私はすぐにメモリ不足に。私はYourKitでアプリケーションのプロファイリングを行い、メモリ使用量は屋根を越えています（実行前に6GBを超えています）。 coarseEdgesは本当に大きくなることがあります。大規模なデータセットで拡張されたメモリ内のMap実装が優れていますか？または、保存せずにこれを行うより良い方法がありますか？coarseEdges？

PS：一定時間内にグラフがエッジ（u、v）を取得できないことに注意してください。これは基本的にリストのリストで、これは私のアプリケーションの他の重要な部分のパフォーマンスを改善します。

Answer 1

ここでは盲目のスタブはほとんどありません。どの程度役立つかを確認するには、それらを実装する必要があります。

1）グアバテーブルではなく、ハッシュマップでコンポジットキー（int、int）を使用することを検討します。確かにエッジウェイトの方が効率的です。特定の頂点から出て行くエッジを照会する必要がある場合は、それほど明白ではありませんが、CPUとメモリーのトレードオフを比較する必要があります。

2）プレーンハッシュマップを使用する場合は、オフヒープ実装を使用することを検討できます。たとえばhttps://github.com/OpenHFT/Chronicle-Mapを見てください。

3）メモリにいて余分なスペースを絞っている場合、プリミティブマップで汚いトリックを行うことができます。たとえば、http://labs.carrotsearch.com/download/hppc/0.4.1/api/com/carrotsearch/hppc/LongDoubleMap.htmlまたはhttp://trove4j.sourceforge.net/javadocs/gnu/trove/map/hash/TLongDoubleHashMap.htmlのようなlong-> doubleマップを使用して、2xintの頂点ペアを長時間エンコードし、それがどの程度役立つかを確認します。 64ビットを使用している場合、Integerは16バイト（圧縮されたoopsを仮定）、Double 24バイト - エントリあたり32 + 24 = 56バイト、プリミティブマップの場合は8 + 8となります。