Java toString() が間接サイクルで無限ループするのはなぜですか?

StackOverflow https://stackoverflow.com/questions/995477

質問

これは質問というよりも、私が共有したい落とし穴です。で印刷するとき 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!
  }
}

これは、コレクションを出力するコードのデバッグで発生したため、私にとっては非常に厄介な問題でした (直接サイクルをキャッチしたときは驚きました。そのため、一般的にチェックが実装されていると誤って推測していました)。質問があります:なぜ？

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

わかりました...私自身の質問にはある程度答えましたが、何か重要なことを見逃していませんか?何か追加したい人はいますか?

説明:私が見た問題は特定の問題であることがわかりました 印刷 コレクション (すなわち、の toString() 方法）。周期的には問題ないよ それ自体 (私自身も使用しているので必要です);問題は、Java がそれらを印刷できないことです。 編集 Andrzej Doyle 氏は、それは単なるコレクションではなく、 toString と呼ばれます。

このメソッドに制限されていることを考慮して、それをチェックするアルゴリズムを次に示します。

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

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

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

役に立ちましたか？

解決

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

そして、この時点では、ライブラリのコードはあなたが渡しているオブジェクトについて何も知りません。彼らはCollection（またはIterable）のインスタンスをしている場合は、1つの場合は、ジェネリック医薬品の実装は自分自身を知らない、それしばらくそれは実際にはコレクションではありません「コレクションのような」オブジェクトのかどうかと言うことですが、それでも延期循環参照が含まれているinstanceof、経由でこれを見つけることができますか？それがコレクションの場合でも第二に、何それは実際の実装ですので、行動はどのようなものであるか言ってはありません。理論的には1が遅延して使用されようとしているすべてのロングスを含むコレクションを持つことができます。ライブラリはこのことを知らないので、すべてのエントリを反復処理する恐ろしく高価です。それとも、実際に1でも（これは非常に多くの構造/ライブラリクラスがhasNextが最終的falseを返すことを想定しているため、実際に使用するのは困難であろうが）終了したことがないイテレータとコレクションをデザインすることができます。

それは基本的に、実際にとにかく問題ではないかもしれない何かをやってからあなたを停止するために、未知の、おそらく無限のコストに降りてくるようにします。

他のヒント

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

  

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

誤解を招く恐れがあります。

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

あなたがあなた自身のCollection実装を作成した場合、言語/プラットフォームは、このような自己参照からあなた自動的に安全ではないだろう - あなたはAbstractCollectionを延長しない限り、あなたは、このロジックを自分でカバーを確認する必要があります

私はここ分割毛かもしれないが、私はこれを作るために重要な違いだと思います。 JDKでの基礎クラスの一つは、全体的な傘としての「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(", ");
    }
}

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

Sun の誰が自己参照チェックを AbstractCollection.toString() メソッド氏はこれらすべてを考慮し、（同僚と協力して）「完全な解決策」はやり過ぎであると判断しました。現在の設計/実装は正しいと思います。

Object.toString 実装が耐爆性であることは要件ではありません。

あなたはすでにあなた自身の質問に答え、正しいです。長いサイクル（周期長1000のような特に本当に長いもの）のためにチェックすることは、あまりにも多くのオーバーヘッドとなり、ほとんどの場合には必要ありません。誰かがそれを望んでいるならば、彼はそれを自分自身をチェックする必要があります。

直接サイクルの場合は、しかし、チェックするとより頻繁に発生します簡単ですので、それは、Javaによって行われます。

あなたは本当に間接的なサイクルを検出することはできません。それは停止問題の典型的な例です。

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top