Можно ли эффективно представить мутацию объекта-графа с неизменяемыми состояниями?

Я практикую использование неизменного объекта в C ++. Моя личная цель - представить общий граф объектов (в куче) с помощью последовательности неизменяемых графов.

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

Я пытался поделиться неизменными узлами. Но в этом случае у меня появилась новая проблема; Ссылки. Ссылка на другой объект должна обновляться во всем графе. Это требует посещения всех узлов каждый раз, когда я получаю новую версию графа. И это изменяет узлы со ссылками, поэтому они также должны быть получены (путем копирования). Производительность не будет лучше, чем копирование методом перебора.

Насколько я могу себе представить, реального эффективного способа представления мутации графа объектов с неизменяемыми состояниями не существует. Поэтому я прошу некоторую идею по этому поводу.

Можно ли эффективно представить мутацию графа объекта с неизменным состоянием?

То, что вы ищете, называется постоянной структурой данных. Каноническим ресурсом для постоянных структур данных является книга Чисто функциональных структур данных Криса Окасаки . Постоянные структуры данных вызвали интерес в последнее время благодаря их популяризации в Clojure и Scala.

Однако, по какой-то странной причине, постоянные графики, похоже, в основном игнорируются. У нас есть списки, десятки различных видов деревьев, массивы, очереди с приоритетами, карты, но нет графиков.

Я действительно нашел только одну статью: « Полностью стойкие графики» - какую выбрать?

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

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

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

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

Для каждого объекта на графике создайте «дескриптор объекта». Объект handle содержит список версионных неизменяемых состояний. Вместо того, чтобы хранить ссылки на объекты в любом из объектов графа, вы должны хранить ссылку на объект дескриптора. Затем каждая ссылка на объекты будет разыменовываться через дескриптор, используя дескриптор и номер версии представления графа объектов, который в настоящее время обрабатывается. Это вернет правильное неизменное состояние для объекта. В неизменяемых состояниях используются дескрипторы для ссылки на другие объекты в графе, поэтому вы всегда получаете согласованную дату для версии графа, который вы хотите обработать.

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

Существует опубликованное решение этой проблемы с очень хорошей амортизированной временной сложностью, но ее трудно найти, когда вы точно не знаете, что искать. Вы можете найти хорошее резюме в этих лекционных заметках (см. Раздел 2.2.3) или прочитать оригинальную статью « Обеспечение устойчивости структур данных» . Если ваш объектный граф имеет ограниченную связность (например, древовидные структуры), вы можете даже достичь сложность O (1) для чтения и обновления неизменяемого графа, что впечатляет.

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

• У объекта, который вы хотите изменить, еще есть место для изменений. Вы можете сохранить изменения непосредственно в объекте.

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

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

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

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