2

Graph(GraphImp) オブジェクトと Node(NodeImp) オブジェクトを持つ割り当てのグラフ実装を作成しようとしています。

Node オブジェクトには、Graph、x & y 座標、および名前への参照が含まれています。

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

}
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) スキャンではなく、バイナリ検索を使用して挿入ポイントを見つけることができます。現在の実装は n 個のアイテムを挿入するために O(n^2) ですが、O(n log n) になる可能性があります。

于 2012-04-10T05:57:33.187 に答える
1

OOMプログラム全体がなければ、正確な原因を診断するのは困難ですが、ここに 1 つの観察結果があります。

getNodes()

かなり非効率です。あなたtoArrayはLinkedListそれを横断して特定のインスタンスを探すだけです。を使用しないのはなぜですか。contains()ちゃんと？その場合、すべての要素をコピーする必要はありません。または、以前に行っていたことを実行しますがList、配列コピーの代わりに実行します。

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

最後に追加する「古い」アプローチも OOM にヒットする可能性が高いと思いますが、ハイゼンバグの理由により、それ自体は現れていません。プロファイラーで実行しましたか?

于 2012-04-10T05:51:55.913 に答える