data structures - persistentes - estructura de datos persistente vs inmutable

persistencia wikipedia

Question

¿Hay alguna diferencia en una estructura de datos persistente e inmutable? Wikipedia se refiere a la estructura de datos inmutables cuando se habla de persistencia, pero tengo la sensación de que podría haber una sutil diferencia entre los dos.

Answer 1

Sí, hay una diferencia. Una estructura de datos inmutables no se puede modificar de ninguna manera después de su creación. La única forma de modificarlo eficazmente sería hacer una copia mutable o algo similar (por ejemplo, modificando ligeramente los parámetros que pasa al constructor del nuevo). Una estructura de datos persistente, por otro lado, es mutable en el sentido de que la API expuesta parece permitir cambios en la estructura de datos. En verdad, sin embargo, cualquier cambio retendrá un puntero a la estructura de datos existente (y por lo tanto a cada estructura anterior); solo parecen mutar la estructura de datos porque la API expuesta devuelve un nuevo puntero que puede incluir punteros a un subconjunto de la estructura de datos previa (en árboles, por ejemplo, apuntarmos al nodo cuyo subárbol no ha cambiado como resultado de la operacion).

Answer 2

La inmutabilidad es una técnica de implementación. Entre otras cosas, proporciona persistencia , que es una interfaz. La API de persistencia es algo así como:

• version update(operation o, version v) realiza la operación o en la versión v , devolviendo una nueva versión. Si la estructura de datos es inmutable, la nueva versión es una nueva estructura (que puede compartir partes inmutables de la estructura anterior). Si la estructura de datos no es inmutable, la versión devuelta puede ser simplemente un número de versión. La versión v sigue siendo una versión válida, y no debe cambiar de ninguna manera observable debido a esta actualización; la actualización solo es visible en la versión devuelta, no en v .
• data observe(query q, version v) observa una estructura de datos en la versión v sin cambiarla o crear una nueva versión.

Para obtener más información sobre estas diferencias, consulte:

• El capítulo "Estructuras de datos persistentes" de Haim Kaplan en el Manual sobre estructuras de datos y aplicaciones
• "Haciendo que las estructuras de datos sean persistentes" por Driscoll et al.
• La primera conferencia de la encarnación de Spring 2012 de 6.851 de MIT: Estructuras de datos avanzadas