Какие существуют решения для циклических ссылок?

Каковы возможные решения/методы работы с циклическими ссылками при использовании подсчета ссылок?

Наиболее известным решением является использование слабых ссылок, однако во многих статьях на эту тему подразумевается, что существуют и другие методы, но продолжайте повторять пример со слабыми ссылками. Что заставляет меня задаться вопросом, что это за другие методы?

  • Я не спрашиваю, каковы альтернативы подсчету ссылок, а каковы решения для циклических ссылок при использовании подсчета ссылок.

  • Этот вопрос касается не какой-либо конкретной проблемы/реализации/языка, а общего вопроса.


person OB OB    schedule 01.07.2009    source источник
comment
Решение для циклических ссылок см. здесь. :-)   -  person Chris W. Rea    schedule 01.07.2009


Ответы (11)


На протяжении многих лет я рассматривал проблему десятком разных способов, и единственное решение, которое я нашел, которое работает каждый раз, — это перепроектировать мое решение, чтобы не использовать циклическую ссылку.

Изменить:

Можете ли вы расширить? Например, как бы вы поступили с отношением родитель-потомок, когда дочернему элементу необходимо знать о родительском объекте или получить доступ к нему?OB OB

Как я уже сказал, единственное хорошее решение — избегать таких конструкций, если только вы не используете среду выполнения, которая может безопасно с ними работать.

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

Это становится сложным и громоздким, поэтому единственное решение IMO — полностью избегать его.

person Randolpho    schedule 01.07.2009
comment
+1 то же самое здесь. Пример подхода см. в моем ответе на другой вопрос: stackoverflow.com/questions/1047877/ - person Fredrik Mörk; 01.07.2009
comment
Можете ли вы расширить? Например, как бы вы справились с отношением родитель-потомок, когда дочернему нужно знать о родителе/доступ к нему? - person OB OB; 01.07.2009
comment
@ChrisW: в исходном вопросе упоминались слабые ссылки. OB искал альтернативы. - person Randolpho; 01.07.2009
comment
что, если вы специально пометите родительскую ссылку как родительскую, чтобы знать, что это не дочерняя ссылка? - person Adrian; 24.04.2013

Вот решение, которое я видел:

Добавьте метод к каждому объекту, чтобы указать ему освободить свои ссылки на другие объекты, скажем, назовите его Teardown().

Затем вы должны знать, кто «владеет» каждым объектом, и владелец объекта должен вызвать для него Teardown(), когда он закончит с ним.

Если есть циклическая ссылка, скажем, A ‹-> B, и C владеет A, то когда вызывается Teardown() C, он вызывает Teardown A, который вызывает Teardown для B, B затем освобождает свою ссылку на A, A затем освобождает свою ссылку на B (уничтожая B), а затем C освобождает свою ссылку на A (уничтожая A).

person Alex Black    schedule 01.07.2009
comment
Я думаю, что в большинстве случаев вы хотели бы вызывать разрыв из деструктора объекта. Явный вызов teardown чем-то похож на уничтожение объекта вручную. (Откуда вы знаете, что никто другой не использует объект при его сносе?) - person OB OB; 01.07.2009
comment
Да, вы правы, вызовите Teardown в деструкторе объекта. Однако вызов Teardown не обязательно уничтожает объект, если у кого-то еще есть ссылка на него, он останется в живых. Объекты уничтожаются только тогда, когда счетчик ссылок достигает 0. - person Alex Black; 01.07.2009
comment
Позвольте мне исправить это: вызов Teardown для объекта не обязательно уничтожает его, но это означает, что объект больше не полезен, это похоже на вызов Dispose(). Поскольку объект освободил свои ссылки на объекты, от которых он зависит, его использование небезопасно. - person Alex Black; 01.07.2009
comment
@Alex Black: Что, если есть 2 объекта C и D, которым принадлежит A. Затем, когда C вызывает Teardown(), но D все еще хочет, чтобы он был живым? У вас должен быть счетчик в объекте A, который будет игнорировать все вызовы Teardown, кроме последнего. - person alpav; 01.12.2009
comment
@alpav: мы избежали этого сценария. Только один из C или D может владеть A. Скажем, C владеет A, а D нет, но D имеет ссылку на A, тогда вы должны разработать свой код таким образом, чтобы D не обращался к A после того, как C ушел, один из способов сделать это — сделать D принадлежащим C. - person Alex Black; 01.12.2009

Я предполагаю, что другой метод, используемый сборщиками мусора, - это «отметить и очистить»:

  1. Установите флаг в каждом экземпляре объекта
  2. Пройдите граф каждого доступного экземпляра, сняв этот флаг
  3. Каждый оставшийся экземпляр с установленным флагом недоступен, даже если некоторые из этих экземпляров имеют циклические ссылки друг на друга.
person ChrisW    schedule 01.07.2009
comment
Как я уже сказал, я прошу не альтернативы подсчету ссылок, а решения циклических ссылок. - person OB OB; 01.07.2009
comment
В чем проблема с циклическими ссылками, которую вы пытаетесь решить: это проблема сборки мусора или другая проблема? Если проблема заключается в сборке мусора, разве альтернатива не то же самое, что и решение? - person ChrisW; 01.07.2009
comment
@ChrisW: Да, проблема обычно в сборке мусора. Существует множество методов сборки мусора. Один из них — подсчет ссылок, другой — пометка и развертка. Mark-and-sweep — это пример альтернативы подсчету ссылок в качестве метода gc, слабые ссылки — это пример решения для циклических ссылок, но, с другой стороны, по-прежнему используется подсчет ссылок в качестве метода gc. Надеюсь, вы видите разницу. - person OB OB; 01.07.2009
comment
Если вы хотите сделать это, используя только первоклассные ссылки, вам нужен способ обнаружения цикличности. Метод Алекса Блэка должен делать это: делать вид, что уважает все, на что указывает объект, на который указывает ссылка, и если этот эксперимент приводит к разыменованию исходного объекта, то это циклическая ссылка. Я не знаю, но, возможно, это дорогой способ сделать это: дороже, чем разметить и зачистить, особенно в патологических / длинноцепочечных случаях. - person ChrisW; 01.07.2009
comment
На самом деле вы можете использовать сборщик мусора в тандеме с подсчетом ссылок. Счетчик ссылок вызывает немедленную очистку материала, если это возможно, а GC обрабатывает циклические ссылки (и если БОЛЬШИНСТВО вещей автоматически удаляется с помощью счетчика ссылок, у GC остается меньше работы!) - person Grant Peters; 21.07.2009

Я хотел бы предложить немного другой метод, который пришел мне в голову, я не знаю, есть ли у него какое-либо официальное название:

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

Аналогичным образом ссылки находятся в общих группах с объектами или принадлежат нулевой группе.

Ссылка на объект влияет на счетчик ссылок группы (объекта), только если она (ссылка) является внешней по отношению к группе.

Если два объекта образуют циклическую ссылку, их следует сделать частью одной и той же группы. Если две группы создают циклическую ссылку, их следует объединить в одну группу.

Большие группы предоставляют больше свободы ссылок, но объекты группы имеют больше возможностей оставаться в живых, пока они не нужны.

person OB OB    schedule 01.07.2009
comment
Это эквивалентно определению того, какие из ваших ссылок являются «слабыми»: если ссылка относится к объекту в той же группе, то ссылка является «слабой», в противном случае — к объекту из другой группы, поэтому эта ссылка является «сильной». - person ChrisW; 01.07.2009
comment
Да, только то, что если у вас есть внешняя ссылка на объект A, которая содержит слабую ссылку на объект B, а B не упоминается иначе, B все равно останется в живых (что является желаемым поведением). Вы не получите этого с обычными слабыми ссылками. - person OB OB; 01.07.2009
comment
Звучит похоже на наличие дискретных пулов памяти для разных частей приложения (так что вы можете просто удалить весь пул сразу, а затем просто очищать указатели в пуле), что обычно используется в играх, и добавление счетчика ссылок (который я думаю, это решит проблему очистки указателей) - person Grant Peters; 21.07.2009

Расставьте вещи по иерархии

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

Работа с деревьями

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

Эмуляция сборки мусора

Если у вас есть куча объектов, которые могут дико указывать друг на друга, и вы хотите очистить, как только некоторые объекты станут недоступными, вы можете создать для них контейнер и массив корневых ссылок, чтобы делать мусор. сбор вручную.

Используйте уникальные указатели, необработанные указатели и значения

В реальном мире я обнаружил, что фактические варианты использования общих указателей очень ограничены, и их следует избегать в пользу уникальных указателей, необработанных указателей или, что еще лучше, просто типов значений. Общие указатели обычно используются, когда у вас есть несколько ссылок, указывающих на общую переменную. Совместное использование вызывает трения и споры, и его следует избегать в первую очередь, если это возможно. Гораздо проще рассуждать об уникальных указателях и необработанных указателях и/или значениях, не являющихся владельцами. Однако иногда необходимы общие указатели. Общие указатели также используются для продления срока службы объекта. Обычно это не приводит к циклическим ссылкам.

Нижняя линия

Используйте общие указатели экономно. Отдавайте предпочтение уникальным указателям и необработанным указателям или простым значениям, не принадлежащим владельцам. Общие указатели указывают на совместное владение. Используйте их таким образом. Упорядочите свои объекты в иерархии. Дочерние объекты или объекты на одном уровне в иерархии не должны использовать общие ссылки друг на друга или на своего родителя, но вместо этого они должны использовать необработанные указатели, не являющиеся владельцами.

person Ralph Tandetzky    schedule 17.06.2013

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

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

В Python есть сборщик, который делает это, как и в PHP.

Я все еще пытаюсь понять алгоритм, потому что есть расширенные версии, которые утверждают, что могут делать это параллельно, не останавливая программу...

В любом случае это не просто, для этого требуется несколько сканирований, дополнительный набор счетчиков ссылок и уменьшение элементов (в дополнительном счетчике) в «испытании», чтобы увидеть, можно ли собирать самореферентные данные.

Некоторые документы: «Впереди счет? Получение рекомендаций по подсчету в ринге» Рифат Шахрияр, Стивен М. Блэкберн и Дэниел Фрэмптон http://users.cecs.anu.edu.au/~steveb/downloads/pdf/rc-ismm-2012.pdf " Единая теория сбора мусора» Дэвида Ф. Бэкона, Перри Ченга и В.Т. Раджан http://www.cs.virginia.edu/~cs415/reading/bacon-garbage.pdf

В подсчете ссылок есть много других тем, таких как экзотические способы сокращения или избавления от взаимосвязанных инструкций в подсчете ссылок. Я могу придумать 3 способа, 2 из которых были описаны.

person Josh S    schedule 14.09.2013

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

  1. Преобразуйте родителя в службу, тогда родитель не знает о дочерних элементах, и родитель умирает, когда больше нет дочерних элементов или основная программа удаляет родительскую ссылку.

  2. Если родитель должен иметь доступ к дочерним элементам, то у родителя должен быть метод регистрации, который принимает указатель, который не подсчитывается, например указатель объекта, и соответствующий метод отмены регистрации. Ребенок должен будет вызвать метод регистрации и отмены регистрации. Когда родителю необходимо получить доступ к дочернему элементу, он приводит указатель объекта к интерфейсу с подсчетом ссылок.

person William Egge    schedule 12.04.2011

Каковы возможные решения/методы работы с циклическими ссылками при использовании подсчета ссылок?

Три решения:

  1. Дополните наивный подсчет ссылок с помощью детектора циклов: счетчики, уменьшенные до ненулевых значений, считаются потенциальными источниками циклов, а топология кучи вокруг них ищет циклы.

  2. Дополните наивный подсчет ссылок обычным сборщиком мусора, таким как mark-sweep.

  3. Ограничьте язык таким образом, чтобы его программы могли создавать только ациклические (или однонаправленные) кучи. Erlang и Mathematica делают это.

  4. Замените ссылки поиском по словарю, а затем реализуйте собственный сборщик мусора, который может собирать циклы.

person J D    schedule 08.01.2012

я тоже ищу хорошее решение проблемы кругового подсчета ссылок.

я воровал позаимствовал API из World of Warcraft, связанный с достижениями. я неявно переводил его в интерфейсы, когда понял, что у меня циклические ссылки.

Примечание. Вы можете заменить слово достижения на приказы, если вам не нравятся достижения. Но кто не любит достижения?

Вот само достижение:

IAchievement = interface(IUnknown)
   function GetName: string;
   function GetDescription: string;
   function GetPoints: Integer;
   function GetCompleted: Boolean;

   function GetCriteriaCount: Integer;
   function GetCriteria(Index: Integer): IAchievementCriteria;
end;

А затем список критериев достижения:

IAchievementCriteria = interface(IUnknown)
   function GetDescription: string;
   function GetCompleted: Boolean;
   function GetQuantity: Integer;
   function GetRequiredQuantity: Integer;
end;    

Все достижения регистрируются в центральном IAchievementController:

IAchievementController = interface
{
   procedure RegisterAchievement(Achievement: IAchievement);
   procedure UnregisterAchievement(Achievement: IAchievement);
}

Затем контроллер можно использовать для получения списка всех достижений:

IAchievementController = interface
{
   procedure RegisterAchievement(Achievement: IAchievement);
   procedure UnregisterAchievement(Achievement: IAchievement);

   function GetAchievementCount(): Integer;
   function GetAchievement(Index: Integer): IAchievement;
}

Идея заключалась в том, что если произойдет что-то интересное, система вызовет IAchievementController и уведомит их о том, что произошло что-то интересное:

IAchievementController = interface
{
   ...
   procedure Notify(eventType: Integer; gParam: TGUID; nParam: Integer);
}

И когда происходит событие, контроллер будет перебирать каждого дочернего элемента и уведомлять их о событии с помощью их собственного метода Notify:

IAchievement = interface(IUnknown)
   function GetName: string;
   ...

   function GetCriteriaCount: Integer;
   function GetCriteria(Index: Integer): IAchievementCriteria;

   procedure Notify(eventType: Integer; gParam: TGUID; nParam: Integer);
end;

Если объект Achievement решит, что событие представляет интерес для него, он уведомит свои дочерние критерии:

IAchievementCriteria = interface(IUnknown)
   function GetDescription: string;
   ...
   procedure Notify(eventType: Integer; gParam: TGUID; nParam: Integer);
end;    

До сих пор график зависимостей всегда располагался сверху вниз:

 IAchievementController --> IAchievement --> IAchievementCriteria

Но что происходит, когда критерии достижения соблюдены? Объект Criteria должен был уведомить своего родителя о достижении:

 IAchievementController --> IAchievement --> IAchievementCriteria
                                    ^                      |
                                    |                      |
                                    +----------------------+

Это означает, что Criteria потребуется ссылка на его родителя; кто теперь ссылается друг на друга - утечка памяти.

И когда достижение, наконец, будет выполнено, ему нужно будет уведомить родительский контроллер, чтобы он мог обновлять представления:

 IAchievementController --> IAchievement --> IAchievementCriteria
      ^                      |    ^                      |
      |                      |    |                      |                                        
      +----------------------+    +----------------------+

Теперь Controller и его потомок Achievements циклически ссылаются друг на друга - больше утечек памяти.

я подумал, что, возможно, объект Criteria мог бы вместо этого уведомить объект Controller, удалив ссылку на его родителя. Но у нас все еще есть циклическая ссылка, просто она занимает больше времени:

 IAchievementController --> IAchievement --> IAchievementCriteria
      ^                      |                          |
      |                      |                          |                                        
      +<---------------------+                          |
      |                                                 |
      +-------------------------------------------------+

Решение World of Warcraft

Теперь World of Warcraft API не ориентирован на объекты. Но он решает любые циклические ссылки:

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

    Минусы. Делает тестирование и имитацию невозможными, потому что вам нужно иметь известную глобальную переменную.

  2. Достижение не знает своего списка критериев. Если вы хотите Criteria для Achievement, попросите для них Controller:

     IAchievementController = interface(IUnknown)
         function GetAchievementCriteriaCount(AchievementGUID: TGUID): Integer;
         function GetAchievementCriteria(Index: Integer): IAchievementCriteria;
     end;
    

    Минусы. Achievement больше не может принимать решение о передаче уведомлений своему Criteria, поскольку у него нет необходимых критериев. Теперь вам нужно зарегистрировать Criteria в Controller

  3. Когда Criteria завершается, он уведомляет Controller, который уведомляет Achievement:

     IAchievementController-->IAchievement      IAchievementCriteria
          ^                                              |
          |                                              |
          +----------------------------------------------+
    

    Минусы: голова болит.

я уверен, что метод Teardown гораздо более желателен, чем перестройка всей системы в ужасно запутанный API.

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

person Ian Boyd    schedule 05.05.2012

Если вам нужно хранить циклические данные для моментального снимка в строку,

Я прикрепляю циклическое логическое значение к любому объекту, который может быть циклическим.

Шаг 1. При синтаксическом анализе данных в строку JSON я помещаю любой объект object.is_cycloper, который не использовался, в массив и сохраняю индекс в строке. (Все используемые объекты заменяются существующим индексом).

Шаг 2: я просматриваю массив объектов, устанавливая любой из Children.is_cycloper в указанный индекс или помещая любые новые объекты в массив. Затем синтаксический анализ массива в строку JSON.

ПРИМЕЧАНИЕ. Помещение новых циклических объектов в конец массива вызывает рекурсию до тех пор, пока не будут удалены все циклические ссылки.

Шаг 3: В последний раз я анализирую обе строки JSON в одну строку;

Вот скрипт javascript... https://jsfiddle.net/7uondjhe/5/

function my_json(item) {

var parse_key = 'restore_reference', 
    stringify_key = 'is_cyclic';

var referenced_array = [];


var json_replacer = function(key,value) {

            if(typeof value == 'object' && value[stringify_key]) {
                var index = referenced_array.indexOf(value);

                if(index == -1) {
                    index = referenced_array.length;
                    referenced_array.push(value);
                };

                return {
                    [parse_key]: index
                }
            }
            return value;
}

var json_reviver = function(key, value) {

        if(typeof value == 'object' && value[parse_key] >= 0) {
                return referenced_array[value[parse_key]];
        }
        return value;
}
var unflatten_recursive = function(item, level) {
        if(!level) level = 1;
        for(var key in item) {
            if(!item.hasOwnProperty(key)) continue;
            var value = item[key];

            if(typeof value !== 'object') continue;

            if(level < 2 || !value.hasOwnProperty(parse_key)) {
                unflatten_recursive(value, level+1);
                continue;
            }

            var index = value[parse_key];
            item[key] = referenced_array[index];

        }
};


var flatten_recursive = function(item, level) {
        if(!level) level = 1;
        for(var key in item) {
            if(!item.hasOwnProperty(key)) continue;
            var value = item[key];

            if(typeof value !== 'object') continue;

            if(level < 2 || !value[stringify_key]) {
                flatten_recursive(value, level+1);
                continue;
            }

            var index = referenced_array.indexOf(value);

            if(index == -1) (item[key] = {})[parse_key] = referenced_array.push(value)-1; 
            else (item[key] = {})[parse_key] = index;
        }
};


return {

    clone: function(){ 
        return JSON.parse(JSON.stringify(item,json_replacer),json_reviver)
},

    parse: function() {
            var object_of_json_strings = JSON.parse(item);
            referenced_array = JSON.parse(object_of_json_strings.references);
            unflatten_recursive(referenced_array);
            return JSON.parse(object_of_json_strings.data,json_reviver);
    },

    stringify: function() {
            var data = JSON.stringify(item,json_replacer);
            flatten_recursive(referenced_array);
            return JSON.stringify({
                        data: data,
                        references: JSON.stringify(referenced_array)
                });
    }
}
}
person anonymous    schedule 04.05.2016

Я знаю несколько способов обойти это:

Первый (и предпочтительный) просто извлекает общий код в третью сборку и заставляет обе ссылки использовать его.

Второй добавляет ссылку как «Ссылка на файл» (dll) вместо «Ссылка на проект».

Надеюсь это поможет

person Nissim    schedule 01.07.2009
comment
Вопрос не в ссылках между сборками, а в ссылках между объектами (из тегов, в среде подсчета ссылок, т.е. без сбора мусора) - person AakashM; 01.07.2009