LinkedList : java.lang.OutOfMemoryError : Java 힙 공간

Question

그래프 (GraphImp) 개체와 노드 (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) 스캔 대신 삽입 지점을 찾을 수 있습니다. 현재 구현은 O (n^2)이고 n 개의 항목을 삽입하지만 O (n log n) 일 수 있습니다.

Answer 2

그것은 전체 프로그램없이 OOM의 정확한 원인을 진단하기 어렵지만, 여기에서 관측이다 :

여기

오류입니다

getNodes()

is pretty 효과. toArrayLinkedList을 단순히 통과시키고 특정 인스턴스를 찾습니다. 왜 그냥 사용하지 마십시오. 제대로? 그러면 모든 요소를 ​​복사 할 필요가 없습니다. 또는 당신이 전에하던 일을하지만 대신 배열 복사본의 List에 수행

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

내 추측 끝에 추가하는 '오래된'접근뿐만 아니라 OOM을 칠 가능성이라고하지만, 어떤 heisenbug 이유를 위해 그것은 그 자체를 명백하게하지 않고 있었다. 프로파일 러로 실행 해 보셨습니까?