En informática , una estructura de datos persistente o estructura de datos no efímera es una estructura de datos que siempre conserva la versión anterior de sí misma cuando es modificada. Estas estructuras de datos son efectivamente inmutables , ya que sus operaciones no actualizan (visiblemente) la estructura en el lugar, sino que siempre generan una nueva estructura actualizada. El término fue introducido en el artículo de 1986 de Driscoll, Sarnak, Sleator y Tarjan. [1]
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. La estructura de datos es completamente persistente si se puede acceder y modificar cada versión. Si también hay una operación de fusión o fusión que puede crear una nueva versión a partir de dos versiones anteriores, la estructura de datos se llama confluentemente persistente . Las estructuras que no son persistentes se denominan efímeras . [2]
Estos tipos 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 totalmente persistente, 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 consultar o actualizar versiones anteriores de una estructura de datos se degraden, como ocurre con la estructura de datos de cuerda . [4] Además, una estructura de datos puede denominarse confluentemente persistente si, además de ser completamente persistente, se pueden combinar dos versiones de la misma estructura de datos para formar una nueva versión que aún sea completamente persistente. [5]
Un tipo de estructura de datos donde el usuario puede consultar cualquier versión de la estructura pero solo puede actualizar la última versión.
Una estructura de datos efímera se puede convertir en una estructura de datos parcialmente persistente utilizando algunas técnicas.
Una de las técnicas consiste en utilizar una versión aleatoria de Van Emde Boas Tree, que se crea mediante hash dinámico perfecto. Esta estructura de datos se crea de la siguiente manera:
El tamaño de esta estructura de datos está limitado por la cantidad de elementos almacenados en la estructura que es O (m). La inserción de un nuevo elemento máximo se realiza en un tiempo esperado y amortizado constante O(1). Finalmente, se puede realizar una consulta para encontrar un elemento en esta estructura en el peor de los casos O (log (log n)). [6]
Un método para crear una estructura de datos persistente es utilizar una estructura de datos efímera proporcionada por la plataforma, como una matriz, para almacenar los datos en la estructura de datos y copiar la totalidad de esa estructura de datos utilizando la semántica de copia en escritura para cualquier actualización de los datos. estructura. Esta es una técnica ineficiente porque toda la estructura de datos de respaldo debe copiarse para cada escritura, lo que lleva al peor de los casos O(n·m) características de rendimiento para m modificaciones de una matriz de tamaño n. [ cita necesaria ]
El método del nodo grueso consiste en registrar todos los cambios realizados en los campos del nodo en los propios nodos, sin borrar los valores antiguos de los campos. Esto requiere que se permita que los nodos se vuelvan "gordos" arbitrariamente. En otras palabras, cada nodo grueso contiene la misma información y campos de puntero que un nodo efímero, junto con espacio para una cantidad arbitraria de valores de campo adicionales. Cada valor de campo adicional tiene un nombre de campo asociado y un sello de versión que indica la versión en la que se cambió el campo nombrado para tener el valor especificado. Además, cada nodo gordo tiene su propio sello de versión, que indica la versión en la que se creó el nodo. El único propósito de que los nodos tengan sellos de versión es asegurarse de que cada nodo solo contenga un valor por nombre de campo por versión. Para navegar a través de la estructura, cada valor de campo original en un nodo tiene un sello de versión de cero.
Al utilizar el método del nodo grueso, se requiere espacio O(1) para cada modificación: simplemente almacene los nuevos datos. Cada modificación requiere O(1) tiempo adicional 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 almacene en una matriz ampliable . En el momento del acceso , se debe encontrar la versión correcta en cada nodo a medida que se atraviesa la estructura. Si se hicieran "m" modificaciones, entonces cada operación de acceso tendría una desaceleración O(log m) resultante del costo de encontrar la modificación más cercana en la matriz.
Con el método de copia de ruta, se realiza una copia de todos los nodos en la ruta a cualquier nodo que esté a punto de modificarse. Estos cambios deben luego volverse 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 nodo. Estas modificaciones provocan más cambios en cascada, y así sucesivamente, hasta llegar al nodo raíz.
Con m modificaciones, esto cuesta O(log m) tiempo de búsqueda aditiva . El tiempo y el espacio de modificación están limitados por el tamaño de la ruta más larga en la estructura de datos y el costo de la actualización en la estructura de datos efímera. En un árbol de búsqueda binaria equilibrado sin punteros principales, la complejidad del tiempo de modificación en el peor de los casos es O (log n + costo de actualización). Sin embargo, en una lista vinculada, la complejidad del tiempo de modificación en el peor de los casos es O (n + costo de actualización).
A Driscoll, Sarnak, Sleator y Tarjan se les ocurrió [1] una forma de combinar las técnicas de nodos gruesos y copia de rutas, logrando una ralentización del acceso O(1) y una modificación del espacio y la complejidad temporal O(1).
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 de cuándo se aplicó esa modificación. Inicialmente, el cuadro de modificación de cada nodo está vacío.
Cada vez que se accede a un nodo, se marca la casilla de modificación y su marca de tiempo se compara con el tiempo de acceso. (El tiempo de acceso especifica la versión de la estructura de datos que se está considerando). Si el cuadro de modificación está vacío, o el tiempo de acceso es anterior al tiempo de modificación, entonces el cuadro de modificación se ignora y solo se considera la parte normal del nodo. Por otro lado, si el tiempo de acceso es posterior al tiempo de modificación, entonces se utiliza el valor del cuadro de modificación, anulando ese valor en el nodo.
La modificación de un nodo funciona así. (Se supone que cada modificación toca un puntero o campo similar). Si el cuadro de modificación del nodo está vacío, se llena con la modificación. De lo contrario, el cuadro de modificación estará lleno. Se realiza una copia del nodo, pero utilizando solo los valores más recientes. La modificación se realiza directamente en el nuevo nodo, sin utilizar 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 transmite en cascada al nodo principal, al igual que la copia de ruta. (Esto puede implicar llenar el cuadro de modificación del padre o hacer una copia del padre de forma recursiva. Si el nodo no tiene padre (es la raíz), se agrega la nueva raíz a una matriz ordenada de raíces).
Con este algoritmo , dado cualquier momento t, existe como máximo un cuadro de modificación en la estructura de datos con el tiempo t. Por lo tanto, una modificación en el momento t divide el árbol en tres partes: una parte contiene los datos anteriores al momento t, una parte contiene los datos posteriores al momento t y la otra parte no se vio afectada por la modificación.
El tiempo y el espacio para las modificaciones requieren un análisis amortizado. Una modificación requiere O(1) espacio amortizado y O(1) tiempo amortizado. Para ver por qué, use una función potencial ϕ, donde ϕ(T) es el número de nodos activos completos en T. Los nodos activos de T son solo los nodos a los que se puede acceder 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 cuyos cuadros de modificación están llenos.
Cada modificación implica una cierta cantidad de copias, digamos k, seguidas de 1 cambio en un cuadro de modificación. Considere cada una de las k copias. Cada uno 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 activo, por lo que contribuye a la función potencial. Sin embargo, la función potencial sólo disminuirá si no se puede acceder al nodo antiguo en el nuevo árbol. Pero se sabe que no es accesible 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 el cuadro de modificación de la copia está vacío. Por lo tanto, se ha reemplazado un nodo activo completo. reemplazado con un nodo activo vacío, y ϕ baja en uno). El paso final llena un cuadro de modificación, que cuesta O(1) tiempo y aumenta ϕ en uno.
En conjunto, el cambio en ϕ es Δϕ =1− k. Por lo tanto, el algoritmo toma 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 determinada estructura de datos, como los árboles de búsqueda binarios. Es bueno tener una estrategia general para implementar la persistencia que funcione con cualquier estructura de datos determinada. Para lograrlo, consideramos un gráfico dirigido G . Suponemos que cada vértice v en G tiene un número constante c de aristas salientes que están representadas por punteros. Cada vértice tiene una etiqueta que representa los datos. Consideramos que un vértice tiene un número acotado d de aristas que conducen a él y que definimos como inedges ( v ). Permitimos las siguientes operaciones diferentes en G .
Cualquiera de las operaciones anteriores se realiza en un momento específico y el propósito de la representación del gráfico persistente es poder acceder a cualquier versión de G en cualquier momento dado. 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 para los bordes salientes, una etiqueta que representa los datos en el vértice y un tiempo t en el que se realizó la operación. Además de eso, hay una matriz inedges( v ) que realiza un seguimiento de todos los bordes entrantes a v . Cuando una tabla está llena, se puede crear una nueva tabla con filas. La tabla anterior pasa a estar inactiva y la nueva tabla se convierte en la tabla activa.
Una llamada a CREATE-NODE crea una nueva tabla y establece todas las referencias en nulas
Si asumimos que se llama a CHANGE-EDGE( v , i , u ), entonces hay dos casos a considerar.
Funciona exactamente igual que CHANGE-EDGE excepto que en lugar de cambiar el i- ésimo borde del vértice, cambiamos la i -ésima etiqueta.
Para encontrar la eficiencia del esquema propuesto anteriormente, utilizamos un argumento definido como esquema de crédito. El crédito representa una moneda. Por ejemplo, el crédito se puede utilizar para pagar una mesa. El argumento expresa lo siguiente:
El esquema de crédito siempre debe satisfacer la siguiente invariante: cada fila de cada tabla activa almacena un crédito y la tabla tiene la misma cantidad de créditos que la cantidad de filas. Confirmemos que el invariante se aplica a las tres operaciones CREAR-NODO, CAMBIAR-BORDE y CAMBIAR-ETIQUETA.
Como resumen, concluimos que tener llamadas a CREATE_NODE y llamadas a CHANGE_EDGE dará como resultado la creación de tablas. Dado que cada tabla tiene un tamaño sin tener en cuenta las llamadas recursivas, completar una tabla requiere que el factor d adicional provenga de la actualización de los inedges en otros nodos. Por lo tanto, la cantidad de trabajo necesaria 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 y hay operaciones de borde y etiqueta, por lo que requiere . Concluimos que existe una estructura de datos que puede completar cualquier secuencia de CREATE-NODE, CHANGE-EDGE y CHANGE-LABEL en .
Una de las aplicaciones útiles que se puede resolver de manera eficiente usando la persistencia es la búsqueda del siguiente elemento. Suponga que hay segmentos de línea que no se cruzan y que no se cruzan entre sí y que son paralelos al eje x. Queremos construir una estructura de datos que pueda consultar un punto y devolver el segmento anterior (si corresponde). Comenzaremos resolviendo la búsqueda del siguiente elemento usando el método ingenuo y luego mostraremos cómo resolverla usando el método de estructura de datos persistente.
Comenzamos con un segmento de línea vertical que comienza en el infinito y barremos 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 avión en franjas verticales. Si hay segmentos de línea, entonces podemos obtener franjas verticales ya que cada segmento tiene puntos finales. Ningún segmento comienza y termina en la tira. Cada segmento o no toca la tira o la cruza por completo. Podemos pensar en los segmentos como algunos objetos que están ordenados de arriba a abajo. Lo que nos importa es dónde encaja el punto que estamos analizando en este orden. Ordenamos los puntos finales de los segmentos por sus coordenadas. Para cada tira , almacenamos los segmentos del subconjunto que se cruzan en un diccionario. Cuando la línea vertical barre los segmentos de línea, cada vez que pasa por el punto final izquierdo de un segmento, lo agregamos al diccionario. Cuando pasa por el extremo derecho del segmento, lo eliminamos del diccionario. En cada punto final, guardamos una copia del diccionario y almacenamos todas las copias ordenadas por coordenadas. Así tenemos una estructura de datos que puede responder a cualquier consulta. Para encontrar el segmento encima de un punto , podemos fijarnos en la coordenada de para saber a qué copia o tira pertenece. Luego podemos mirar la coordenada para encontrar el segmento encima de ella. Por lo tanto, necesitamos dos búsquedas binarias, una de coordenadas para encontrar la tira o la copia, y otra de coordenadas para encontrar el segmento encima de ella. Por tanto, 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 que la estructura se construya usando el método ingenuo sería . Veamos cómo podemos construir otra estructura de datos persistentes con el mismo tiempo de consulta pero con un mejor espacio.
Podemos notar que lo que realmente lleva tiempo en la estructura de datos utilizada en el método ingenuo es que cada vez que pasamos de una franja a la siguiente, necesitamos tomar una instantánea de cualquier estructura de datos que estemos usando para mantener las cosas en orden. Podemos notar que una vez que obtenemos los segmentos que se cruzan , cuando nos movemos hacia una cosa sale o una cosa entra. Si la diferencia entre lo que está y lo que está es solo una inserción o eliminación, entonces no es una buena idea copiar todo de a . El truco es que, dado que cada copia difiere de la anterior solo en una inserción o eliminación, entonces necesitamos copiar solo las partes que cambian. Supongamos que tenemos un árbol con raíces en . Cuando insertamos una clave en el árbol, creamos una nueva hoja que contiene . Realizar rotaciones para reequilibrar el árbol solo modificará los nodos de la ruta de a . Antes de insertar la clave en el árbol, copiamos todos los nodos en la ruta desde hasta . Ahora tenemos 2 versiones del árbol, la original que no contiene y el nuevo árbol que contiene y cuya raíz es una copia de la raíz de . Dado que copiar la ruta de a no aumenta el tiempo de inserción en más de un factor constante, la inserción en la estructura de datos persistentes lleva tiempo. Para la eliminación, necesitamos encontrar qué nodos se verán afectados por la eliminación. Para cada nodo afectado por la eliminación, copiamos la ruta desde la raíz a . 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. El original que contiene y el nuevo que no contiene . Dado que cualquier eliminación sólo modifica la ruta desde la raíz y se ejecuta cualquier algoritmo de eliminación apropiado , la eliminación en la estructura de datos persistentes tarda . Cada secuencia de inserción y eliminación provocará la creación de una secuencia de diccionarios o versiones o árboles donde cada uno es el resultado de operaciones . Si cada uno contiene elementos, entonces la búsqueda en cada uno toma . Usando esta estructura de datos persistente podemos resolver el problema de búsqueda del siguiente elemento en el tiempo y espacio de consulta en lugar de . A continuación encontrará el código fuente para ver un ejemplo relacionado con el siguiente problema de búsqueda.
Quizás la estructura de datos persistentes más simple sea la lista enlazada individualmente o lista basada en contras , una lista simple de objetos formada por cada uno de los cuales lleva una referencia al siguiente en la lista. Esto es persistente porque se puede tomar la cola de la lista, es decir, los últimos k elementos para algunos k , y se pueden agregar nuevos nodos delante de ella. La cola no se duplicará, sino que se compartirá entre la lista anterior y la nueva. Mientras el contenido de la cola 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] se pueden adaptar fácilmente para crear una versión persistente. Algunos otros necesitan un poco más de esfuerzo, por ejemplo: colas , colas y extensiones que incluyen min-deques (que tienen una operación O (1) min adicional que devuelve el elemento mínimo) y deques de acceso aleatorio (que tienen una operación adicional de acceso aleatorio con complejidad sublineal, generalmente logarítmica).
También existen estructuras de datos persistentes que utilizan operaciones destructivas [ se necesita aclaración ] , lo que las hace imposibles de implementar de manera eficiente en lenguajes puramente funcionales (como Haskell fuera de mónadas especializadas como state o IO), pero posibles en lenguajes como C o Java. Este tipo de estructuras de datos a menudo se pueden evitar con un diseño diferente. Una ventaja principal de utilizar estructuras de datos puramente persistentes es que a menudo se comportan mejor en entornos multiproceso.
Las listas enlazadas individualmente 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, el recolector de basura no puede modificarlo, solo copiarlo, hacer referencia a él o destruirlo cuando nada hace referencia a él. (Tenga en cuenta que ML en sí no es puramente funcional, pero admite un subconjunto de operaciones de lista no destructivas, lo que también es cierto en los dialectos del lenguaje funcional Lisp (LISt Processing) como Scheme y Racket ).
Considere 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 hacia afuera representa el segundo elemento del nodo que es un puntero a otro nodo).
Ahora concatenando 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 la lista ysse comparten. Como resultado, las listas originales ( xsy ys) persisten y no se han modificado.
El motivo de la copia es que el último nodo de 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.
Considere un árbol de búsqueda binario , [10] donde cada nodo del árbol tiene la invariante recursiva 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 El subárbol tiene un valor que es mayor que el valor almacenado en el nodo.
Por ejemplo, el conjunto de datos
xs = [a, b, c, d, f, g, h]
podría estar representado por el siguiente árbol de búsqueda binario:
Una función que inserta datos en el árbol binario y mantiene el invariante es:
inserción divertida ( x , E ) = T ( E , x , E ) | inserte ( x , s como T ( a , y , b )) = si x < y entonces T ( inserte ( x , a ), y , b ) si no, si x > y entonces T ( a , y , inserte ( x , b )) más sDespués de ejecutar
ys = insertar ("e", xs)Se produce la siguiente configuración:
Observe dos puntos: primero, el árbol original ( xs) persiste. En segundo lugar, muchos nodos comunes se comparten entre el árbol antiguo y el nuevo. Tal persistencia e intercambio son difíciles 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 la GC es una característica que se encuentra comúnmente en los lenguajes de programación funcionales .
Repositorio de GitHub que contiene implementaciones de BST persistentes que utilizan técnicas de nodos grasos, copia en escritura y copia de ruta.
Para utilizar las implementaciones persistentes de BST, simplemente clone el repositorio y siga las instrucciones proporcionadas en el archivo README.
Enlace: https://github.com/DesaultierMAKK/PersistentBST
Un trie mapeado de matriz hash persistente es una variante especializada de un trie mapeado de matriz hash que preservará las versiones anteriores de sí mismo en cualquier actualización. A menudo se utiliza para implementar una estructura de datos de mapas persistentes de propósito general. [11]
Los intentos mapeados de matrices hash se describieron originalmente en un artículo de 2001 de Phil Bagwell titulado "Ideal Hash Trees". Este documento 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, las operaciones son O(1). Se pueden garantizar y se pierden tiempos pequeños en el peor de los casos para las operaciones de inserción, búsqueda y eliminación cuestan menos que las búsquedas exitosas". [12] Rich Hickey modificó esta estructura de datos para que fuera completamente persistente para su uso en el lenguaje de programación Clojure . [13]
Conceptualmente, los intentos mapeados de matrices hash funcionan de manera similar a cualquier árbol genérico en el sentido de que almacenan nodos jerárquicamente y los recuperan siguiendo una ruta hasta un elemento en particular. La diferencia clave es que los intentos Hash Array Mapped utilizan primero una función hash para transformar su clave de búsqueda en un entero (generalmente de 32 o 64 bits). Luego, la ruta hacia abajo en el árbol se determina utilizando porciones de la representación binaria de ese número entero para indexar en una matriz dispersa en cada nivel del árbol. Los nodos hoja del árbol se comportan de manera similar a los depósitos utilizados para construir tablas hash y pueden contener o no múltiples candidatos dependiendo de las colisiones hash . [11]
La mayoría de las implementaciones de intentos mapeados de matrices hash persistentes utilizan un factor de ramificación de 32 en su implementación. Esto significa que, en la práctica, si bien las inserciones, eliminaciones y búsquedas en una matriz hash persistente mapeada tienen una complejidad computacional de O (log n ), para la mayoría de las aplicaciones son efectivamente de tiempo constante, ya que requeriría una cantidad extremadamente grande de entradas para Haga que cualquier operación requiera más de una docena de pasos. [14]
Haskell es un lenguaje puramente funcional y por lo tanto no permite mutaciones. Por lo tanto, todas las estructuras de datos del 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 invalidara las versiones anteriores de una estructura de datos violaría la transparencia referencial .
En su biblioteca estándar, Haskell tiene implementaciones persistentes eficientes para listas enlazadas, [16] Mapas (implementados como árboles de tamaño equilibrado), [17] y Conjuntos [18], entre otros. [19]
Como muchos lenguajes de programación de la familia Lisp , Clojure contiene una implementación de una lista enlazada, pero a diferencia de otros dialectos su implementación de una lista enlazada ha impuesto la persistencia en lugar de ser persistente por convención. [20] Clojure también tiene implementaciones eficientes de vectores, mapas y conjuntos persistentes basados en intentos mapeados de 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 en lugar de estructuras de datos mutables porque tienen una semántica de valor que brinda el beneficio de hacerlas compartibles libremente entre subprocesos con alias baratos, fáciles de fabricar e independientes del lenguaje. [22]
Estas estructuras de datos forman la base del soporte de Clojure para la computación paralela , ya que permiten reintentos fáciles de operaciones para eludir las carreras de datos y la comparación e intercambio atómico de semántica. [23]
El lenguaje de programación Elm es puramente funcional como Haskell, lo que hace que todas sus estructuras de datos sean persistentes por necesidad. Contiene implementaciones persistentes de listas enlazadas, así como matrices, diccionarios y conjuntos persistentes. [24]
Elm utiliza una implementación DOM virtual personalizada que aprovecha la naturaleza persistente de los datos de Elm. A partir de 2016, los desarrolladores de Elm informaron que este DOM virtual permite que el lenguaje Elm represente HTML más rápido que los populares marcos de JavaScript React , Ember y Angular . [25]
El lenguaje de programación Java no es particularmente funcional. A pesar de esto, el paquete principal de 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. Las colecciones totalmente persistentes están disponibles en bibliotecas de terceros, [26] u otros lenguajes JVM.
El popular marco de interfaz de JavaScript React se utiliza con frecuencia 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 JavaScript Redux . La biblioteca Redux está inspirada 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 hagan uso de bibliotecas para estructuras de datos persistentes eficientes y aplicadas. Según se informa, esto permite un mayor rendimiento que al comparar o hacer copias de objetos JavaScript normales. [30]
Una de esas 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 aporta un enfoque interesante en el que se "crea el siguiente estado inmutable mutando el actual". [33] Immer.js utiliza objetos JavaScript nativos y estructuras de datos persistentes no eficientes y puede causar problemas de rendimiento cuando el tamaño de los datos es grande.
Los términos de prólogo son naturalmente inmutables y, por lo tanto, las estructuras de datos suelen ser estructuras de datos persistentes. Su rendimiento depende del intercambio y la recolección de basura que ofrece el sistema Prolog. [34] Las extensiones a términos Prolog no terrestres no siempre son factibles debido a la explosión del espacio de búsqueda. Los objetivos retrasados podrían mitigar el problema.
Sin embargo, algunos sistemas Prolog proporcionan operaciones destructivas como setarg/3, que pueden venir en diferentes versiones, con/sin copia y con/sin retroceso del cambio de estado. Hay casos en los que setarg/3 se utiliza con el fin de 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 funcional de objeto". [36] Scala contiene implementaciones de muchas estructuras de datos persistentes, incluidas listas vinculadas, árboles rojo-negro , así como intentos mapeados de 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 automático de recolección de basura , como el recuento de referencias o el marcado y barrido . [39] En algunas plataformas donde se utilizan estructuras de datos persistentes, es una opción no utilizar la recolección de basura que, si bien hacerlo puede provocar pérdidas de memoria , en algunos casos puede tener un impacto positivo en el rendimiento general de una aplicación. [40]
{{cite book}}: Mantenimiento CS1: varios nombres: lista de autores ( enlace ){{cite journal}}: Citar diario requiere |journal=( ayuda ){{cite journal}}: Citar diario requiere |journal=( ayuda ){{cite journal}}: Citar diario requiere |journal=( ayuda )