LinkedList：java.lang.OutOfMemoryError：Java堆空間

我想要爲Graph（GraphImp）對象和Node（NodeImp）對象進行賦值的圖形實現。LinkedList：java.lang.OutOfMemoryError：Java堆空間

節點對象包含對它們的圖形的引用，x座標和名稱。

Graph對象包含其節點的鏈接列表。

當我嘗試添加一個節點到節點列表的中間（追加到最後工作正常）時，會出現問題。程序耗盡堆空間。我不知道爲什麼會出現這種情況，因爲插入到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; 
    } 

}

來源

2012-04-10 Ian

在Java中沒有明確的指針概念。一切都是對象。 – noMAD 2012-04-10 05:42:21

其中是Node類的代碼？ – 2012-04-10 05:57:01

@noMAD：是，否。變量都是*對象的引用，而不是對象本身。引用的行爲與指針類似（但不完全相同）。 – 2012-04-10 05:58:47

問題在於，在列表中間插入新節點後，您不會退出循環。你的代碼會嘗試無限次地插入相同的節點，因此是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）。

來源

2012-04-10 05:57:33

卡梅隆 - 你的觀點非常好。你能否提一下爲什麼你認爲他會增加無數次？不會在大多數尺寸時間添加嗎？ – 2012-04-10 06:02:18

嗯，我覺得自己像個白癡。謝謝 – Ian 2012-04-10 06:03:26

這是因爲你在'i'位置添加了一個節點，將當前節點（我們稱之爲'x'）移動到'i + 1'位置。然後循環繼續，並檢查新節點是否爲'i + 1'，它是'x'again。 'x'現在移動到'i + 2'，並且這個列表現在有兩個新節點的副本，分別是'i'和'i + 1'。這永遠重複。 – 2012-04-10 06:04:46

很難診斷您OOM的確切原因，沒有完整的程序，但這裏有一個觀察：

getNodes()

很漂亮fficient。你只需要遍歷它並尋找一個特定的實例。爲什麼不使用。正確嗎？不需要複製所有的元素。或者只是做你做之前，但這樣做的List而不是數組複製：

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

我的猜測是，增加了結束的「老」的做法很可能會打一個OOM很好，但對於一些heisenbug理由它沒有表現出來。你有沒有運行探查器？

來源

2012-04-10 05:51:55

感謝您的效率建議埃米爾 - 永遠感激。 – Ian 2012-04-10 06:10:36

LinkedList：java.lang.OutOfMemoryError：Java堆空間

回答

相關問題