Estructura de datos persistente

En informática , una estructura de datos persistente o no efímera es aquella que conserva siempre su versión anterior al ser modificada. Estas estructuras son prácticamente inmutables , ya que sus operaciones no actualizan (visiblemente) la estructura directamente, sino que siempre generan una nueva estructura actualizada. El término fue introducido en el artículo de Driscoll, Sarnak, Sleator y Tarjan de 1986. ^{[ 1 ]}

Una estructura de datos es parcialmente persistente si se puede acceder a todas las versiones, pero solo se puede modificar la más reciente. La estructura de datos es totalmente persistente si se puede acceder a todas las versiones y modificarlas. Si además existe una operación de fusión que permite crear una nueva versión a partir de dos versiones anteriores, la estructura de datos se denomina persistente confluente . Las estructuras que no son persistentes se denominan efímeras . ^{[ 2 ]}

Este tipo de estructuras de datos son particularmente comunes en la programación lógica y funcional , ^{[ 2 ]} ya que los lenguajes en esos paradigmas desalientan (o prohíben por completo) el uso de datos mutables.

En el modelo de persistencia parcial, un programador puede consultar cualquier versión anterior de una estructura de datos, pero solo puede actualizar la última versión. Esto implica un orden lineal entre cada versión de la estructura de datos. ^{[ 3 ]} En el modelo de persistencia total, se permiten tanto actualizaciones como consultas en cualquier versión de la estructura de datos. En algunos casos, se puede permitir que las características de rendimiento de la consulta o actualización de versiones anteriores de una estructura de datos se degraden, como sucede con la estructura de datos de cuerda . ^{[ 4 ]} Además, una estructura de datos puede denominarse persistente confluente si, además de ser totalmente persistente, dos versiones de la misma estructura de datos se pueden combinar para formar una nueva versión que sigue siendo totalmente persistente. ^{[ 5 ]}

Un método para crear una estructura de datos persistente consiste en utilizar una estructura de datos efímera proporcionada por la plataforma, como un array , para almacenar los datos y copiar la totalidad de dicha estructura. Esta técnica es ineficiente porque se debe copiar toda la estructura de datos subyacente en cada escritura, lo que conlleva un rendimiento deficiente para m modificaciones de un array de tamaño n . La gestión de memoria mediante copia en escritura puede reducir el coste de una actualización de a , donde B es el tamaño del bloque de memoria y u el número de páginas actualizadas en una operación. ${\displaystyle O(n\cdot m)}$${\displaystyle \Theta (n)}$${\displaystyle O(Bu)}$

El método de nodo gordo consiste en registrar todos los cambios realizados en los campos de los nodos en los propios nodos, sin borrar los valores antiguos de los campos. Esto requiere que los nodos puedan volverse arbitrariamente "gordos". En otras palabras, cada nodo gordo contiene la misma información y campos de puntero que un nodo efímero, junto con espacio para un número arbitrario de valores de campo adicionales. Cada valor de campo adicional tiene un nombre de campo asociado y una marca de versión que indica la versión en la que se modificó el campo nombrado para tener el valor especificado. Además, cada nodo gordo tiene su propia marca de versión, que indica la versión en la que se creó el nodo. El único propósito de que los nodos tengan marcas de versión es asegurar que cada nodo contenga solo un valor por nombre de campo por versión. Para navegar por la estructura, cada valor de campo original en un nodo tiene una marca de versión de cero.

Con el método de nodo gordo, se requiere un espacio de O(1) para cada modificación: solo se almacenan los nuevos datos. Cada modificación toma un tiempo adicional de O(1) para almacenar la modificación al final del historial de modificaciones. Este es un límite de tiempo amortizado , suponiendo que el historial de modificaciones se almacena en un arreglo de tamaño creciente . En el momento del acceso , se debe encontrar la versión correcta en cada nodo a medida que se recorre la estructura. Si se hicieran m modificaciones, entonces cada operación de acceso tendría una ralentización resultante del costo de encontrar la modificación más cercana en el arreglo. Alternativamente, se puede emplear el árbol de van Emde Boas en cada nodo (posiblemente la versión eficiente en espacio usando hashing) para reducir el tiempo para un acceso a costa de aumentar el tiempo de actualización a . Si solo se requiere persistencia parcial, el tiempo para una actualización se puede mantener en su orden de magnitud original, módulo aleatorización y amortización (ya que el tiempo para una sola actualización al nodo gordo se puede amortizar esperado ^{[ 6 ]} ). ${\displaystyle O(\log m)}$${\displaystyle O(\log \log m)}$${\displaystyle O(\log \log m)}$${\displaystyle O(1)}$

Este método presupone que la estructura de datos es un grafo enlazado de nodos. Al actualizar, se crea una copia de todos los nodos en la ruta hacia cualquier nodo que esté a punto de modificarse. Estos cambios deben propagarse en cascada a través de la estructura de datos: todos los nodos que apuntaban al nodo antiguo deben modificarse para que apunten al nuevo. Estas modificaciones provocan más cambios en cascada, y así sucesivamente, hasta llegar al nodo raíz.

Con m modificaciones, esto cuesta un tiempo de búsqueda aditivo de O(log m) . El tiempo y el espacio de modificación están limitados por el número máximo de ancestros para cualquier nodo en la estructura de datos multiplicado por el costo de la actualización en la estructura de datos efímera. En un árbol de búsqueda binaria balanceado sin punteros a padres, la complejidad temporal de modificación en el peor de los casos es O(log n + costo de actualización). Sin embargo, en una lista enlazada, la complejidad temporal de modificación en el peor de los casos es O(n + costo de actualización).

Driscoll, Sarnak, Sleator y Tarjan idearon ^{[ 1 ]} una forma de combinar las técnicas de nodos grandes y copia de rutas, logrando una ralentización de acceso de O(1) y una sobrecarga amortizada de O(1) en espacio y tiempo por modificación. Su método asume una estructura de datos enlazada con como máximo d punteros entrantes a cada nodo, donde d es una constante conocida.

En cada nodo se almacena un cuadro de modificación. Este cuadro puede contener una modificación del nodo (ya sea una modificación de uno de los punteros, de la clave del nodo o de algún otro dato específico del nodo) y una marca de tiempo que indique cuándo se aplicó dicha modificación. Inicialmente, el cuadro de modificación de cada nodo está vacío.

Cada vez que se accede a un nodo, se comprueba la casilla de modificación y se compara su marca de tiempo con la hora de acceso. (La hora de acceso especifica la versión de la estructura de datos que se está considerando). Si la casilla de modificación está vacía o la hora de acceso es anterior a la hora de modificación, se ignora la casilla de modificación y solo se considera la parte normal del nodo. Por otro lado, si la hora de acceso es posterior a la hora de modificación, se utiliza el valor de la casilla de modificación, sobrescribiendo el valor del nodo.

Modificar un nodo funciona así: (Se asume que cada modificación afecta a un puntero o campo similar). Si el cuadro de modificación del nodo está vacío, se rellena con la modificación. De lo contrario, el cuadro de modificación está lleno. Se crea una copia del nodo, pero utilizando solo los valores más recientes. La modificación se realiza directamente en el nuevo nodo, sin usar el cuadro de modificación. (Uno de los campos del nuevo nodo se sobrescribe y su cuadro de modificación permanece vacío). Finalmente, este cambio se propaga al nodo padre, al igual que al copiar una ruta. (Esto puede implicar rellenar el cuadro de modificación del padre o crear una copia del padre de forma recursiva. Si el nodo no tiene padre (es la raíz), se añade la nueva raíz a un array ordenado de raíces).

Con este algoritmo , dado cualquier instante t, existe como máximo una caja de modificación en la estructura de datos correspondiente a ese instante. Por lo tanto, una modificación en el instante t divide el árbol en tres partes: una parte contiene los datos anteriores al instante t, otra contiene los datos posteriores al instante t, y la tercera no se ve afectada por la modificación.

El tiempo y el espacio para las modificaciones requieren un análisis amortizado. Una modificación requiere un espacio amortizado de O(1) y un tiempo amortizado de O(1). Para entender por qué, usemos una función potencial ϕ , donde ϕ (T) es el número de nodos activos completos en T. Los nodos activos de T son simplemente los nodos que son accesibles desde la raíz actual en el momento actual (es decir, después de la última modificación). Los nodos activos completos son los nodos activos cuyas cajas de modificación están llenas.

Cada modificación implica un cierto número de copias, digamos k , seguidas de 1 cambio en una caja de modificación. Consideremos cada una de las k copias. Cada una cuesta O(1) espacio y tiempo, pero disminuye la función potencial en uno. (Primero, el nodo que se va a copiar debe estar lleno y vivo, por lo que contribuye a la función potencial. Sin embargo, la función potencial solo disminuirá si el nodo antiguo no es alcanzable en el nuevo árbol. Pero se sabe que no es alcanzable en el nuevo árbol; el siguiente paso en el algoritmo será modificar el padre del nodo para que apunte a la copia. Finalmente, se sabe que la caja de modificación de la copia está vacía. Por lo tanto, se ha reemplazado un nodo vivo lleno por un nodo vivo vacío, y ϕ disminuye en uno). El paso final llena una caja de modificación, lo que cuesta O(1) tiempo y aumenta ϕ en uno.

En resumen, el cambio en ϕ es Δ ϕ =1 − k . Por lo tanto, el algoritmo requiere O( k +Δ ϕ )= O(1) espacio y O( k +Δ ϕ +1) = O(1) tiempo.

La copia de rutas es uno de los métodos simples para lograr persistencia en una estructura de datos determinada, como los árboles de búsqueda binaria. Es conveniente contar con una estrategia general para implementar la persistencia que funcione con cualquier estructura de datos dada. Para lograrlo, consideramos un grafo dirigido G. Suponemos que cada vértice v en G tiene un número constante c de aristas salientes representadas por punteros. Cada vértice tiene una etiqueta que representa los datos. Consideramos que un vértice tiene un número limitado d de aristas que llegan a él , que definimos como inedges( v ). Permitimos las siguientes operaciones diferentes en G.

• CREATE-NODE(): Crea un nuevo vértice sin aristas entrantes ni salientes.
• CAMBIAR-BORDE( v , i , u ): Cambia el i- ^ésimo borde de v para que apunte a u.
• CHANGE-LABEL( v , x ): Cambia el valor de los datos almacenados en v a x

Cualquiera de las operaciones anteriores se realiza en un momento específico, y el propósito de la representación persistente del grafo es poder acceder a cualquier versión de G en cualquier momento. Para ello, definimos una tabla para cada vértice v en G. La tabla contiene c columnas y filas. Cada fila contiene, además de los punteros a las aristas salientes, una etiqueta que representa los datos del vértice y el tiempo t en el que se realizó la operación. Además, existe un array inedges( v ) que registra todas las aristas entrantes a v . Cuando una tabla está llena, se puede crear una nueva tabla con filas. La tabla antigua se vuelve inactiva y la nueva se convierte en la tabla activa. ${\displaystyle d+1}$${\displaystyle d+1}$

Una llamada a CREATE-NODE crea una nueva tabla y establece todas las referencias a nulo.

Si asumimos que se llama a CHANGE-EDGE( v , i , u ), entonces hay dos casos a considerar.

• Hay una fila vacía en la tabla del vértice v : en este caso copiamos la última fila de la tabla y cambiamos la i- ésima arista del vértice v para que apunte al nuevo vértice u.
• La tabla del vértice v está llena: en este caso necesitamos crear una nueva tabla. Copiamos la última fila de la tabla antigua en la nueva. Necesitamos iterar sobre el array inedges( v ) para que cada vértice del array apunte a la nueva tabla creada. Además, necesitamos cambiar la entrada v en inedges(w) para cada vértice w tal que exista la arista v ,w en el grafo G.

Funciona exactamente igual que CHANGE-EDGE, excepto que en lugar de cambiar la i- ^ésima arista del vértice, cambiamos la i- ^ésima etiqueta.

Para determinar la eficiencia del esquema propuesto anteriormente, utilizamos un argumento definido como un esquema de crédito. El crédito representa una moneda. Por ejemplo, el crédito puede usarse para pagar una mesa. El argumento establece lo siguiente:

• La creación de una tabla requiere un crédito.
• Cada llamada a CREATE-NODE incluye dos créditos.
• Cada llamada a CHANGE-EDGE incluye un crédito.

El esquema de créditos siempre debe cumplir la siguiente condición: cada fila de cada tabla activa almacena un crédito y la tabla tiene el mismo número de créditos que de filas. Confirmemos que esta condición se aplica a las tres operaciones: CREAR-NODO, CAMBIAR-ARISTA y CAMBIAR-ETIQUETA.

• CREATE-NODE: Adquiere dos créditos; uno se utiliza para crear la tabla y el otro se asigna a la fila que se agrega a la tabla. De esta manera, se mantiene la invariante.
• CHANGE-EDGE: Hay dos casos a considerar. El primer caso ocurre cuando aún hay al menos una fila vacía en la tabla. En este caso, se utiliza un crédito para la fila recién insertada. El segundo caso ocurre cuando la tabla está llena. En este caso, la tabla antigua se vuelve inactiva y los créditos se transfieren a la nueva tabla, además del crédito adquirido al llamar a CHANGE-EDGE. Por lo tanto, en total tenemos créditos. Un crédito se utilizará para la creación de la nueva tabla. Otro crédito se utilizará para la nueva fila añadida a la tabla y los d créditos restantes se utilizan para actualizar las tablas de los demás vértices que necesitan apuntar a la nueva tabla. Concluimos que el invariante se mantiene.${\displaystyle d+1}$${\displaystyle d+2}$
• CHANGE-LABEL: Funciona exactamente igual que CHANGE-EDGE.

En resumen, concluimos que las llamadas a CREATE_NODE y CHANGE_EDGE resultarán en la creación de tablas. Dado que cada tabla tiene un tamaño sin tener en cuenta las llamadas recursivas, entonces llenar una tabla requiere . Por lo tanto, la cantidad de trabajo requerida para completar una secuencia de operaciones está limitada por el número de tablas creadas multiplicado por . Cada operación de acceso se puede realizar en y hay m operaciones de borde y etiqueta, por lo que requiere . Concluimos que Existe una estructura de datos que puede completar cualquier secuencia n de CREATE-NODE, CHANGE-EDGE y CHANGE-LABEL y m operaciones de acceso en . ${\displaystyle n_{1}}$${\displaystyle n_{2}}$${\displaystyle 2\cdot n_{1}+n_{2}}$${\displaystyle O(d)}$${\displaystyle O(dc)}$${\displaystyle O(dc)}$${\displaystyle O(\log(d))}$${\displaystyle m\cdot O(\log(d))}$${\displaystyle O(n\cdot dc)+m\cdot O(\log(d))}$

Una de las aplicaciones útiles que se pueden resolver de manera eficiente mediante persistencia es la búsqueda del siguiente elemento. Supongamos que existen n segmentos de línea que no se intersecan ni se cruzan entre sí y que son paralelos al eje x. Queremos construir una estructura de datos que pueda consultar un punto p y devolver el segmento que se encuentra por encima de p (si existe). Comenzaremos resolviendo la búsqueda del siguiente elemento mediante el método ingenuo y luego mostraremos cómo resolverla utilizando el método de estructura de datos persistente.

Comenzamos con un segmento de línea vertical que comienza en el infinito y recorremos los segmentos de línea de izquierda a derecha. Hacemos una pausa cada vez que encontramos un punto final de estos segmentos. Las líneas verticales dividen el plano en franjas verticales. Si hay n segmentos de línea, podemos obtener franjas verticales ya que cada segmento tiene${\displaystyle 2\cdot n+1}$2 puntos finales. Ningún segmento comienza ni termina en la tira. Cada segmento o bien no toca la tira o la cruza completamente. Podemos pensar en los segmentos como objetos ordenados de arriba a abajo. Lo que nos interesa es dónde encaja el punto que estamos observando en este orden. Ordenamos los puntos finales de los segmentos por su coordenada x . Para cada tira , almacenamos en un diccionario el subconjunto de segmentos que la cruzan. Cuando la línea vertical barre los segmentos, cada vez que pasa por el punto final izquierdo de un segmento, lo añadimos al diccionario. Cuando pasa por el punto final derecho del segmento, lo eliminamos del diccionario. En cada punto final, guardamos una copia del diccionario y almacenamos todas las copias ordenadas por las coordenadas x . De esta forma, tenemos una estructura de datos que puede responder a cualquier consulta. Para encontrar el segmento que está encima de un punto p , podemos observar la coordenada x de p para saber a qué copia o tira pertenece. Luego podemos observar la coordenada y para encontrar el segmento que está encima. Por lo tanto, necesitamos dos búsquedas binarias, una para la coordenada x para encontrar la tira o la copia, y otra para la coordenada y para encontrar el segmento superior. Así, el tiempo de consulta es de . En esta estructura de datos, el espacio es el problema, ya que si asumimos que tenemos los segmentos estructurados de tal manera que cada segmento comienza antes del final de cualquier otro segmento, entonces el espacio requerido para construir la estructura usando el método ingenuo sería de . Veamos cómo podemos construir otra estructura de datos persistente con el mismo tiempo de consulta pero con un mejor espacio. ${\displaystyle s_{i}}$${\displaystyle s_{i}}$${\displaystyle O(\log(n))}$${\displaystyle O(n^{2})}$

Podemos notar que lo que realmente toma tiempo en la estructura de datos utilizada en el método ingenuo es que cada vez que pasamos de una tira a la siguiente, necesitamos tomar una instantánea de cualquier estructura de datos que estemos usando para mantener las cosas en orden ordenado. Podemos notar que una vez que obtenemos los segmentos que se intersecan , cuando pasamos a o bien sale algo o entra algo. Si la diferencia entre lo que está en y lo que está en es solo una inserción o eliminación, entonces no es una buena idea copiar todo de a . El truco es que como cada copia difiere de la anterior en solo una inserción o eliminación, entonces necesitamos copiar solo las partes que cambian. Supongamos que tenemos un árbol con raíz en T . Cuando insertamos una clave k en el árbol, creamos una nueva hoja que contiene k . Realizar rotaciones para reequilibrar el árbol solo modificará los nodos del camino de k a T . Antes de insertar la clave k en el árbol, copiamos todos los nodos en el camino de k a T . Ahora tenemos 2 versiones del árbol, la original que no contiene k y el nuevo árbol que contiene k y cuya raíz es una copia de la raíz de T. Dado que copiar la ruta de k a T no aumenta el tiempo de inserción en más de un factor constante, entonces la inserción en la estructura de datos persistente toma tiempo. Para la eliminación, necesitamos encontrar qué nodos se verán afectados por la eliminación. Para cada nodo v afectado por la eliminación, copiamos la ruta desde la raíz hasta v . Esto proporcionará un nuevo árbol cuya raíz es una copia de la raíz del árbol original. Luego realizamos la eliminación en el nuevo árbol. Terminaremos con 2 versiones del árbol. La original que contiene k y la nueva que no contiene k . Dado que cualquier eliminación solo modifica la ruta desde la raíz hasta v y cualquier algoritmo de eliminación apropiado se ejecuta en , por lo tanto, la eliminación en la estructura de datos persistente toma . Cada secuencia de inserción y eliminación provocará la creación de una secuencia de diccionarios, versiones o árboles, donde cada uno es el resultado de operaciones . Si cada uno contiene m elementos, la búsqueda en cada uno toma . Usando esta estructura de datos persistente, podemos resolver el problema de búsqueda del siguiente elemento en tiempo y espacio de consulta en lugar de . A continuación, encontrará el código fuente .${\displaystyle s_{i}}$${\displaystyle s_{i+1}}$${\displaystyle s_{i}}$${\displaystyle s_{i+1}}$${\displaystyle s_{i}}$${\displaystyle s_{i+1}}$${\displaystyle O(\log(n))}$${\displaystyle O(\log(n))}$${\displaystyle O(\log(n))}$${\displaystyle S_{1},S_{2},\dots S_{i}}$${\displaystyle S_{i}}$${\displaystyle S_{1},S_{2},\dots S_{i}}$${\displaystyle S_{i}}$${\displaystyle S_{i}}$${\displaystyle O(\log(m))}$${\displaystyle O(\log(n))}$${\displaystyle O(n\cdot \log(n))}$${\displaystyle O(n^{2})}$por un ejemplo relacionado con el siguiente problema de búsqueda.

Las estructuras de datos puramente funcionales son automáticamente persistentes. Quizás la estructura de datos persistente más simple sea la lista enlazada simple o lista basada en cons , una lista simple de objetos formada por cada uno de los cuales contiene una referencia al siguiente en la lista. Esta es persistente porque se puede tomar el final de la lista, es decir, los últimos k elementos para algún k , y se pueden agregar nuevos nodos delante de él. El final no se duplica, sino que se comparte entre la lista antigua y la nueva. Siempre que el contenido del final sea inmutable, este intercambio será invisible para el programa.

Muchas estructuras de datos comunes basadas en referencias, como árboles rojo-negro , ^{[ 7 ]} pilas , ^{[ 8 ]} y treaps , ^{[ 9 ]} pueden adaptarse fácilmente para crear una versión persistente. Otras requieren un poco más de esfuerzo, por ejemplo: colas , dequeues y extensiones que incluyen min-deques (que tienen una operación adicional O (1) min que devuelve el elemento mínimo) y deques de acceso aleatorio (que tienen una operación adicional de acceso aleatorio con una complejidad sublineal, generalmente logarítmica).

Las estructuras de datos persistentes que se basan en estructuras inmutables ("puramente funcionales") deben contrastarse con las estructuras que utilizan actualizaciones destructivas (mutación) y que se hacen persistentes utilizando las técnicas de copia de nodos o rutas descritas anteriormente.

Las listas enlazadas simples son la estructura de datos básica en los lenguajes funcionales. ^{[ 10 ]} Algunos lenguajes derivados de ML , como Haskell , son puramente funcionales porque una vez que se ha asignado un nodo en la lista, no se puede modificar, solo copiar, referenciar o destruir por el recolector de basura cuando nada hace referencia a él. (Cabe señalar que ML en sí mismo no es puramente funcional, pero admite un subconjunto de operaciones de lista no destructivas, lo cual también es cierto en los dialectos de lenguajes funcionales Lisp (LISt Processing) como Scheme y Racket ).

Consideremos las dos listas:

xs = [0, 1, 2] ys = [3, 4, 5] 

Estos quedarían representados en la memoria por:

donde un círculo indica un nodo en la lista (la flecha que sale representa el segundo elemento del nodo, que es un puntero a otro nodo).

Ahora concatenamos las dos listas:

zs = xs ++ ys 

da como resultado la siguiente estructura de memoria:

Observe que los nodos de la lista xsse han copiado, pero los nodos de ysse comparten. Como resultado, las listas originales ( xsy ys) persisten y no se han modificado.

La razón de la copia es que el último nodo en xs(el nodo que contiene el valor original 2) no se puede modificar para que apunte al inicio de ys, porque eso cambiaría el valor de xs.

Consideremos un árbol de búsqueda binaria , ^{[ 10 ]} donde cada nodo del árbol tiene el invariante recursivo de que todos los subnodos contenidos en el subárbol izquierdo tienen un valor menor o igual al valor almacenado en el nodo, y los subnodos contenidos en el subárbol derecho tienen un valor mayor que el valor almacenado en el nodo.

Por ejemplo, el conjunto de datos

xs = [a, b, c, d, f, g, h] 

podría representarse mediante el siguiente árbol de búsqueda binaria:

Una función que inserta datos en el árbol binario y mantiene el invariante es:

fun insert ( x , E ) = T ( E , x , E ) | insert ( x , s as T ( a , y , b )) = if x < y then T ( insert ( x , a ), y , b ) else if x > y then T ( a , y , insert ( x , b )) else s

Después de ejecutar

ys = insertar ("e", xs) 

Se produce la siguiente configuración:

Observe dos puntos: primero, el árbol original ( xs) persiste. Segundo, muchos nodos comunes se comparten entre el árbol antiguo y el nuevo. Esta persistencia y compartición es difícil de gestionar sin algún tipo de recolección de basura (GC) para liberar automáticamente los nodos que no tienen referencias activas, y es por eso que GC es una característica común en los lenguajes de programación funcional .

Un trie mapeado a matriz hash persistente es una variante especializada de un trie mapeado a matriz hash que conserva versiones anteriores de sí mismo en cualquier actualización. Se utiliza a menudo para implementar una estructura de datos de mapa persistente de propósito general. ^{[ 11 ]}

Los árboles hash mapeados fueron descritos originalmente en un artículo de 2001 de Phil Bagwell titulado "Árboles hash ideales". Este artículo presentó una tabla hash mutable donde "los tiempos de inserción, búsqueda y eliminación son pequeños y constantes, independientemente del tamaño del conjunto de claves, y las operaciones son O(1). Se pueden garantizar tiempos pequeños en el peor de los casos para las operaciones de inserción, búsqueda y eliminación, y los fallos cuestan menos que las búsquedas exitosas". ^{[ 12 ]} Esta estructura de datos fue posteriormente modificada por Rich Hickey para que fuera completamente persistente para su uso en el lenguaje de programación Clojure . ^{[ 13 ]}

Conceptualmente, los árboles de búsqueda mapeados por matrices hash funcionan de manera similar a cualquier árbol genérico , ya que almacenan nodos jerárquicamente y los recuperan siguiendo una ruta hacia un elemento específico. La diferencia clave radica en que los árboles de búsqueda mapeados por matrices hash primero utilizan una función hash para transformar su clave de búsqueda en un entero (generalmente de 32 o 64 bits). La ruta hacia abajo en el árbol se determina utilizando segmentos de la representación binaria de ese entero para indexar una matriz dispersa en cada nivel del árbol. Los nodos hoja del árbol se comportan de manera similar a los cubos utilizados para construir tablas hash y pueden contener o no múltiples candidatos, dependiendo de las colisiones de hash . ^{[ 11 ]}

La mayoría de las implementaciones de árboles de prefijos persistentes mapeados a matrices hash utilizan un factor de ramificación de 32. Esto significa que, en la práctica, si bien las inserciones, eliminaciones y búsquedas en un árbol de prefijos persistente mapeado a una matriz hash tienen una complejidad computacional de O (log n ), para la mayoría de las aplicaciones son efectivamente de tiempo constante, ya que se requeriría una cantidad extremadamente grande de entradas para que cualquier operación tomara más de una docena de pasos. ^{[ 14 ]}

Haskell es un lenguaje funcional puro y, por lo tanto, no permite la mutación. Por consiguiente, todas las estructuras de datos en el lenguaje son persistentes, ya que es imposible no preservar el estado anterior de una estructura de datos con semántica funcional. ^{[ 15 ]} Esto se debe a que cualquier cambio en una estructura de datos que invalide versiones anteriores de la misma violaría la transparencia referencial .

En su biblioteca estándar, Haskell tiene implementaciones persistentes eficientes para listas enlazadas, ^{[ 16 ]} mapas (implementados como árboles equilibrados en tamaño), ^{[ 17 ]} y conjuntos ^{[ 18 ]} entre otros. ^{[ 19 ]}

Al igual que muchos lenguajes de programación de la familia Lisp , Clojure incluye una implementación de lista enlazada, pero a diferencia de otros dialectos, su implementación de lista enlazada impone persistencia en lugar de ser persistente por convención. ^{[ 20 ]} Clojure también cuenta con implementaciones eficientes de vectores, mapas y conjuntos persistentes basados ​​en árboles de búsqueda mapeados a matrices hash persistentes. Estas estructuras de datos implementan las partes obligatorias de solo lectura del marco de colecciones de Java . ^{[ 21 ]}

Los diseñadores del lenguaje Clojure abogan por el uso de estructuras de datos persistentes sobre estructuras de datos mutables porque tienen semántica de valor, lo que ofrece la ventaja de hacerlas libremente compartibles entre hilos con alias baratos, fáciles de fabricar e independientes del lenguaje. ^{[ 22 ]}

Estas estructuras de datos constituyen la base del soporte de Clojure para la computación paralela , ya que permiten reintentos sencillos de operaciones para evitar condiciones de carrera y semántica de comparación e intercambio atómicos . ^{[ 23 ]}

El lenguaje de programación Elm es puramente funcional, al igual que Haskell, lo que hace que todas sus estructuras de datos sean persistentes por necesidad. Contiene implementaciones persistentes de listas enlazadas, así como arreglos, diccionarios y conjuntos persistentes. ^{[ 24 ]}

Elm utiliza una implementación personalizada del DOM virtual que aprovecha la naturaleza persistente de los datos de Elm. En 2016, los desarrolladores de Elm informaron que este DOM virtual permite que el lenguaje Elm renderice HTML más rápido que los populares frameworks de JavaScript React , Ember y Angular . ^{[ 25 ]}

El lenguaje de programación Java no es particularmente funcional. A pesar de ello, el paquete principal del JDK, java.util.concurrent, incluye CopyOnWriteArrayList y CopyOnWriteArraySet, que son estructuras persistentes implementadas mediante técnicas de copia en escritura. Sin embargo, la implementación habitual de mapas concurrentes en Java, ConcurrentHashMap, no es persistente. Existen colecciones totalmente persistentes disponibles en bibliotecas de terceros ^{[ 26 ]} u otros lenguajes de la JVM.

El popular framework frontend de JavaScript React se usa frecuentemente junto con un sistema de gestión de estado que implementa la arquitectura Flux , ^{[ 27 ] [ 28 ]} una implementación popular de la cual es la biblioteca de JavaScript Redux . La biblioteca Redux se inspira en el patrón de gestión de estado utilizado en el lenguaje de programación Elm, lo que significa que exige que los usuarios traten todos los datos como persistentes. ^{[ 29 ]} Como resultado, el proyecto Redux recomienda que en ciertos casos los usuarios utilicen bibliotecas para estructuras de datos persistentes, seguras y eficientes. Según se informa, esto permite un mayor rendimiento que cuando se comparan o se hacen copias de objetos JavaScript regulares. ^{[ 30 ]}

Una de estas bibliotecas de estructuras de datos persistentes, Immutable.js, se basa en las estructuras de datos disponibles y popularizadas por Clojure y Scala. ^{[ 31 ]} La documentación de Redux la menciona como una de las posibles bibliotecas que pueden proporcionar inmutabilidad forzada. ^{[ 30 ]} Mori.js trae estructuras de datos similares a las de Clojure a JavaScript. ^{[ 32 ]} Immer.js presenta un enfoque interesante donde se "crea el siguiente estado inmutable mutando el actual". ^{[ 33 ]} Immer.js utiliza objetos nativos de JavaScript y no estructuras de datos persistentes eficientes, lo que podría causar problemas de rendimiento cuando el tamaño de los datos es grande.

Los términos de Prolog son inmutables por naturaleza y, por lo tanto, las estructuras de datos suelen ser persistentes. Su rendimiento depende del uso compartido y la recolección de basura que ofrece el sistema Prolog. ^{[ 34 ]} Las extensiones a términos de Prolog que no son básicos no siempre son factibles debido a la explosión del espacio de búsqueda. Los objetivos diferidos podrían mitigar el problema.

Algunos sistemas Prolog, no obstante, proporcionan operaciones destructivas como setarg/3, que pueden presentarse en diferentes variantes, con o sin copia y con o sin retroceso del cambio de estado. Hay casos en los que setarg/3 se utiliza para proporcionar una nueva capa declarativa, como un solucionador de restricciones. ^{[ 35 ]}

El lenguaje de programación Scala promueve el uso de estructuras de datos persistentes para implementar programas utilizando el "Estilo Objeto-Funcional". ^{[ 36 ]} Scala contiene implementaciones de muchas estructuras de datos persistentes, incluyendo listas enlazadas, árboles rojo-negro , así como tries mapeados a matrices hash persistentes, como se introdujo en Clojure. ^{[ 37 ]}

Debido a que las estructuras de datos persistentes a menudo se implementan de tal manera que las versiones sucesivas de una estructura de datos comparten la memoria subyacente ^{[ 38 ],} el uso ergonómico de dichas estructuras de datos generalmente requiere algún tipo de sistema de recolección de basura automática , como el conteo de referencias o el marcado y barrido . ^{[ 39 ]} En algunas plataformas donde se utilizan estructuras de datos persistentes, es una opción no usar la recolección de basura, lo que, si bien puede provocar fugas de memoria , en algunos casos puede tener un impacto positivo en el rendimiento general de una aplicación. ^{[ 40 ]}

• Copia en escritura
• Base de datos de navegación
• Datos persistentes
• Estructura de datos retroactiva
• Estructura de datos puramente funcional

• Implementación ligera en Java de árboles rojo-negro persistentes.
• Estructuras persistentes eficientes en C# Archivado el 21/12/2017 en Wayback Machine
• PersistentBST en GitHub : repositorio de GitHub que contiene implementaciones de BST persistentes mediante técnicas de copia en escritura (Copy-on-Write) y copia de rutas. Para usar las implementaciones de BST persistentes, simplemente clone el repositorio y siga las instrucciones del archivo README.