Estructuras de datos persistentes

Todas las estructuras de datos discutidas aquí hasta ahora son no persistentes (o efímeras). Una estructura de datos persistente es una estructura de datos que siempre conserva la versión anterior de sí misma cuando se modifica. Se pueden considerar como ‘inmutables’ ya que las actualizaciones no están en su lugar .

Una estructura de datos es parcialmente persistente si se puede acceder a todas las versiones, pero solo se puede modificar la versión más reciente. Totalmente persistente si se puede acceder a todas las versiones y modificarlas. Confluently persistente es cuando fusionamos dos o más versiones para obtener una nueva versión. Esto induce un DAG en el gráfico de versión.

La persistencia se puede lograr simplemente copiando, pero esto es ineficiente en el uso de CPU y RAM, ya que la mayoría de las operaciones solo harán un pequeño cambio en el DS. Por lo tanto, un mejor método es explotar la similitud entre las versiones nuevas y antiguas para compartir la estructura entre ellas.

Ejemplos:

1. Concatenación de listas enlazadas: considere el problema de concatenar dos listas enlazadas individualmente con n y m como el número de Nodes en ellas. Di n>m. Necesitamos mantener las versiones, es decir, deberíamos poder hacer una lista original.
   Una forma es hacer una copia de cada Node y hacer las conexiones. O(n + m) para atravesar listas y O(1) cada uno para agregar (n + m – 1) conexiones.
   Otra forma, y ​​una forma más eficiente en el tiempo y el espacio, implica atravesar solo una de las dos listas y menos conexiones nuevas. Dado que asumimos m<n, podemos elegir una lista con m Nodes para copiar. Esto significa O(m) para el recorrido y O(1) para cada una de las (m) conexiones. Debemos copiarlo, de lo contrario, la forma original de la lista no habría persistido.

   

2. Inserción del árbol de búsqueda binaria: Considere el problema de la inserción de un nuevo Node en un árbol de búsqueda binaria. Al ser un árbol de búsqueda binario, existe una ubicación específica donde se colocará el nuevo Node. Todos los Nodes en la ruta desde el nuevo Node hasta la raíz del BST observarán un cambio de estructura (en cascada). Por ejemplo, el Node para el que el nuevo Node es el hijo ahora tendrá un puntero nuevo. Este cambio en la estructura induce un cambio en el camino completo hasta la raíz. Considere el árbol a continuación con el valor del Node enumerado dentro de cada uno de ellos.
   

Enfoques para hacer que las estructuras de datos sean persistentes
Para los métodos que se sugieren a continuación, las actualizaciones y el tiempo de acceso y el espacio de las versiones varían según se implemente la persistencia total o parcial.

1. Copia de ruta: Haga una copia del Node que estamos a punto de actualizar. Luego proceda a la actualización. Y finalmente, vuelva a aplicar el cambio en cascada a través de la estructura de datos, algo muy similar a lo que hicimos en el ejemplo dos anterior. Esto provoca una string de actualizaciones, hasta que llega a un Node al que ningún otro apunta: la raíz.
   ¿Cómo acceder al estado en el tiempo t? Mantenga una array de raíces indexadas por marca de tiempo.
2. Nodes gordos: como sugiere el nombre, hacemos que cada Node almacene su historial de modificaciones, lo que lo convierte en «grueso».
3. Nodes con cajas: Se puede conseguir tiempo y espacio amortizado O(1) para acceso y actualizaciones. Este método fue proporcionado por Sleator, Tarjan y su equipo. Para un árbol, implica usar una caja de modificación que puede contener:
   a. una modificación al Node (la modificación podría ser de uno de los punteros, o de la clave del Node o de algún otro dato específico del Node)
   b. la hora en que se aplicó el mod
   La marca de tiempo es crucial para llegar a la versión del Node que nos interesa. Uno puede leer más sobre esto aquí. Con este algoritmo, dado cualquier tiempo t, existe como máximo una casilla de modificación en la estructura de datos con el tiempo t. Por lo tanto, una modificación en el tiempo t divide el árbol en tres partes: una
   parte contiene los datos anteriores al tiempo t, una parte contiene los datos posteriores al tiempo t y
   una parte no se vio afectada por la modificación (Fuente: MIT OCW ).
   Las estructuras de datos que no son de árbol pueden requerir más de un cuadro de modificación, pero se limitan al grado de entrada del Node para O(1) amortizado.

Enlaces útiles:

1. OCW del MIT (Erik Demaine)
2. OCW del MIT (David Karger)
3. Charla de Dann Toliver
4. Página wiki

 

Árbol de segmentos persistentes | Serie 1 (Introducción)

Este artículo es una contribución de Yash Varyani . Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.