Почему цикл 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! 
    } 
} 

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

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

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

---

Разъяснения: теперь я понимаю, проблема, которую я видел, специфична для печати Коллекции (т.е. метода toString()). Нет проблем с циклами per se (я использую их сам и должен их иметь); проблема в том, что Java не может их распечатать. Редактировать Andrzej Doyle указывает, что это не только коллекции, но и любой объект, вызывающий toString.

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

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

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

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

Answer 1

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

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

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

Answer 2

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

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

Answer 3

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

Answer 4

Я просто хотел бы отметить, что это заявление:

при печати с 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 5

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

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

Это не требование, чтобы реализации Object.toString были защищены от бомб.