Números de serie a estructuras de datos persistentes / funcionales

Question

estructuras de datos persistentes dependen de la puesta en común de la estructura de la eficiencia. Para ver un ejemplo, consulte aquí .

¿Cómo puedo conservar la estructura de intercambio cuando serializar las estructuras de datos y escribir en un archivo o base de datos? Si tan sólo ingenuamente atravesar la estructuras de datos, voy a almacenar los valores correctos, pero voy a perder el intercambio de estructura. Me gustaría ser capaz de salvar estructuras de datos con componentes compartidos en un archivo, restaurarlos, y todavía tienen la mayor parte de la estructura compartida en los datos restaurados.

Answer 1

¿Quieres algún tipo de hash Consing. Este problema ha sido bien estudiado. de combinadores pickler explica en detalle cómo serializar y unserialize preservando al mismo tiempo compartir.

Answer 2

Hay dos métodos obvios que se me ocurre, y están relacionados entre sí.

1. No serializar los estructuras , serializar los nodos . Así que, es almacenar un registro en serie para cada uno de los nodos en el árbol de ejemplo que diste, y que le convertir todas las referencias de nodo a un nombre clave de la base de datos para el nodo. Esto le da compartir de forma automática, pero tiene el costo de tener que hacer múltiples búsquedas de las referencias que persiguen el fin de cargar una estructura.
2. Color nodos de la propiedad, al igual que en su ejemplo. Tener un concepto de la estructura de un nodo dado 'pertenece' a serializar y sólo los nodos en una estructura que pertenecen a esa estructura. Los enlaces a nodos en otras estructuras son reemplazados por una referencia a la estructura y el nodo en cuestión. Esto le permite cargar una estructura completa de una vez, pero puede hacer que usted tiene que cargar todas las estructuras relacionadas, si estos están altamente relacionados entre sí.

La elección entre estas opciones depende de lo que usted está tratando de optimizar para, y qué tipo de vinculación que espera ver en la práctica.