¿Qué clases de estructuras de datos pueden hacerse persistentes?

Resultado positivo: la persistencia no cuesta demasiado. Se puede demostrar que cada estructura de datos puede hacerse completamente persistente con a lo sumo una desaceleración de . $O(\lg n)$

Prueba: puede tomar una matriz y hacerla persistente utilizando estructuras de datos estándar (por ejemplo, un árbol binario equilibrado; vea el final de esta respuesta para obtener un poco más de detalle). Esto incurre en una desaceleración de : cada acceso a la matriz toma tiempo con la estructura de datos persistentes, en lugar de tiempo para la matriz no persistente. Ahora tome cualquier algoritmo imperativo cuyo tiempo de ejecución en el modelo RAM sea , donde denota la cantidad de memoria utilizada. Representa toda la memoria como una gran matriz (con elementos) y haz que sea persistente usando un mapa persistente. Cada paso del algoritmo imperativo incurre como máximo en una desaceleración , por lo que el tiempo total de ejecución es $O(\lg n)$ $O(\lg n)$ $O(1)$ $O(f(n))$ $n$ $n$ $O(\lg n)$ $O(f(n) \lg n)$ .

Aparentemente es posible hacerlo un poco mejor: aparentemente uno puede reducir el factor de desaceleración a (tiempo esperado, amortizado), usando las técnicas en el documento de Demaine que se cita a continuación, pero no estoy familiarizado con los detalles de ese trabajo, así que no puedo responder por esto yo mismo. Gracias a jbapple por esta observación. $O(\lg \lg n)$

Resultado negativo: no puede evitar cierta desaceleración, para algunas estructuras de datos. Para responder a su tercera pregunta, existen estructuras de datos donde se sabe que hacerlas persistentes introduce cierta desaceleración.

En particular, considere una matriz de elementos. Sin persistencia, cada acceso a la matriz tarda tiempo (en el modelo RAM). Con persistencia, aparentemente se ha demostrado que no hay forma de construir una matriz persistente con peor de los casos para acceder a un elemento aleatorio. En particular, aparentemente hay un límite inferior que muestra que las matrices completamente persistentes deben tener tiempo de acceso . Este límite inferior se afirma en la p.3 del siguiente documento: $n$ $O(1)$ $O(1)$ $\Omega(\lg \lg n)$

Intentos persistentes con confianza para un control de versiones eficiente . Erik D. Demaine, Stefan Langerman, Eric Price. Algorithmica, volumen 57, número 3, 2010, páginas 462–483.

El límite inferior se atribuye a Mihai Patrascu, pero no hay ninguna cita a una fuente que proporcione los detalles de la prueba de este límite inferior afirmado.

Una rica área de investigación. Si tomamos una estructura de datos arbitraria o un algoritmo, es una pregunta delicada si puede hacer que sea persistente con desaceleración de como máximo o no. No conozco ningún teorema de clasificación general. Sin embargo, hay mucha investigación sobre formas de hacer que las estructuras de datos específicas sean persistentes, de manera eficiente. $O(1)$

También hay una fuerte conexión con lenguajes de programación funcionales. En particular, cada estructura de datos que se puede implementar de una manera puramente funcional (sin mutaciones) ya es una estructura de datos persistente. (Lo contrario no es necesariamente el caso, por desgracia). Si desea entrecerrar los ojos, podría tomar esto como una especie de teorema de clasificación parcial débil: si es implementable en un lenguaje de programación puramente funcional con los mismos límites de tiempo que en un lenguaje imperativo, entonces hay una estructura de datos persistente con los mismos límites de tiempo que el no persistente. Me doy cuenta de que probablemente esto no sea lo que estabas buscando, es sobre todo una reformulación trivial de la situación.

Cómo hacer una matriz persistente. No trataré de describir la construcción de cómo construir una matriz completamente persistente con peor tiempo de acceso. Sin embargo, las ideas básicas no son demasiado complicadas, así que resumiré la esencia de las ideas. $O(\lg n)$

La idea básica es que podemos tomar cualquier estructura de datos de árbol binario y hacerla persistente usando una técnica llamada copia de ruta . Digamos que tenemos un árbol binario y queremos modificar el valor en algún leaf . Sin embargo, por persistencia, no nos atrevemos a modificar el valor en esa hoja en su lugar. En cambio, hacemos una copia de esa hoja y modificamos el valor en la copia. Luego, hacemos una copia de su elemento primario y cambiamos el puntero secundario apropiado en la copia para que apunte a la nueva hoja. Continúe de esta manera, clonando cada nodo en el camino desde la raíz hasta la hoja. Si queremos modificar una hoja a profundidad , esto requiere copiar nodos . $\ell$ $d$ $d$

Si tenemos un árbol binario balanceado que tiene nodos, entonces todas las hojas tienen profundidad , por lo que esta operación en el árbol binario toma tiempo . Hay algunos detalles que estoy omitiendo: para lograr peor de los casos, es posible que necesitemos reequilibrar el árbol para asegurarnos de que se mantenga equilibrado, pero esto da una idea general. $n$ $O(\lg n)$ $O(\lg n)$ $O(\lg n)$

Puede encontrar más explicaciones, con bonitas imágenes, en los siguientes recursos:

Lea las secciones etiquetadas "Árboles de búsqueda binaria" y "Estructuras de acceso aleatorio" (específicamente, el método del árbol) en http://toves.org/books/persist/index.html .
O lea http://netcode.ru/dotnet/?artID=6592#BinaryTrees y algunas de las secciones posteriores.
O lea las secciones etiquetadas "Estructuras de datos funcionales" y "Copia de ruta" (comenzando en la página 4) del documento de Demaine citado anteriormente: http://erikdemaine.org/papers/ConfluentTries_Algorithmica/paper.pdf

Eso te dará la idea principal. Hay detalles adicionales para cuidar, pero los detalles están fuera del alcance de esta pregunta. Afortunadamente, todo esto es algo estándar, y hay mucha información disponible en la literatura sobre cómo construir tales estructuras de datos. Siéntase libre de hacer una pregunta por separado si los recursos anteriores no son suficientes y desea obtener más información sobre los detalles de la construcción de una estructura de datos de matriz persistente.

DW
fuente

Realmente no entiendo el primer párrafo, ¿cómo haría para que una matriz sea persistente usando un árbol rojo-negro?

G. Bach

@ G.Bach, hay una muy buena explicación en las secciones etiquetadas "Árboles de búsqueda binaria" y "Estructuras de acceso aleatorio" (específicamente, el método del árbol) en toves.org/books/persist/index.html . Para otra buena descripción, vea netcode.ru/dotnet/?artID=6592#BinaryTrees y algunas de las secciones posteriores. Eso te dará la idea principal. Los detalles están fuera del alcance de esta pregunta, pero todo esto es material estándar; Le recomiendo que haga una pregunta por separado si desea obtener más información sobre cómo construir una estructura de datos de este tipo.

Buena respuesta, DW. Puede reducir el tiempo a (esperado amortizado) . Vea "

O (\lg \lg n)

$O(\lg \lg n)$

Pruebas

¿Qué clases de estructuras de datos pueden hacerse persistentes?

Respuestas: