2

PriorityQueueを使用して、グラフのトポロジカルソートを実行したいと思います。簡潔にするために、コンパレータには匿名の内部クラスを使用したいと思います。ただし、g見ているノードの程度を判断するには、グラフにアクセスする必要があります。これは可能ですか？

    /**
 * topological sort 
 * @param g must be a dag
 */
public static Queue<String> topoSort(DirectedGraph<String, DefaultEdge> g) {
    Queue<String> result = new PriorityQueue<String>(g.vertexSet().size(), 
            new Comparator<String>() {

                DirectedGraph<String, DefaultEdge> g;

                @Override
                public int compare(String arg0, String arg1) {
                    if (g.inDegreeOf(arg0) < g.inDegreeOf(arg1)) {
                        return -1;
                    }
                    if (g.inDegreeOf(arg0) > g.inDegreeOf(arg1)) {
                        return 1;
                    }
                    return 0;
                }
    });

    result.addAll(g.vertexSet());

    return result;
}

修正されたコード

/**
 * topological sort 
 * @param g must be a dag
 */
public static Queue<String> topoSort(final DirectedGraph<String, DefaultEdge> g) {
    Queue<String> result = new PriorityQueue<String>(g.vertexSet().size(), 
            new Comparator<String>() {          
                @Override
                public int compare(String arg0, String arg1) {
                    if (g.inDegreeOf(arg0) < g.inDegreeOf(arg1)) {
                        return -1;
                    }
                    if (g.inDegreeOf(arg0) > g.inDegreeOf(arg1)) {
                        return 1;
                    }
                    return 0;
                }
    });

    result.addAll(g.vertexSet());

    return result;
}
4

3 に答える 3

11

はい、最終的にします。

public static Queue<String> topoSort(final DirectedGraph<String, DefaultEdge> g) {

最後のキーワードの最後の言葉を参照してください：

匿名のローカルクラス

最終変数を含む2番目の状況は、実際には言語セマンティクスによって義務付けられています。そのような状況では、Javaコンパイラーは、変数がfinalとして宣言されていない限り、変数を使用できません。この状況は、匿名ローカルクラスとも呼ばれるクロージャで発生します。ローカルクラスは、finalとして宣言されたローカル変数とパラメーターのみを参照できます。

public void doSomething(int i, int j)
{
  final int n = i + j; // must be declared final

  Comparator comp = new Comparator()
  {
    public int compare(Object left, Object right)
    {
      return n; // return copy of a local variable
    }
  };
}

この制限の理由は、ローカルクラスの実装方法に光を当てると明らかになります。匿名ローカルクラスはローカル変数を使用できます。これは、コンパイラがクラスにプライベートインスタンスフィールドを自動的に与えて、クラスが使用する各ローカル変数のコピーを保持するためです。コンパイラーはまた、これらの自動的に作成されたプライベート・フィールドを初期化するために、各コンストラクターに隠しパラメーターを追加します。したがって、ローカルクラスは実際にはローカル変数にアクセスするのではなく、それらのプライベートコピーにアクセスするだけです。これが正しく機能する唯一の方法は、ローカル変数がfinalとして宣言されている場合です。これにより、ローカル変数が変更されないことが保証されます。この保証が適用されると、ローカルクラスは、変数の内部コピーが実際のローカル変数を正確に反映することが保証されます。

于 2009-11-17T02:29:25.097 に答える
2

ローカル変数が内部クラスで使用されている場合、コンパイラは内部クラスのインスタンス フィールドを生成し、ローカル変数の値をそこにコピーします。ここで、ローカル変数が変更された場合、instances 変数の値は古い値のままになります。そのため、ローカル変数の値をインスタンス フィールドと同じにし、変更できないようにするために、それを final にします。

于 2012-08-27T15:03:45.807 に答える
0

参考までに、Google コレクションには次のオプションもあります。

  Ordering.natural().onResultOf(
      new Function<String, Integer>() {
        public Integer apply(String arg) {
          return g.inDegreeOf(arg);
        }
      });

ご覧のとおり、その関数の他の用途が見つからない限り、これは必ずしも多くの入力を節約するとは限りませんが、手動のコンパレータ実装に非常に頻繁に忍び寄るバグから保護します。

于 2009-11-18T09:01:08.183 に答える