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 se modifica. Dichas estructuras de datos son efectivamente inmutables , ya que sus operaciones no actualizan (visiblemente) la estructura en el lugar, sino que siempre producen 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 versión más reciente. La estructura de datos es completamente persistente si se puede acceder a todas las versiones y modificarlas. Si también hay una operación de fusión o combinación que puede 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 versión más reciente. Esto implica un ordenamiento lineal entre cada versión de la estructura de datos. [3] En el modelo completamente 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 la consulta o actualización de versiones anteriores de una estructura de datos se degraden, como sucede con la estructura de datos rope . [4] Además, una estructura de datos puede considerarse 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 del árbol de Van Emde Boas, que se crea mediante un algoritmo hash perfecto dinámico. Esta estructura de datos se crea de la siguiente manera:
El tamaño de esta estructura de datos está limitado por el número de elementos almacenados en la estructura, que es O(m). La inserción de un nuevo elemento máximo se realiza en un tiempo constante esperado y amortizado de O(1). Finalmente, la consulta para encontrar un elemento se puede realizar en esta estructura en un tiempo O(log(log n)) en el peor de los casos. [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 la estructura de datos. Esta es una técnica ineficiente porque se debe copiar toda la estructura de datos de respaldo para cada escritura, lo que conduce a características de rendimiento de O(n·m) en el peor de los casos para m modificaciones de una matriz de tamaño n. [ cita requerida ]
El método de nodo fat 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 se permita que los nodos se vuelvan arbitrariamente "fat". En otras palabras, cada nodo fat contiene la misma información y los mismos 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 fat 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 por la estructura, cada valor de campo original en un nodo tiene un sello de versión de cero.
Al utilizar el método de nodo fat, se requiere O(1) espacio para cada modificación: solo se almacenan los datos nuevos. 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 almacena en una matriz ampliable . 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 desaceleración de 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 de la ruta hacia cualquier nodo que esté a punto de modificarse. Estos cambios deben luego repetirse en cascada a través de la estructura de datos: todos los nodos que apuntaban al nodo anterior deben modificarse para que apunten al nuevo nodo. Estas modificaciones provocan más cambios en cascada, y así sucesivamente, hasta que se llega al nodo raíz.
Con m modificaciones, esto cuesta O(log m) tiempo de búsqueda aditivo . 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 balanceado sin punteros principales, la complejidad del tiempo de modificación en el peor caso es O(log n + costo de actualización). Sin embargo, en una lista enlazada, la complejidad del tiempo de modificación en el peor caso es O(n + costo de actualización).
Driscoll, Sarnak, Sleator y Tarjan idearon [1] una forma de combinar las técnicas de nodos gordos y copia de rutas, logrando una desaceleración de acceso O(1) y una complejidad espacial y temporal de modificación 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 que indica 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 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 dicha casilla 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, anulando ese valor en el nodo.
La modificación de un nodo funciona de la siguiente manera (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 está lleno. Se realiza una copia del nodo, pero utilizando solo los últimos valores. La modificación se realiza directamente en el nuevo nodo, sin utilizar el cuadro de modificación (se sobrescribe uno de los campos del nuevo nodo y su cuadro de modificación permanece vacío). Finalmente, este cambio se aplica en cascada al padre del nodo, al igual que la copia de ruta (esto puede implicar llenar el cuadro de modificación del padre o hacer una copia del padre recursivamente. 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 un tiempo t, existe como máximo un cuadro de modificación en la estructura de datos con 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 ve 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é, utilice 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 una caja de modificación. Considere 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 activo, por lo que contribuye a la función potencial. Sin embargo, la función potencial solo disminuirá si el nodo anterior no es accesible 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 la caja de modificación de la copia está vacía. Por lo tanto, se reemplaza un nodo activo lleno con un nodo activo 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.
Poniendo todo junto, 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 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 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, 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 este propósito 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 se vuelve 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 borde i del vértice, cambiamos la etiqueta i .
Para hallar 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 puede utilizarse para pagar una mesa. El argumento establece 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 la invariante se aplica a las tres operaciones CREATE-NODE, CHANGE-EDGE y CHANGE-LABEL.
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 tamaño sin tener en cuenta las llamadas recursivas, entonces completar una tabla requiere donde el factor d adicional proviene de actualizar los bordes en otros nodos. 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 operaciones de borde y de etiqueta, por lo tanto, 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 mediante la persistencia es la búsqueda del siguiente elemento. Supongamos que hay segmentos de línea que no se intersecan y que no se cruzan entre sí y que son paralelos al eje x. Queremos crear una estructura de datos que pueda consultar un punto y devolver el segmento que se encuentra por encima (si lo hay). Comenzaremos resolviendo la búsqueda del siguiente elemento mediante el método ingenuo y luego mostraremos cómo resolverla mediante 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 plano en franjas verticales. Si hay segmentos de línea, podemos obtener franjas verticales ya que cada segmento tiene puntos finales. Ningún segmento comienza y termina en la franja. Cada segmento no toca la franja o la cruza por completo. Podemos pensar en los segmentos como algunos objetos que están en algún orden ordenado de arriba a abajo. Lo que nos importa es dónde encaja el punto que estamos mirando en este orden. Ordenamos los puntos finales de los segmentos por su coordenada. Para cada franja , almacenamos los segmentos del subconjunto que se cruzan en un diccionario. Cuando la línea vertical barre los segmentos de línea, siempre que pase por el punto final izquierdo de un segmento, lo agregamos 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. De este modo, tenemos una estructura de datos que puede responder a cualquier consulta. Para encontrar el segmento que se encuentra por encima de un punto , podemos mirar la coordenada de para saber a qué copia o tira pertenece. Luego, podemos mirar la coordenada para encontrar el segmento que se encuentra por encima de ella. Por lo tanto, necesitamos dos búsquedas binarias, una para la coordenada para encontrar la tira o la copia, y otra para la coordenada para encontrar el segmento que se encuentra por encima de ella. Por lo tanto, el tiempo de consulta tarda . 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 se construya la estructura utilizando el método ingenuo sería . Veamos cómo podemos construir otra estructura de datos persistente con el mismo tiempo de consulta pero con un mejor espacio.
Podemos notar que lo que realmente toma tiempo en la estructura de datos utilizada en el método ingenuo es que siempre que nos movemos 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. Podemos notar que una vez que obtenemos los segmentos que se intersecan , cuando nos movemos a sale una cosa o entra una cosa. Si la diferencia entre lo que está dentro y lo que está dentro 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 por solo una inserción o eliminación, entonces necesitamos copiar solo las partes que cambian. Supongamos que tenemos un árbol con raíz 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 de a . 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 solo modifica la ruta desde la raíz a y cualquier algoritmo de eliminación apropiado se ejecuta en , la eliminación en la estructura de datos persistentes lleva . 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 las operaciones . Si cada uno contiene elementos, entonces la búsqueda en cada uno toma . Usando esta estructura de datos persistente podemos resolver el siguiente problema de búsqueda de elementos en tiempo y espacio de consulta en lugar de . A continuación, encontrará el código fuente de un ejemplo relacionado con el siguiente problema de búsqueda.
Quizás la estructura de datos persistente más simple es la lista enlazada simple o lista basada en cons , 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 algún 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, esta compartición será invisible para el programa.
Muchas estructuras de datos comunes basadas en referencias, como árboles rojo-negros , [7] pilas , [8] y treaps , [9] se pueden adaptar fácilmente para crear una versión persistente. Algunas otras necesitan un poco más de esfuerzo, por ejemplo: colas , desencolas 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 complejidad sublineal, la mayoría de las veces logarítmica).
También existen estructuras de datos persistentes que utilizan operaciones destructivas [ aclaración necesaria ] , lo que hace que sea imposible implementarlas de manera eficiente en lenguajes puramente funcionales (como Haskell fuera de mónadas especializadas como state o IO), pero sí es posible en lenguajes como C o Java. Estos tipos de estructuras de datos a menudo se pueden evitar con un diseño diferente. Una ventaja principal de usar estructuras de datos puramente persistentes es que a menudo se comportan mejor en entornos multiproceso.
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. (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 de lenguaje funcional 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 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:
Tenga en cuenta que los nodos de la lista xsse han copiado, pero los nodos de ysse han compartido. Como resultado, las listas originales ( xsy ys) persisten y no se han modificado.
El motivo de la copia es que el último nodo en xs(el nodo que contiene el valor original 2) no se puede modificar para apuntar 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 que es menor o igual al valor almacenado en el nodo, y los subnodos contenidos en el subárbol derecho tienen 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 representarse mediante el siguiente árbol binario de búsqueda:
Una función que inserta datos en el árbol binario y mantiene la invariante es:
fun insert ( x , E ) = T ( E , x , E ) | insert ( x , scomoT ( a , y , b )) = si x < y entonces T ( insertar ( x , a ) , y , b ) de lo contrario si x > y entonces T ( a , y , insertar ( x , b )) de lo contrario 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. Dicha 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 la GC es una característica que se encuentra comúnmente en los lenguajes de programación funcional .
Repositorio de GitHub que contiene implementaciones de BST persistentes utilizando nodos Fat, copia en escritura y técnicas de 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 con matriz hash persistente es una variante especializada de un trie mapeado con matriz hash que conservará 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 intentos mapeados de matrices hash fueron descritos originalmente en un artículo de 2001 de Phil Bagwell titulado "Ideal Hash Trees". 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, 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 errores cuestan menos que las búsquedas exitosas". [12] Esta estructura de datos fue luego modificada por Rich Hickey para que fuera completamente persistente para su uso en el lenguaje de programación Clojure . [13]
En términos conceptuales, los intentos mapeados en matrices hash funcionan de manera similar a cualquier árbol genérico , ya que almacenan nodos jerárquicamente y los recuperan siguiendo una ruta hacia abajo hasta un elemento en particular. La diferencia clave es que los intentos mapeados en matrices hash primero usan 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 del árbol se determina usando porciones de la representación binaria de ese entero para indexar en una matriz dispersa en cada nivel del árbol. Los nodos de hoja del árbol se comportan de manera similar a los contenedores utilizados para construir tablas hash y pueden o no contener múltiples candidatos dependiendo de las colisiones hash . [11]
La mayoría de las implementaciones de tries mapeados en 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 un trie mapeado en una matriz hash persistente 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 tome más de una docena de pasos. [14]
Haskell es un lenguaje puramente funcional y, por lo tanto, no permite la mutación. Por lo tanto, 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 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]
Al igual que 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 persistentes, mapas y conjuntos 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 recomiendan 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 libremente compartibles 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 evitar carreras de datos y semánticas de comparación e intercambio atómico . [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 de DOM virtual personalizada 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 represente 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 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 completamente persistentes están disponibles en bibliotecas de terceros [26] u otros lenguajes de JVM.
El popular framework de interfaz de JavaScript React se utiliza con frecuencia junto con un sistema de gestión de estados que implementa la arquitectura Flux, [27] [28] una implementación popular de la cual es la biblioteca de JavaScript Redux . La biblioteca Redux está inspirada en el patrón de gestión de estados 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 reforzadas. Según se informa, esto permite un mayor rendimiento que cuando se comparan o hacen copias de objetos JavaScript normales. [30]
Una de estas bibliotecas de estructuras de datos persistentes, Immutable.js, se basa en las estructuras de datos que Clojure y Scala pusieron a disposición y popularizaron. [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 uno "crea el siguiente estado inmutable mutando el actual". [33] Immer.js utiliza objetos nativos de JavaScript 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 Prolog son naturalmente inmutables y, por lo tanto, las estructuras de datos suelen ser persistentes. Su rendimiento depende de la compartición y la recolección de basura que ofrece el sistema Prolog. [34] Las extensiones a términos Prolog no básicos 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 ofrecen operaciones destructivas como setarg/3, que pueden presentarse en diferentes versiones, con o sin copia y con o sin retroceso del cambio de estado. Hay casos en los que se utiliza setarg/3 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 que utilicen el "Estilo Objeto-Funcional". [36] Scala contiene implementaciones de muchas estructuras de datos persistentes, incluidas listas enlazadas, árboles rojo-negros , así como intentos mapeados en matrices hash persistentes, como los introducidos 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 conteo 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 fugas de memoria , en algunos casos puede tener un impacto positivo en el rendimiento general de una aplicación. [40]
{{cite book}}: CS1 maint: varios nombres: lista de autores ( enlace ){{cite journal}}: Requiere citar revista |journal=( ayuda ){{cite journal}}: Requiere citar revista |journal=( ayuda ){{cite journal}}: Requiere citar revista |journal=( ayuda )