2

我正在尝试为具有 Graph(GraphImp) 对象和 Node(NodeImp) 对象的分配创建图形实现。

节点对象包含对其 Graph、x & y 坐标和名称的引用。

Graph 对象包含其节点的链表。

当我尝试将节点添加到节点列表的中间时会出现问题（附加到末尾可以正常工作）。程序用完了堆空间。我不确定为什么会发生这种情况，因为插入 LinkedList 的复杂性应该是 O(1)，并且 Java（我相信）使用指针，而不是对象本身。我也试过一个数组列表

在这种情况下，使堆变大不是一种选择，并且（据我所知）不应该是问题的根源。

提前致谢。

这是错误：

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;
    }

}
4

2 回答 2

3

问题是在列表中间插入新节点后，您没有退出循环。您的代码将尝试无限次插入同一个节点，因此会出现 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-10T05:57:33.187 回答
1

OOM如果没有整个程序，很难诊断出你的确切原因，但这里有一个观察结果：

getNodes()

效率很低。您只需遍历它toArray并LinkedList查找特定实例。为什么不直接使用 . contains()适当地？无需复制所有元素。或者只是做你之前做的事情，但在List而不是数组副本上做：

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

我的猜测是，添加到末尾的“旧”方法也可能会遇到 OOM，但由于某些 heisenbug 原因，它并没有表现出来。您是否使用分析器运行过？

于 2012-04-10T05:51:55.913 回答