Matriz persistente

En informática , y más concretamente en lo que respecta a las estructuras de datos , un array persistente es una estructura de datos persistente con propiedades similares a las de un array (no persistente) . Es decir, tras la actualización de un valor en un array persistente, existen dos arrays persistentes: uno que incorpora la actualización y otro que es igual al array anterior a la actualización.

Diferencia entre arreglos persistentes y arreglos

Una matriz $\mathrm {ar} =[e_{0},\dots,e_{n-1}]$ es una estructura de datos, con un número fijo n de elementos. $e_{0},\dots,e_{n-1}$ Se espera que, dado el array ar y un índice $0\leq i<n$ , el valor $e_{i}$ se puede recuperar rápidamente. Esta operación se llama búsqueda . Además, dado el array ar , un índice $0\leq i<n$ y un nuevo valor v , un nuevo array ar2 con contenido $[e_{0},\dots,e_{i-1},v,e_{i+1},\dots,e_{n-1}]$ se puede crear rápidamente. Esta operación se llama actualización . La principal diferencia entre los arreglos persistentes y no persistentes es que, en los arreglos no persistentes, el arreglo ar se destruye durante la creación de ar2 .

Por ejemplo, considere el siguiente pseudocódigo .

array = [0, 0, 0] updated_array = array.update (0, 8) other_array = array.update (1, 3) last_array = updated_array.update (2, 5)

Al final de la ejecución, el valor de array sigue siendo [0, 0, 0], el valor de updated_array es [8, 0, 0], el valor de other_array es [0, 3, 0] y el valor de last_array es [8, 0, 5].

Existen dos tipos de arreglos persistentes. Un arreglo persistente puede ser parcial o totalmente persistente. Un arreglo totalmente persistente puede actualizarse un número arbitrario de veces, mientras que un arreglo parcialmente persistente puede actualizarse como máximo una vez. En nuestro ejemplo anterior, si el arreglo fuera solo parcialmente persistente, la creación de other_array estaría prohibida; sin embargo, la creación de last_array seguiría siendo válida. De hecho, updated_array es un arreglo distinto de array y nunca se ha actualizado antes de la creación de last_array .

Límite inferior del tiempo de búsqueda en matrices persistentes

Dado que los arreglos no persistentes admiten actualizaciones y búsquedas en tiempo constante, es natural preguntarse si lo mismo es posible con los arreglos persistentes. El siguiente teorema muestra que, bajo supuestos leves sobre la complejidad espacial del arreglo, las búsquedas deben tomar $\Omega (\log \log n)$ tiempo en el peor de los casos, independientemente del tiempo de actualización, en el modelo de sonda celular .

Teorema ^{[ 1 ]}^{: 67–69} — Considere una matriz parcialmente persistente con $n$ elementos y $m=n^{\gamma }$ modificaciones, donde $\gamma$ es una satisfacción constante $1<\gamma \leq 2$ Suponiendo que la complejidad espacial del arreglo es $O(m\log ^{k}m)$ por una constante $k$ , el límite inferior de la complejidad de búsqueda en este arreglo parcialmente persistente es $\Omega (\log \log n)$ .

Implementaciones

En esta sección, $n$ es el número de elementos del arreglo, y $m$ es el número de actualizaciones.

Tiempo de registro en el peor de los casos

La implementación más sencilla de un array totalmente persistente utiliza un mapa persistente arbitrario, cuyas claves son los números del 0 al n − 1. Un mapa persistente puede implementarse utilizando un árbol equilibrado persistente , en cuyo caso tanto las actualizaciones como las búsquedas tomarían $O(\log n)$ tiempo. Esta implementación es óptima para el modelo de máquina de punteros . ^{[ 1 ]}^{: 88–89}

Encuadernación superficial

Se puede implementar un array totalmente persistente utilizando un array y el llamado truco del panadero. ^{[ 2 ]} Esta implementación se utiliza en el módulo OCaml parray.ml ^{[ 3 ]} de Jean-Christophe Filliâtre.

Para definir esta implementación, se deben dar algunas otras definiciones. Un array inicial es un array que no se genera mediante una actualización de otro array. Un hijo de un array ar es un array de la forma ar.update(i,v) , y ar es el padre de ar.update(i,v) . Un descendiente de un array ar es ar o el descendiente de un hijo de ar . El array inicial de un array ar es ar si ar es inicial, o es el array inicial del padre de ar . Es decir, el array inicial de ar es el único array init tal que $\mathrm {ar} =init.update(i_{0},v_{0}).\dots .update(i_{m},v_{m})$ , con inicialización inicial y $i_{0},\dots ,i_{m}$ una secuencia arbitraria de índices y $v_{0},\dots,v_{m}$ una secuencia arbitraria de valores. Una familia de arreglos es, por lo tanto, un conjunto de arreglos que contiene un arreglo inicial y todos sus descendientes. Finalmente, el árbol de una familia de arreglos es el árbol cuyos nodos son los arreglos, y con una arista e desde ar a cada uno de sus hijos ar.update(i,v) .

Un arreglo persistente que utiliza el truco de Baker consiste en un par formado por un arreglo real llamado arreglo y el árbol de arreglos. Este árbol admite una raíz arbitraria, no necesariamente el arreglo inicial. La raíz puede moverse a un nodo arbitrario del árbol. Cambiar la raíz de raíz a un nodo arbitrario ar toma un tiempo proporcional a la profundidad de ar . Es decir, en la distancia entre raíz y ar . De manera similar, buscar un valor toma un tiempo proporcional a la distancia entre el arreglo y la raíz de su familia. Por lo tanto, si el mismo arreglo ar puede buscarse varias veces, es más eficiente mover la raíz a ar antes de realizar la búsqueda. Finalmente, actualizar un arreglo solo toma un tiempo constante .

Técnicamente, dados dos arreglos adyacentes ar1 y ar2 , con ar1 más cerca de la raíz que ar2 , el borde de ar1 a ar2 se etiqueta por (i,ar2[i]) , donde i es la única posición cuyo valor difiere entre ar1 y ar2 .

El acceso a un elemento i de un arreglo ar se realiza de la siguiente manera: Si ar es la raíz, entonces ar[i] es igual a root[i] . En caso contrario, sea e la arista que sale de ar hacia la raíz. Si la etiqueta de e es (i,v) , entonces ar[i] es igual a v . En caso contrario, sea ar2 el otro nodo de la arista e . Entonces ar[i] es igual a ar2[i] . El cálculo de ar2[i] se realiza recursivamente utilizando la misma definición.

La creación de ar.update(i,v) consiste en agregar un nuevo nodo ar2 al árbol y una arista e de ar a ar2 etiquetada por (i,v) .

Finalmente, mover la raíz a un nodo ar se hace de la siguiente manera. Si ar ya es la raíz, no hay nada que hacer. De lo contrario, sea e la arista que sale de ar hacia la raíz actual, (i,v) su etiqueta y ar2 el otro extremo de e . Mover la raíz a ar se hace moviendo primero la raíz a ar2 , cambiando la etiqueta de e a (i, ar2[i]) y cambiando array[i] a v .

Las actualizaciones tardan $O(1)$ tiempo. Las búsquedas toman $O(1)$ tiempo si la raíz es el array que se está buscando, pero $\Theta (m)$ tiempo en el peor de los casos.

Tiempo logarítmico amortizado esperado

En 1989, Dietz ^{[ 4 ]} dio una implementación de arreglos totalmente persistentes utilizando $O(m+n)$ espacio tal que se puedan realizar búsquedas en $O(\log \log m)$ en el peor de los casos, las actualizaciones se pueden realizar en $O(\log \log m)$ tiempo amortizado esperado . Según el límite inferior de la sección anterior, esta complejidad temporal para la búsqueda es óptima cuando $m=n^{\gamma }$ para $\gamma \en (1,2]$ Esta implementación está relacionada con el problema del mantenimiento del orden e involucra árboles vEB , uno para todo el arreglo y uno para cada índice.

Straka demostró que los tiempos para ambas operaciones pueden mejorarse (ligeramente) $O(\log \log \min(m,n))$ . ^{[ 1 ]}^{: 88–89}

peor caso registro-registro-tiempo

Straka mostró cómo lograrlo $O((\log \log m)^{2}/\log \log \log m)$ tiempo en el peor de los casos y lineal ( $O(m+n)$ ) espacio, o $O(\log \log m)$ tiempo del peor caso y espacio superlineal. Queda por ver si es posible lograr el tiempo del peor caso. $O(\log \log m)$ sujeto a espacio lineal. ^{[ 1 ]}^{: 88}

Referencias

1 2 3 4 Straka e, Milán (2013). Estructuras de datos funcionales y algoritmos . Praga.{{cite book}}: CS1 mantenimiento: falta el editor de ubicación ( enlace )
↑ Fillâtre, Jean-Christophe; Conchon, Sylvain (2007). Una estructura de datos persistente de unión-búsqueda (PDF) . Nueva York, NY, EE. UU.: ACM. págs. 37–46 . ISBN 978-1-59593-676-9.
↑ Filliâtre, Jean-Christophe. "Implementación de arreglo persistente" . GitHub .
↑ Dietz, Paul F. (1989). "Arreglos totalmente persistentes". Actas de Algoritmos y Estructuras de Datos . págs. 67–74 . CiteSeerX 10.1.1.621.1599 . doi : 10.1007/3-540-51542-9_8 .

[Straka-1] 1 2 3 4 Straka e, Milán (2013). Estructuras de datos funcionales y algoritmos . Praga.{{cite book}}: CS1 mantenimiento: falta el editor de ubicación ( enlace )

[ML-2] Fillâtre, Jean-Christophe; Conchon, Sylvain (2007). Una estructura de datos persistente de unión-búsqueda (PDF) . Nueva York, NY, EE. UU.: ACM. págs. 37–46 . ISBN 978-1-59593-676-9.

[3] Filliâtre, Jean-Christophe. "Implementación de arreglo persistente" . GitHub .

[Dietz-4] Dietz, Paul F. (1989). "Arreglos totalmente persistentes". Actas de Algoritmos y Estructuras de Datos . págs. 67–74 . CiteSeerX 10.1.1.621.1599 . doi : 10.1007/3-540-51542-9_8 .

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]