Hispanopedia WikiEn informática, una estructura de datos retroactiva es aquella que permite realizar modificaciones eficientes a una secuencia de operaciones realizadas sobre ella. Estas modificaciones pueden consistir en la inserción, eliminación o actualización retroactiva de una operación realizada en algún momento del pasado. [ 1 ]
Algunas aplicaciones de las estructuras de datos retroactivas
En la práctica, existen muchos casos en los que se desea modificar una operación anterior dentro de una secuencia de operaciones. A continuación, se enumeran algunas de las posibles aplicaciones:
- Corrección de errores : Entrada de datos incorrecta. Los datos deben corregirse y deben eliminarse todos los efectos secundarios derivados de los datos incorrectos.
- Datos erróneos : Al trabajar con sistemas grandes, especialmente aquellos que implican una gran cantidad de transferencia automatizada de datos, esto es bastante común. Por ejemplo, supongamos que uno de los sensores de una red meteorológica falla y comienza a reportar datos basura o incorrectos. La solución ideal sería eliminar todos los datos que el sensor produjo desde que falló, junto con todos los efectos que dichos datos erróneos tuvieron en el sistema en general.
- Recuperación : Supongamos que un sensor de hardware se dañó, pero ahora se ha reparado y se pueden leer los datos. Nos gustaría poder reinsertar esos datos en el sistema como si el sensor nunca se hubiera dañado.
- Manipulación del pasado : Cambiar el pasado puede ser útil en los casos de control de daños y las estructuras de datos retroactivas están diseñadas para la manipulación intencional del pasado.
El tiempo como dimensión espacial
No es posible considerar el tiempo como una dimensión espacial adicional. Para ilustrar esto, supongamos que mapeamos la dimensión del tiempo a un eje espacial. La estructura de datos que utilizaremos para agregar la dimensión espacial del tiempo es un min-heap. Sea el eje y el que representa los valores clave de los elementos dentro del heap y el eje x la dimensión espacial del tiempo. Después de varias inserciones y operaciones delete-min (todas realizadas de forma no retroactiva), nuestro min-heap se vería como en la figura 1. Ahora supongamos que insertamos retroactivamente cero al principio de la lista de operaciones. Nuestro min-heap se vería como en la figura 2. Nótese cómo una sola operación produce un efecto en cascada que afecta a toda la estructura de datos. Así, podemos ver que, si bien el tiempo puede representarse como una dimensión espacial, las operaciones que involucran tiempo producen dependencias que tienen un efecto en cadena cuando se realizan modificaciones con respecto al tiempo.
Comparación con la persistencia
A primera vista, la noción de estructuras de datos retroactivas parece muy similar a la de estructuras de datos persistentes, ya que ambas consideran la dimensión del tiempo. La diferencia clave entre las estructuras de datos persistentes y las retroactivas radica en cómo manejan este elemento. Una estructura de datos persistente mantiene varias versiones de una estructura de datos, y se pueden realizar operaciones sobre una versión para producir otra. Dado que cada operación produce una nueva versión, cada versión se convierte en un archivo inmutable (solo se pueden generar nuevas versiones a partir de ella). Como cada versión permanece inmutable, la dependencia entre ellas también lo hace. En las estructuras de datos retroactivas, se permite realizar cambios directamente en versiones anteriores. Dado que cada versión es interdependiente, un solo cambio puede provocar una serie de cambios en todas las versiones posteriores. Las figuras 1 y 2 muestran un ejemplo de este efecto en cadena.
Definición
Cualquier estructura de datos puede reformularse en un contexto retroactivo. En general, la estructura de datos implica una serie de actualizaciones y consultas realizadas durante un período de tiempo. Sea U = [u t 1 , u t 2 , u t 3 , ..., u t m ] la secuencia de operaciones de actualización desde t 1 hasta t m tal que t 1 < t 2 < ... < t m . Aquí se asume que se puede realizar como máximo una operación por cada tiempo t dado.
Parcialmente retroactivo
Definimos una estructura de datos como parcialmente retroactiva si puede realizar operaciones de actualización y consulta en el momento actual y admite operaciones de inserción y eliminación en el pasado. Por lo tanto, para que sea parcialmente retroactiva, nos interesan las siguientes operaciones:
- Insertar(t, u): Inserta una nueva operación u en la lista U en el instante t.
- Delete(t): Elimina la operación en el tiempo t de la lista U.
Dadas las operaciones retroactivas anteriores, una operación de inserción estándar tendría ahora la forma Insert(t, "insertar(x)"). Todos los cambios retroactivos en el historial operativo de la estructura de datos pueden afectar potencialmente a todas las operaciones desde el momento de la operación hasta el presente. Por ejemplo, si tenemos t i-1 < t < t i+1 , entonces Insert(t, insertar(x)) colocaría una nueva operación, op , entre las operaciones op i-1 y op i+1 . El estado actual de la estructura de datos (es decir, la estructura de datos en el momento presente) estaría entonces en un estado tal que las operaciones op i-1 , op y op i+1 ocurrieron en secuencia, como si la operación op siempre hubiera estado presente. Véanse las figuras 1 y 2 para un ejemplo visual.
Totalmente retroactivo
Definimos la estructura de datos como totalmente retroactiva si, además de las operaciones parcialmente retroactivas, también permitimos realizar consultas sobre el pasado. De forma similar a como la operación estándar insert(x) se convierte en Insert(t, "insert(x)") en el modelo parcialmente retroactivo, la operación query(x) en el modelo totalmente retroactivo ahora tiene la forma Query(t, "query(x)").
Tiempos de funcionamiento retroactivos
El tiempo de ejecución de las estructuras de datos retroactivas se basa en el número de operaciones, m , realizadas en la estructura, el número de operaciones r que se realizaron antes de que se realice la operación retroactiva y el número máximo de elementos n en la estructura en un momento dado.
Retroactividad automática
La principal cuestión relativa a la retroactividad automática en estructuras de datos es si existe una técnica general que permita convertir cualquier estructura de datos en una contraparte retroactiva eficiente. Un enfoque sencillo consiste en revertir todos los cambios realizados en la estructura antes de la operación retroactiva que se va a aplicar. Una vez revertida la estructura de datos al estado adecuado, se puede aplicar la operación retroactiva para realizar el cambio deseado. Tras realizar el cambio, es necesario volver a aplicar todos los cambios revertidos previamente para que la estructura de datos alcance su nuevo estado. Si bien esto puede funcionar para cualquier estructura de datos, suele ser ineficiente y generar desperdicios, especialmente cuando el número de cambios que se deben revertir es elevado. Para crear una estructura de datos retroactiva eficiente, es necesario analizar las propiedades de la propia estructura para determinar dónde se pueden lograr mejoras de velocidad. Por lo tanto, no existe una forma general de convertir cualquier estructura de datos en una contraparte retroactiva eficiente. Erik D. Demaine , John Iacono y Stefan Langerman lo demuestran. [ 1 ]
Véase también
Referencias
- 1 2 Demaine, Erik D. ; Iacono, John ; Langerman, Stefan (2007). "Estructuras de datos retroactivas" . ACM Transactions on Algorithms . 3 (2): 13. doi : 10.1145/1240233.1240236 . S2CID 5555302 . Recuperado el 21 de abril de 2012 .
- Estructuras de datos
