Warum funktioniert Java toString () Schleife unendlich auf indirekten Zyklen?

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

Frage

Das ist mehr ein Gotcha ich als eine Frage teilen wollte: wenn sie mit toString() Druck, Java direkte Zyklen in einer Sammlung erkennt (wo die Sammlung auf sich selbst verweist), nicht aber indirekte Zyklen (wo eine Sammlung auf eine andere Sammlung bezieht sich die sich auf den ersten -. oder mit mehr Stufen) 

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

Das war eine echte Gotcha für mich, weil es in Debugging-Code aufgetreten aus der Sammlung zu drucken (ich war überrascht, als sie einen direkten Zyklus gefangen, so dass ich fälschlicherweise angenommen, dass sie die Prüfung in der Regel umgesetzt hatten). Es ist eine Frage: Warum?

Die Erklärung, die ich denken kann, ist, dass es sehr billig ist für eine Sammlung zu überprüfen, die auf sich selbst verweist, da Sie nur die Sammlung speichern müssen (die Sie haben bereits), aber für längere Zyklen, müssen Sie alle speichern die Sammlungen auftreten, von der Wurzel beginnen. Darüber hinaus können Sie nicht in der Lage sein, sicher zu sagen, was die root ist, und so würden Sie jede Sammlung im System hinterlegen müssen - was Sie ohnehin tun - aber Sie würden auch zu tun haben, ein Hash-Lookup auf jedem Sammelelement. Es ist sehr teuer für den relativ seltenen Fall von Zyklen (in den meisten Programmierung). (Glaube ich) der einzige Grund, warum es für die direkten Zyklus überprüft ist, weil es so billig (ein Referenz Vergleich).

OK ... Ich habe ein bisschen meine eigene Frage beantwortet - aber habe ich verpasst etwas Wichtiges? Jeder möchte etwas hinzufügen?

Zur Verdeutlichung: Ich weiß jetzt, das Problem, das ich sah, ist spezifisch für Drucken eine Collection (das heißt, die toString() Methode). Es gibt kein Problem mit Zyklen per se (ich sie selbst nutzen und müssen sie haben); das Problem ist, dass Java sie nicht drucken kann. Bearbeiten Andrzej Doyle weist darauf hin, es ist nicht nur Sammlungen, aber jedes Objekt, das toString genannt wird.

Da es auf diese Methode beschränkt ist, hier ist ein Algorithmus für sie zu überprüfen:

  • die Wurzel ist das Objekt, dass die ersten toString() auf aufgerufen wird (dies, um zu bestimmen, müssen Sie Zustand auf halten, ob eine toString ist derzeit im Gang ist oder nicht, so ist dies unbequem).
    • , wie Sie jedes Objekt durchqueren, können Sie es zu einem IdentityHashMap hinzufügen, zusammen mit einer eindeutigen Kennung (z einen inkrementierten Index).
    • aber wenn das Objekt bereits in der Karte ist, schreibt seine Kennung statt.

Dieser Ansatz auch richtig macht multirefs (einen Knoten, der mehr als einmal bezeichnet wird).

Die Speicherkosten ist die IdentityHashMap (eine Referenz und Index pro Objekt); die Komplexität Kosten ein Hash-Lookup für jeden Knoten in dem gerichteten Graphen (d.h. jedes Objekt, das gedruckt wird).

War es hilfreich?

Lösung

ich denke, im Grunde ist es, weil, während die Sprache, die Sie zu stoppen versucht, sich von sich selbst in den Fuß zu schießen, sollte es nicht wirklich in einer Weise tun, die teuer ist. So, während es ist fast frei Objektzeiger (z tut obj == this) etwas darüber hinaus beinhaltet Aufruf Methoden auf dem Objekt, das Sie vorbei in.

vergleichen

Und an dieser Stelle die Bibliothek Code weiß nichts über die Objekte in Ihnen vorbei sind. Zum einen die Generika-Implementierung nicht weiß, ob sie Instanzen von Collection (oder Iterable) sind selbst, und während es könnte dies über instanceof herauszufinden, wer zu sagen ist, ob es sich um eine „Sammlung-like“ Objekt ist, das nicht eigentlich eine Sammlung ist, enthält aber immer noch eine latente zirkuläre Referenz? Zweitens, selbst wenn es sich um eine Sammlung ist es ist nicht abzusehen, was es tatsächliche Umsetzung ist und somit das Verhalten ist wie. Theoretisch könnte man eine Sammlung haben alle Longs enthält, die träge verwendet werden, wird sich; aber da die Bibliothek das nicht weiß wäre es schrecklich teuer sein, jeden Eintrag iterieren. Oder in der Tat könnte man sogar eine Sammlung Design mit einem Iterator, die nie beendet (obwohl dies schwierig sein würde, in der Praxis zu verwenden, weil so viele Konstrukte / Bibliotheksklassen gehen davon aus, dass hasNext schließlich false zurück).

So ist es im Grunde darum geht, ein unbekannt, möglicherweise unendlich Kosten, um Sie daran zu hindern, etwas zu tun, das nicht eigentlich sowieso ein Problem sein könnte.

Andere Tipps

Ich möchte nur darauf hinweisen, dass diese Aussage:

  

, wenn sie mit toString Druck () Java erkennt direkte Zyklen in einer Sammlung

ist irreführend.

Java (die JVM, die Sprache selbst, etc.) werden nicht die Selbstreferenz zu erfassen. Vielmehr ist dies eine Eigenschaft der toString() Methode / Überschreibung von java.util.AbstractCollection.

Wenn Sie waren Ihre eigene Collection Implementierung erstellen, die Sprache / Plattform würde nicht automatisch sicher Sie von einer Selbstreferenz so - es sei denn, Sie AbstractCollection verlängern, würden Sie sicher, müssen Sie diese Logik decken sich

könnte ich Haarspalterei sein hier, aber ich denke, das ist eine wichtige Unterscheidung zu machen. Nur weil einer der Grundklassen des JDK nicht bedeutet, etwas nicht, dass „Java“ als ein Gesamtschirm tut es.

Hier ist der relevante Quellcode in AbstractCollection.toString(), mit der Tastenzeile kommentiert: 

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(", ");
    }
}

Das Problem mit dem Algorithmus, den Sie vorschlagen, ist, dass Sie die IdentityHashMap an alle Sammlungen beteiligt übergeben müssen. Dies ist nicht möglich, die veröffentlichte Sammlung APIs. Die Collection-Schnittstelle keine toString(IdentityHashMap) Methode definiert werden.

Ich stelle mir vor, dass wer auch immer bei Sun die Selbstreferenzprüfung in die AbstractCollection.toString() Methode Gedanken an all das gesagt, und (in Verbindung mit seinen Kollegen) entschieden, dass eine „Gesamtlösung“ oben ist vorbei. Ich denke, dass die aktuelle Design / Implementierung korrekt ist.

Es ist nicht erforderlich, dass Object.toString Implementierungen bombensicher sein.

Sie haben Recht, Sie bereits Ihre eigene Frage beantwortet. Überprüfen auf längere Zyklen (vor allem wirklich lange diejenigen wie Periodenlänge 1000) würde zu viel Aufwand und ist nicht in den meisten Fällen erforderlich. Wenn jemand will es, er hat es selbst zu überprüfen.

Der direkte Zyklus Fall ist jedoch leicht zu überprüfen und wird häufiger auftreten, so ist es geschehen durch Java.

Sie können nicht wirklich indirekte Zyklen erfassen; es ist ein typisches Beispiel für das Halteproblem.

Lizenziert unter: CC-BY-SA mit Zuschreibung
Nicht verbunden mit StackOverflow
scroll top