Почему Java toString () зацикливается на косвенных циклах?

Question

Это больше вопрос, который я хотел бы поделиться, чем вопрос: при печати с 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!
  }
}

Это было для меня настоящим уловкой, потому что это происходило при отладке кода для распечатки Коллекции (я был удивлен, когда он перехватил прямой цикл, поэтому я ошибочно предположил, что они реализовали проверку в целом). Возникает вопрос: почему?

Объяснение, которое я могу придумать, состоит в том, что проверять коллекцию, которая ссылается на себя, очень недорого, поскольку вам нужно только хранить коллекцию (которая у вас уже есть), но для более длительных циклов вам нужно хранить все коллекции, с которыми вы сталкиваетесь, начиная с корня. Кроме того, вы не сможете точно сказать, что такое корень , и поэтому вам придется хранить каждую коллекцию в системе - что вы делаете в любом случае - но вам также придется сделать поиск хеша на каждом элементе коллекции. Это очень дорого для относительно редкого случая циклов (в большинстве программ). (Я думаю) единственная причина, по которой он проверяет прямые циклы, в том, что он такой дешевый (одно эталонное сравнение).

ОК ... Я вроде ответил на свой вопрос - но я что-то упустил? Кто-нибудь хочет что-нибудь добавить?

---

Разъяснение: теперь я понимаю, что проблема, с которой я столкнулся, относится только к печати a Collection (то есть к методу toString()). Там нет проблем с циклами per se (я использую их сам и мне нужно иметь их); проблема в том, что Java не может их печатать. Редактировать Анджей Дойл отмечает, что это не просто коллекции, но любой объект, чей toString называется.

Учитывая, что он ограничен этим методом, вот алгоритм для его проверки:

• корень - это объект, для которого вызывается первый toString() (чтобы определить это, вам нужно сохранить состояние о том, выполняется ли toString в данный момент или нет; так что это неудобно).
  • при прохождении каждого объекта вы добавляете его в IdentityHashMap вместе с уникальным идентификатором (например, увеличенный индекс).
  • но если этот объект уже находится на карте, вместо этого запишите его идентификатор.

Этот подход также правильно отображает multirefs (узел, на который ссылаются более одного раза).

Стоимость памяти - IdentityHashMap (одна ссылка и индекс на объект); стоимость сложности - это поиск хеша для каждого узла в ориентированном графе (то есть для каждого печатаемого объекта).

Answer 1

Я думаю, что в основном это потому, что хотя язык пытается помешать вам выстрелить себе в ногу, на самом деле это не должно делать это дорогостоящим способом. Таким образом, хотя сравнивать указатели объектов (например, выполняет obj == this) практически все, что не связано с вызовом методов для объекта, который вы передаете.

И на этом этапе библиотечный код ничего не знает об объектах, которые вы передаете. Например, реализация обобщений не знает, являются ли они экземплярами Collection (или Iterable) сами по себе. и хотя он может это выяснить через instanceof, кто скажет, является ли это «подобным коллекции» объектом, который на самом деле не является коллекцией, но все же содержит отложенную циклическую ссылку? Во-вторых, даже если это коллекция, невозможно сказать, какова ее фактическая реализация и, таким образом, поведение. Теоретически можно иметь коллекцию, содержащую все длинные, которые будут использоваться лениво; но поскольку библиотека не знает этого, было бы ужасно дорого обходить каждую запись. Или на самом деле можно даже спроектировать коллекцию с итератором, который никогда не завершается (хотя это было бы трудно использовать на практике, потому что многие классы конструкций / библиотек предполагают, что hasNext в конечном итоге вернет false).

Таким образом, это сводится к неизвестным, возможно, бесконечным затратам, чтобы помешать вам сделать что-то, что на самом деле может и не быть проблемой.

Answer 2

Я просто хотел бы отметить, что это утверждение:

при печати с помощью 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(", ");
    }
}

Answer 3

Проблема с алгоритмом, который вы предлагаете, заключается в том, что вам нужно передать IdentityHashMap всем участвующим коллекциям. Это невозможно при использовании опубликованных API-интерфейсов коллекции. Интерфейс Collection не определяет метод toString(IdentityHashMap).

Я полагаю, что тот, кто в Sun вставил проверку самоссылки в метод AbstractCollection.toString(), подумал обо всем этом и (совместно со своими коллегами) решил, что «полное решение» - это слишком. Я думаю, что текущий дизайн / реализация верна.

Не требуется, чтобы реализации Object.toString были защищены от бомб.

Answer 4

Вы не можете обнаружить косвенные циклы; это типичный пример проблемы остановки.

Answer 5

Вы правы, вы уже ответили на свой вопрос. Проверка на более длинные циклы (особенно очень длинные, такие как период 1000) будет слишком трудоемкой и в большинстве случаев не требуется. Если кто-то хочет этого, он должен проверить это сам.

Случай прямого цикла, однако, легко проверить и будет происходить чаще, так что это делается Java.