java - objetos - mutable e inmutable

¿Cómo crear una jerarquía de árboles completamente inmutable? Pollo y huevo de construcción

Question

Me gusta hacer que las clases de datos sean inmutables para facilitar la programación concurrente. Pero hacer una jerarquía completamente inmutable parece problemático.

Considera esta simple clase de árbol:

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;
    }
}

Ahora, si quiero crear una jerarquía de estos, cuando lo construyo, o el padre debe existir antes del nodo actual, o los hijos deben existir primero.

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

o

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

Sin forzar que esto sea un árbol enlazado individualmente, ¿hay alguna forma inteligente de construir dicho árbol y aún tener todos los nodos completamente inmutables?

Answer 1

Sin forzar que esto sea un árbol enlazado individualmente, ¿hay alguna forma inteligente de construir dicho árbol y aún tener todos los nodos completamente inmutables?

Mantenga sus interfaces e implementaciones desconectadas, y no limite sus nodos del árbol a ser la misma clase que el árbol mismo.

Una solución a este problema es almacenar la jerarquía de nodos en alguna otra representación inmutable, y cuando un llamante llama a getChildren() o getParent() , construye los nodos secundarios a partir de esa representación inmutable. Si desea que node.getChildren().get(i).getParent() == node sea ​​true (en lugar de .equals(node) , es decir, identidad en lugar de igualdad), entonces tendrá que almacenar en caché los objetos node para que pueda volver a entregarlos en consecuencia.

Answer 2

Construir estructuras de datos eficientes e inmutables puede ser un desafío. Afortunadamente, hay personas que han descubierto cómo implementar muchos de estos ya. Eche un vistazo here para ver una gran variedad de estructuras de datos inmutables.

Esta es un área en la que todavía estoy tratando de ponerme al día, así que no puedo recomendar el subconjunto exacto de estas estructuras que debería estar viendo, pero sí una estructura de datos para trabajar con árboles que pueden Ser muy útil es Zipper.

Answer 3

Dos pensamientos

1. Utilice algún tipo de fábrica de árboles. Podría describir el árbol utilizando estructuras mutables, luego tener una fábrica que ensamblaría un árbol inmutable. Internamente, la fábrica tendría acceso a los campos de los diferentes nodos y, por lo tanto, podría volver a cablear los punteros internos según sea necesario, pero el árbol producido sería inmutable.

2. Construye una envoltura de árbol inmutable alrededor de un árbol mutable. Es decir, hacer que la construcción del árbol use nodos mutables, pero luego construir una clase de envoltura que luego proporcione una vista inmutable del árbol. Esto es similar a (1), pero no tiene una fábrica explícita.

¡Espero que esto ayude!

Answer 4

El enfoque apropiado para construir un árbol inmutable sería hacer que el constructor de cada nodo invoque a los constructores de los nodos secundarios consigo mismo como un parámetro, con la condición de que el constructor del nodo secundario no debe causar que una referencia arraigada a sí mismo se almacene en cualquier lugar, ni utilice el parámetro pasado para ningún propósito, excepto para inicializar un campo que el constructor usaría sin ningún propósito, excepto para aceptar dicha inicialización. Además, el constructor del nodo principal debe evitar el uso de cualquier miembro del nodo secundario que no haga referencia al campo "principal".

Aunque una técnica de este tipo parece violar la regla de que los constructores de objetos inmutables no deben los objetos de flagelación como parámetros de otras rutinas, la regla "real" es que el constructor de un objeto inmutable no debe permitir una referencia al objeto de flagelación para ser utilizado de tal manera que tenga acceso directo o indirecto a cualquier campo que aún no haya alcanzado su valor final. En general, si un objeto nuevo expone una referencia a sí mismo al mundo exterior, no tendrá control sobre lo que el código externo puede hacer con él. Sin embargo, en el caso particular de llamar a un constructor de nodo secundario, suponiendo que el código para el nodo secundario cumpla con los requisitos anteriores, no habrá una referencia arraigada al nodo principal, excepto a través del propio nodo principal . En consecuencia, no habrá peligro de que cualquier código que haga algo inesperado con el nodo de vuelo enarbolado obtenga una referencia a él.

Answer 5

Eric Lippert recientemente blogueó sobre este problema. Vea su publicación en el blog Persistence, Facades y Roslyn''s Red-Green Trees . Aquí hay un extracto:

Realmente hacemos lo imposible manteniendo dos árboles de parse. El árbol "verde" es inmutable, persistente, no tiene referencias principales, se construye "de abajo hacia arriba" y cada nodo hace un seguimiento de su ancho pero no de su posición absoluta . Cuando ocurre una edición, reconstruimos solo las partes del árbol verde que se vieron afectadas por la edición, que generalmente es O (log n) del total de nodos de análisis en el árbol.

El árbol "rojo" es una fachada inmutable que se construye alrededor del árbol verde; se construye "de arriba abajo" a pedido y se desecha en cada edición. Calcula las referencias principales al fabricarlas a pedido a medida que desciende a través del árbol desde la parte superior . Fabrica posiciones absolutas al calcularlas desde los anchos, nuevamente, a medida que desciendes.

Answer 6

Usted ha declarado correctamente su problema como uno de pollo y huevo. Otra forma de reafirmar el problema que podría arrojar una solución es que desea hacer crecer un árbol (raíz, tronco, hojas y todo, todo al mismo tiempo).

Una vez que acepta que la computadora solo puede procesar las cosas paso a paso, surge una serie de posibles soluciones:

1. Eche un vistazo a cómo Clojure crea estructuras de datos inmutables. En el caso de Clojure, cada operación en un árbol (como agregar un nodo) devuelve un nuevo árbol.

2. Hacer la creación de árboles atómica. Puede crear un formato especial y luego deserializar el árbol. Dado que todos los métodos de serialización son internos, no tiene que exponer ningún método mutable.

3. Justo antes de que la fábrica devuelva un árbol construido, ciérrelo primero con una bandera. Este es un análogo de la operación atómica.

4. Usa métodos de nivel de paquete para construir el árbol. De esta manera, los métodos externos no podían acceder a los métodos de mutación en los nodos.

5. Crea nodos sobre la marcha cuando se accede a ellos. Esto significa que su representación interna de árbol nunca se puede cambiar, ya que cambiar los nodos no tiene efecto en su estructura de árbol.

Answer 7

Ya que quieres que sean inmutables, tendrías que hacerlo en la construcción. Haga un constructor que tome padres e hijos, en lugar de dos constructores separados.