Как мне манипулировать деревом неизменных объектов? - PullRequest
Новая
       23

Как мне манипулировать деревом неизменных объектов?

12 голосов
/ 06 апреля 2010

Я создаю целое приложение из неизменяемых объектов, чтобы упростить реализацию многопоточности и отмены. Я использую библиотеку Google Collections , которая предоставляет неизменяемые версии Map, List и Set.

Моя модель приложения выглядит как дерево:

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

Граф объектов может выглядеть следующим образом: 

Scene
 |
 +-- Node
      |
      +-- Node 
           |
           +- Port
      +-- Node
           |
           +- Port
           +- Port

Если все эти объекты являются неизменяемыми и управляются объектом верхнего уровня SceneController:

  • Каков наилучший способ построения этой иерархии?
  • Как бы я заменил объект, который находится произвольно глубоко в дереве объектов?
  • Есть ли способ поддержки обратных ссылок, например, Узел, имеющий атрибут «родитель»?

А в целом:

  • Появились ли какие-либо шаблоны для работы с данными такого типа?
  • Имеется ли (академическая) литература по данному предмету?
  • Это хорошая идея?

Ответы [ 2 ]

11 голосов
/ 06 апреля 2010

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

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

Другая концепция - застежка-молния .Молния - это способ «навигации» по постоянной структуре данных для оптимизации локальных изменений.Например, если вы добавили четыре новых порта вместо одного, но добавили каждый порт по одному, вам нужно будет создать четыре новые сцены и восемь новых узлов.С застежкой-молнией вы откладываете такие создания до тех пор, пока не закончите, экономя на этих промежуточных объектах.

Лучшее объяснение, которое я когда-либо читал о молнии, это здесь .

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

Что касается академической литературы, я рекомендую структуры данных Purely Function, автор Okasaki ( диссертация PDF * 1022).*, полноценная книга ).

3 голосов
/ 06 апреля 2010

Если ваше дерево является неизменным, то, если вы хотите изменить его, вам нужно создать новое дерево.

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

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

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

...