Pourquoi boucle Java toString () infiniment sur les cycles indirects?

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

Question

Ceci est plus un Gotcha je voulais partager qu'une question: lors de l'impression avec toString(), Java détecte les cycles directs dans une collection (où la collection se réfère à lui-même), mais pas des cycles indirects (où une collection fait référence à une autre collection qui se réfère à la première -. ou à plusieurs étapes) 

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

Ce fut un vrai Gotcha pour moi, parce qu'il est survenu dans le code de débogage pour imprimer la collection (j'ai été surpris quand il a attrapé un cycle direct, donc je suppose à tort qu'ils avaient mis en œuvre le contrôle en général). Il y a une question: pourquoi

L'explication que je peux penser est qu'il est très peu coûteux de vérifier une collection qui fait référence à lui-même, il vous suffit de stocker la collection (que vous avez déjà), mais pour des cycles plus longs, vous devez stocker tous les collections que vous rencontrez, à partir de la racine. De plus, vous pourriez ne pas être en mesure de dire avec certitude ce que la root est, et vous auriez donc avoir à stocker toutes les collections dans le système - que vous faites de toute façon - mais vous auriez aussi faire une recherche de hachage sur chaque élément de collection. Il est très coûteux pour le cas relativement rare de cycles (dans la plupart des programmes). (Je pense), la seule raison pour laquelle il vérifie les cycles directs est parce que si pas cher (une comparaison de référence).

OK ... J'ai un peu répondu à ma propre question - mais ai-je manqué quelque chose d'important? Quelqu'un veut-il ajouter quelque chose?

Précision: Je me rends compte maintenant le problème que j'ai vu est spécifique à impression une collection (à savoir la méthode de toString()). Il n'y a pas de problème avec les cycles en soi (je les utilise moi-même et le besoin de les avoir); le problème est que Java ne peut pas les imprimer. Modifier Points Andrzej Doyle sur ce ne sont pas seulement des collections, mais tout objet dont toString est appelé.

Étant donné qu'il est contraint à cette méthode, voici un algorithme pour vérifier il:

  • la racine est l'objet que la première toString() est invoquée sur (pour déterminer cela, vous devez maintenir l'état si un toString est actuellement en cours ou non, ce qui est si peu pratique).
    • comme on traverse chaque objet, de l'ajouter à un IdentityHashMap, et aussi d'un identifiant unique (par exemple un index incrémenté).
    • mais si cet objet est déjà dans la carte, écrire son identifiant à la place.

Cette approche rend également correctement multirefs (un noeud qui est appelé plus d'une fois).

Le coût de la mémoire est la IdentityHashMap (une référence et l'index par objet); le coût de la complexité est une consultation de table de hachage pour chaque noeud du graphe orienté (à savoir, chaque objet qui est imprimé).

Était-ce utile?

La solution

Je pense que fondamentalement c'est parce que si la langue essaie de vous empêcher de vous tirer une balle dans le pied, il ne devrait pas vraiment le faire d'une manière qui est cher. Ainsi, alors qu'il est presque libre de comparer les pointeurs d'objet (par exemple le fait obj == this) au-delà de tout ce qui implique d'invoquer des méthodes sur l'objet que vous en passant.

Et à ce stade, le code de la bibliothèque ne sait rien sur les objets que vous êtes en passant. D'une part, la mise en œuvre des génériques ne sait pas si elles sont des cas de Collection (ou Iterable) eux-mêmes, et alors qu'il pourrait trouver cela via instanceof, qui est de dire que ce soit un objet « collection comme » qui ne sont pas en fait une collection, mais contient encore une référence circulaire différée? En second lieu, même si elle est une collection on ne sait pas ce qu'elle est mise en œuvre effective et donc le comportement est comme. En théorie, on pourrait avoir une collection contenant tous les Longs qui va être utilisé paresseusement; mais étant donné que la bibliothèque ne sait pas ce qu'il serait horriblement cher à itérer sur chaque entrée. Ou, en fait, on pourrait même concevoir une collection avec un itérateur qui n'a jamais mis fin (bien que cela serait difficile à utiliser dans la pratique, car tant de constructions / classes de bibliothèque supposent que hasNext finira par revenir false).

Il se résume à un coût inconnu, peut-être infini afin de vous empêcher de faire quelque chose qui pourrait ne pas vraiment être un problème de toute façon.

Autres conseils

Je voudrais simplement souligner que cette déclaration:

  

lors de l'impression avec toString (), Java détecte cycles directs dans une collection

est trompeur.

Java (la machine virtuelle Java, le langage lui-même, etc.) ne détecte pas l'auto-référence. Plutôt ceci est une propriété de la méthode de toString() / override de java.util.AbstractCollection.

Si vous deviez créer votre propre implémentation de Collection, la langue / plate-forme ne serait pas automatiquement en toute sécurité vous d'une auto-référence comme celui-ci - à moins que vous étendez AbstractCollection, vous devez vous assurer que vous couvrez vous-même logique

Je pourrais être ici couper les cheveux, mais je pense que cela est une distinction importante à faire. Tout simplement parce que l'une des classes de base dans le JDK fait quelque chose ne signifie pas que « Java » comme cadre général le fait.

Voici le code source pertinente dans AbstractCollection.toString(), avec la ligne clé a commenté: 

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

Le problème avec l'algorithme que vous proposez est que vous devez passer le IdentityHashMap à toutes les collections concernées. Ceci est impossible en utilisant les API de collecte publiées. L'interface de collecte ne définit pas une méthode de toString(IdentityHashMap).

J'imagine que quiconque Sun a mis l'auto-vérification de référence dans la méthode de pensée AbstractCollection.toString() de tout cela, et (en collaboration avec ses collègues) a décidé qu'une « solution totale » est sur le dessus. Je pense que la conception / implémentation actuelle est correcte.

Il est pas une exigence que les implémentations Object.toString être l'épreuve des bombes.

Vous avez raison, vous avez déjà répondu à votre question. Vérification des cycles plus longs (en particulier ceux qui sont vraiment longues comme durée de la période 1000) seraient trop frais généraux et ne sont pas nécessaires dans la plupart des cas. Si quelqu'un le veut, il doit vérifier lui-même.

Le cas de cycle direct, cependant, est facile à vérifier et il est plus souvent, il est donc fait en Java.

Vous ne pouvez pas détecter vraiment cycles indirects; il est un exemple typique du problème de l'arrêt.

Licencié sous: CC-BY-SA avec attribution
Non affilié à StackOverflow
scroll top