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

19

Las estructuras de datos persistentes son estructuras de datos inmutables. Las operaciones en ellos devuelven una nueva "copia" de la estructura de datos, pero modificada por la operación; Sin embargo, la antigua estructura de datos permanece sin cambios. La eficiencia generalmente se logra compartiendo algunos de los datos subyacentes y evitando la copia completa de la estructura de datos.

Preguntas:

  • ¿Hay resultados sobre clases de estructuras de datos que pueden hacerse persistentes (manteniendo las mismas o muy similares complejidades)?

  • ¿Se pueden hacer persistentes todas las estructuras de datos (manteniendo las mismas o muy similares complejidades)?

  • ¿Se sabe que algunas estructuras de datos no pueden hacerse persistentes (manteniendo las mismas o muy similares complejidades)?

Ensalada Realz
fuente
1
No puede hacer que un vector sea persistente con complejidad O (1) preservada para acceder a un elemento aleatorio.
smossen
2
@smossen, ¿puedes probar eso?
Realz Slaw
1
Su primera pregunta es una pregunta muy amplia. Hay muchos resultados sobre el tema de las estructuras de datos que pueden hacerse persistentes. Se podría escribir un libro completo sobre el tema, y ​​algunas personas lo han hecho: por ejemplo, el libro de Okasaki es un clásico sobre el tema. ¿Has hecho alguna investigación sobre este tema? ¿Puedes reducir la pregunta? Tal como está, sospecho que podría ser demasiado amplio para ser un buen ajuste para este sitio. ¿Quizás dividir la tercera pregunta en una pregunta separada?
DW
@Realz Slaw: No puedo probarlo formalmente, pero creo que es de sentido común. O (1) el acceso a elementos en vectores (incluidas las tablas hash) depende del tiempo fijo para la decodificación de direcciones en un hardware determinado. La persistencia agrega una o dos dimensiones además del índice vectorial. Pero las direcciones de hardware siguen siendo unidimensionales.
smossen

Respuestas:

22

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(lgn)

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 esO ( lg n ) O ( 1 ) O ( f ( n ) ) n n O ( lg n ) O ( f ( n ) lg n )O(lgn)O(lgn)O(1)O(f(n))nnO(lgn)O(f(n)lgn) .

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(lglgn)


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:O ( 1 ) O ( 1 ) Ω ( lg lg n )nO(1)O(1)Ω(lglgn)

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(lgn)

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 .d ddd

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.O ( lg n ) O ( lg n ) O ( lg n )nO(lgn)O(lgn)O(lgn)

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

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.
DW
44
Buena respuesta, DW. Puede reducir el tiempo a (esperado amortizado) . Vea "O(lglgn)
Pruebas