Как создать полностью неизменяемую древовидную иерархию?Строительная курица и яйцо

Question

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

Рассмотрим этот простой класс деревьев:

public class SOTree {
    private final Set<SOTree> children = new HashSet<>();
    private SOTree parent;

    public SOTree(SOTree parent) {
        this.parent = parent;
    }

    public SOTree(Set<SOTree> children) {
        for (SOTree next : children)
            children.add(next);
    }


    public Set<SOTree> getChildren() {
        return Collections.unmodifiableSet(children);
    }

    public SOTree getParent() {
        return parent;
    }
}

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

    SOTree root = new SOTree((SOTree)null);
    Set<SOTree> children = createChildrenSomehow(root);
    //how to add children now?  or children to the children?

или

    Set<SOTree> children = createChildrenSomehow(null);
    SOTree root = new SOTree(children);
    //how to set parent on children?

Не заставляя это быть односвязное дерево, есть ли какой-нибудь умный способ построить такое дерево и при этом все узлы будут полностью неизменными?

Answer 1

Эрик Липперт недавно написал в блоге об этой проблеме.См. Его сообщение в блоге Стойкость, Фасады и красно-зеленые деревья Рослина .Вот отрывок:

На самом деле мы делаем невозможное, сохраняя два дерева разбора.«Зеленое» дерево является неизменным, постоянным, не имеет родительских ссылок, строится «снизу вверх», и каждый узел отслеживает свою ширину , но не абсолютную позицию .Когда происходит редактирование, мы перестраиваем только те части зеленого дерева, которые были затронуты редактированием, что обычно составляет около O (log n) от общего количества узлов анализа в дереве.

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

Answer 2

Две мысли:

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

2. Построить неизменную оболочку дерева вокругизменчивое дерево.То есть, пусть конструкция дерева использует изменяемые узлы, а затем создает класс-оболочку, который затем обеспечивает неизменное представление дерева.Это похоже на (1), но не имеет явной фабрики.

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

Answer 3

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

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

Answer 4

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

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

1. Посмотрите, как Clojure создает неизменные структуры данных.В случае Clojure каждая операция на дереве (например, добавление узла) возвращает новое дерево.

2. Сделать создание дерева атомарным.Вы можете создать специальный формат и затем десериализовать дерево.Поскольку все методы сериализации являются внутренними, вам не нужно предоставлять какие-либо изменяемые методы.

3. Непосредственно перед тем, как фабрика вернет построенное дерево, сначала заблокируйте его с помощью флага.Это аналог атомарной операции.

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

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

Answer 5

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

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

Answer 6

Не заставляя это быть односвязное дерево, есть ли какой-нибудь умный способ построить такое дерево и при этом все узлы будут полностью неизменными?

Держите ваши интерфейсы и реализации изолированными и не ограничивайте свои узлы дерева тем же классом, что и само дерево.

Одним из решений этой проблемы является сохранение иерархии узлов в каком-либо другом неизменяемом представлении, и когда вызывающий абонент вызывает getChildren() или getParent() что угодно, он лениво создает дочерние узлы из этого неизменяемого представления. Если вы хотите, чтобы значение node.getChildren().get(i).getParent() == node было истинным (а не .equals(node) - т. Е. Идентичность, а не равенство), то вам придется кэшировать объекты узлов, чтобы вы могли переиздавать их соответствующим образом.

Answer 7

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