LinkedList：java.lang.OutOfMemoryError：Javaヒープスペース

Question

Graph（GraphImp）オブジェクトとNode（NodeImp）オブジェクトを持つ代入のグラフ実装を作成しようとしています。

ノードオブジェクトには、グラフ、x & y座標および名前への参照が含まれています。

グラフオブジェクトには、ノードのリンクリストが含まれています。

ノードのリストの中央にノードを追加しようとすると問題が発生します（最後に追加すると問題ありません）。プログラムのヒープスペースが不足しています。 LinkedListへの挿入の複雑さはO（1）でなければならないし、Java（私が信じる）はオブジェクト自体ではなくポインタを使用するので、なぜこれが起こっているのか分かりません。私もarraylistを試しました

この例では、ヒープを大きくすることはオプションではなく、（私が理解する限り）問題の原因ではないはずです。

ありがとうございます。ここで

は誤りである：ここでは

Exception in thread "main" java.lang.OutOfMemoryError: Java heap space 
    at java.util.LinkedList.addBefore(LinkedList.java:795) 
    at java.util.LinkedList.add(LinkedList.java:361) 
    at pt.graph.GraphImp.addNode(GraphImp.java:79) 
    at pt.graph.NodeImp.<init>(NodeImp.java:25) 
    at pt.graph.Graphs.newNode(Solution.java:68) 

はコードです：

class Graphs 
{ 

    static Node newNode(Graph g, double xpos, double ypos, String name) throws InvalidGraphException,InvalidLabelException 
    { 
     if(g==null || !(g instanceof GraphImp)){ //Checking validity of inputs 
      throw new InvalidGraphException(); 
     } 
     if(name==null){ 
      throw new InvalidLabelException(); 
     } 

     NodeImp[] existNodes = ((GraphImp)g).getNodes(); //Get all Nodes already present in the Graph 
     for(int i=0;i<existNodes.length;i++){ 
      if(existNodes[i].getXPos() == xpos && existNodes[i].getYPos() == ypos){ //If node already present at this position, throw InvalidLabelException() 
       throw new InvalidLabelException(); 
      } 
     } 

     Node n = new NodeImp((GraphImp)g, xpos, ypos, name); //If all inputs are valid, create new node 

     return n; 
    } 

} 

class NodeImp extends Node //Node Class 
{ 

    private Object flags = null; 
    private GraphImp g = null; 
    private double xpos = 0.0; 
    private double ypos = 0.0; 
    private String name = ""; 

    NodeImp(GraphImp g, double xpos, double ypos, String name){ 
     this.g = g; 
     this.xpos = xpos; 
     this.ypos = ypos; 
     this.name = name; 
     g.addNode(this); // Add Node to the Graph 
    } 
} 

class GraphImp extends Graph 
{ 
    private LinkedList<NodeImp> nodes = new LinkedList<NodeImp>(); //LinkedList of all Nodes in the Graph 

    GraphImp(){ 

    } 

    NodeImp[] getNodes(){ //Returns an array of all Nodes 
     NodeImp[] nArr = new NodeImp[nodes.size()]; 
     return nodes.toArray(nArr); 
    } 

    int countNodes(){ //Returns number of Nodes 
     return nodes.size(); 
    } 

    void addNode(NodeImp n){ //Add a Node to the LinkedList in order 
     boolean added = false; 
     for(int i = 0;i<nodes.size();i++){ 
      if(n.compareTo(nodes.get(i))<=0){ 
       nodes.add(i,n);   //fails here 
      } 
     } 
     if(!added){ 
      nodes.add(n); 
     } 
     return; 
    } 

} 

Answer 1

問題は、リストの途中に新しいノードを挿入した後にループを終了しないことです。あなたのコードは同じノードを無限に挿入しようとします。つまりOOMです。あなたの挿入はかなり非効率的である、余談として

for(int i = 0;i<nodes.size();i++){ 
    if(n.compareTo(nodes.get(i))<=0){ 
     nodes.add(i,n); 
     added = true; 
     break; 
    } 
} 

：

はこれを試してみてください。リストがすでにソートされていることを知っているので、リストのO（n）スキャンではなく、バイナリ検索を使用して挿入ポイントを見つけることができます。現在の実装は、n個のアイテムを挿入するためにO（n^2）ですが、O（n log n）になる可能性があります。

Answer 2

それは全体のプログラムなしであなたのOOMの正確な原因を診断するのは難しいが、ここでは1つの観測だ。

getNodes()

is pretty効率。 toArrayLinkedListをスキャンして、特定のインスタンスを探します。なぜ使うべきではないの？ 正しく？要素のすべてをコピーする必要はありません。それとも、あなたが前にやっていた何をすべきかが、Listでそれを行う代わりに、配列のコピーで：

for(NodeImp n : existingNodes){ 
    if(n.getXPos() == xpos && n.getYPos() == ypos){ 
     throw new InvalidLabelException(); 
    } 
} 

私の推測では、最後に追加の「古い」のアプローチは、同様にOOMをヒットしそうだったということですが、一部のheisenbugの理由のために、それ自体を明らかにしていない。プロファイラで実行しましたか？