4

これは、質問というよりも共有したかった落とし穴です。 で印刷する場合toString()、Java はコレクション内の直接サイクル (コレクションがそれ自体を参照する場合) を検出しますが、間接サイクル (コレクションが別のコレクションを参照する別のコレクションを参照する場合) は検出しません。最初のもの - またはより多くのステップで)。

import java.util.*;
public class ShonkyCycle {
  static public void main(String[] args) {
    List a = new LinkedList();
    a.add(a);                      // direct cycle
    System.out.println(a);         // works:  [(this Collection)]

    List b = new LinkedList();
    a.add(b);
    b.add(a);                      // indirect cycle
    System.out.println(a);         // shonky:  causes infinite loop!
  }
}

コレクションを出力するコードのデバッグ中に発生したため、これは私にとって本当に落とし穴でした (直接サイクルをキャッチしたときに驚いたので、一般的にチェックを実装したと誤って想定しました)。質問があります：なぜですか？

私が考えることができる説明は、それ自体を参照するコレクションをチェックするのは非常に安価であるということです.コレクションを保存するだけで済みます.出会い、根本から。さらに、ルートが何であるかを確実に伝えることができない場合があるため、すべてのコレクションをシステムに保存する必要がありますが、とにかくこれを行いますが、すべてのコレクション要素に対してハッシュルックアップを行う必要もあります。 . (ほとんどのプログラミングで) サイクルの比較的まれなケースでは、非常にコストがかかります。（私が思うに）直接サイクルをチェックする唯一の理由は、それがとても安いからです（1つの参照比較）。

わかりました...私は自分の質問にちょっと答えました-しかし、何か重要なことを見逃していませんか? 何か追加したい人はいますか？

明確化: 私が見た問題は、コレクション (つまり、メソッド)の印刷に固有のものであることがわかりました。サイクル自体toString()には問題はありません(私はサイクルを自分で使用しており、必要です)。問題は、Java がそれらを印刷できないことです。Edit Andrzej Doyle は、コレクションだけでなく、呼び出されるすべてのオブジェクトであると指摘しています。toString

このメソッドに制約されていることを考えると、これをチェックするアルゴリズムは次のとおりです。

  • ルートは、最初に呼び出されるオブジェクトですtoString()(これを決定するには、toString が現在進行中かどうかの状態を維持する必要があるため、不便です)。
    • 各オブジェクトをトラバースするときに、それを一意の識別子 (インクリメントされたインデックスなど) と共に IdentityHashMap に追加します。
    • ただし、このオブジェクトが既にマップにある場合は、代わりにその識別子を書き出します。

このアプローチは、multirefs (複数回参照されるノード) も正しくレンダリングします。

メモリ コストは IdentityHashMap (オブジェクトごとに 1 つの参照とインデックス) です。複雑さのコストは、有向グラフのすべてのノード (つまり、出力される各オブジェクト) のハッシュ ルックアップです。

4

5 に答える 5

5

基本的には、言語はあなたが自分の足を撃つのを阻止しようとしますが、実際には高価な方法でそうするべきではないからだと思います。したがって、オブジェクトポインタを比較することはほぼ自由ですが（たとえば、そうしますobj == this）、それを超えるものは、渡すオブジェクトのメソッドを呼び出す必要があります。

そして、この時点で、ライブラリコードは、渡されているオブジェクトについて何も知りません。たとえば、ジェネリックスの実装は、それらがそれ自体のインスタンスであるCollectionかどうかを知りません。Iterableinstanceof、実際にはコレクションではないが、延期された循環参照が含まれている「コレクションのような」オブジェクトであるかどうかは誰が言いますか？第二に、それがコレクションであっても、それが実際の実装であるかどうかがわからないため、動作はどのようになりますか。理論的には、怠惰に使用されるすべてのロングを含むコレクションを持つことができます。しかし、ライブラリはこれを認識していないため、すべてのエントリを反復処理するのは非常にコストがかかります。hasNextまたは、実際には、終了しないイテレータを使用してコレクションを設計することもできます（ただし、非常に多くのコンストラクト/ライブラリクラスが最終的に返されると想定しているため、これを実際に使用するのは困難ですfalse）。

したがって、基本的には、実際には問題にならない可能性のあることを実行できないようにするための、未知の、場合によっては無限のコストになります。

于 2009-06-15T11:04:05.990 に答える
3

私はこの声明を指摘したいと思います：

toString（）を使用して印刷する場合、Javaはコレクション内の直接サイクルを検出します

誤解を招くです。

Java（JVM、言語自体など）は自己参照を検出していません。むしろ、これはのtoString()メソッド/オーバーライドのプロパティですjava.util.AbstractCollection。

独自の実装を作成する場合Collection、言語/プラットフォームは、このような自己参照から自動的に保護されません。拡張AbstractCollectionしない限り、このロジックを自分でカバーする必要があります。

私はここで髪を分割しているかもしれませんが、これは重要な区別だと思います。JDKの基礎クラスの1つが何かを実行するからといって、全体的な傘としての「Java」がそれを実行することを意味するわけではありません。

の関連するソースコードはAbstractCollection.toString()次のとおりです。キーラインはコメント付きです。

public String toString() {
    Iterator<E> i = iterator();
    if (! i.hasNext())
        return "[]";

    StringBuilder sb = new StringBuilder();
    sb.append('[');
    for (;;) {
        E e = i.next();
        // self-reference check:
        sb.append(e == this ? "(this Collection)" : e); 
        if (! i.hasNext())
            return sb.append(']').toString();
        sb.append(", ");
    }
}
于 2009-06-16T04:42:46.557 に答える
1

あなたが提案するアルゴリズムの問​​題は、関連するすべてのコレクションに IdentityHashMap を渡す必要があることです。これは、公開された Collection API を使用して行うことはできません。Collection インターフェイスはメソッドを定義しませんtoString(IdentityHashMap)。

Sun の誰かがAbstractCollection.toString()メソッドに自己参照チェックを組み込み、(彼の同僚と協力して) 「完全な解決策」は行き過ぎだと判断したと思います。現在の設計・実装は正しいと思います。

Object.toString の実装が防爆であることは必須ではありません。

于 2009-09-26T23:26:49.913 に答える
0

あなたは正しいです、あなたはすでにあなた自身の質問に答えました。より長いサイクル (特に期間の長さが 1000 のような非常に長いサイクル) をチェックすると、オーバーヘッドが大きくなり、ほとんどの場合必要ありません。誰かがそれを望むなら、彼は自分でそれをチェックしなければなりません。

ただし、直接循環の場合は確認が容易であり、より頻繁に発生するため、Java によって行われます。

于 2009-06-15T10:58:44.333 に答える
0

間接的なサイクルを実際に検出することはできません。停止問題の典型例です。

于 2009-06-15T10:59:09.557 に答える