¿Qué son las estructuras de datos retroactivas?

Las estructuras de datos retroactivas son un tipo de estructura de datos que admite modificaciones eficientes realizadas en una estructura de datos . En este nuevo paradigma de estructuración de datos, las operaciones realizadas en la estructura de datos no solo están en el presente sino también en el pasado, lo que significa que las operaciones pueden modificarse. y modificado incluso en el intervalo del pasatiempo. 

Estas estructuras de datos nos brindan una gran comodidad en términos de flexibilidad mientras trabajamos en aplicaciones complejas que necesitan actualizaciones periódicas, ya que el ajuste de la estructura se puede ajustar de acuerdo con el modelo de trabajo del programa, en el mundo real hay varios casos en los que es necesario modificar una operación pasada de una secuencia de operaciones.

Necesidad de estructuras de datos retroactivas:

• Para implementar la dinamización: en general, algunos algoritmos que son de naturaleza estática exigen una estructura de datos dinámica para procesar su entrada y la estructura de datos retroactiva puede ser la mejor solución para hacer que estos algoritmos sean dinámicos.
• Para realizar una búsqueda de rango aproximado: las estructuras de datos retroactivas ayudan a implementar operaciones que requieren actualizaciones como insertar y eliminar en cualquier momento y devolver la entrada en un rango de tiempo aproximado t.
• Para evitar la sobrecarga adicional de O(log n): las estructuras de datos retroactivas nos ayudan a evitar la sobrecarga adicional de O(log n) y permiten que las aplicaciones realicen operaciones como crear un árbol de segmento de alto grado sobre segmentos, aumentar la raíz con estructuras de datos tradicionales, aumentar Nodes con estructuras CDFC.
• Alteración de la secuencia histórica de transacciones: las estructuras de datos retroactivas hacen que las aplicaciones se adapten de manera eficiente a condiciones tales como deshacer errores que se cometieron anteriormente sin tener que rehacer todo el trabajo desde entonces.

Comparación con estructuras de datos persistentes:

Aunque la noción de estructuras de datos persistentes y estructuras de datos retroactivas puede parecer similar, ya que tienen en cuenta la dimensión del tiempo, la forma en que manejan el elemento de tiempo las hace diferentes entre sí. 

• Una estructura de datos persistente mantiene varias versiones de estructuras de datos y la operación se puede implementar en una versión de datos para crear otra versión.
• En el caso de estructuras de datos retroactivas, los cambios se realizan directamente a las versiones anteriores y no se crean otras versiones anteriores modificadas que hayan estado sujetas a cambios de datos en el pasado.

Tipos de retroactividad:

1. Parcialmente retroactivo: cualquier estructura de datos puede volverse parcialmente retroactiva mediante transformaciones generales. Por ejemplo, lo siguiente inserta una lista parcialmente retroactiva con un estado inicial [1,2,3,4,5]. Luego podemos agregar o eliminar la operación en presente.

A continuación se muestra el pseudocódigo de Python para el concepto anterior:

# Python program to implement  
# the above approach  
x = PartiallyRetroactive([1, 2, 3, 4, 5])  
def appendOne(lst):
 return lst + [1]

# Three appendOnes by applying  
# insertAgo()
x.insertAgo(appendOne, tminus = 0)
x.insertAgo(appendOne, tminus = 0)
x.insertAgo(appendOne, tminus = 0)
x.query()

# Three appendOnes by applying insertAgo()
[1, 2, 3, 4, 5, 1, 1, 1]   

Producción:

>>x.query() :
[1, 2, 3, 4, 5, 1, 1, 1]

También podemos añadir o quitar operaciones del pasado:

def MethodForAppendNum(lst):
       return lst + [6]
       
 ## For Inserting into  *two* operations ago
 a.insertAgo(appendSix, tminus=2)   
 a.query()
 [1, 2, 3, 4, 5, 1, 6, 1, 1]
 
 ## For Deleting the first appendOne
 a.deleteAgo(tminus=3)   
 a.query()
 [1, 2, 3, 4, 5, 6, 1, 1]

Producción:

>>a.query() :
[1, 2, 3, 4, 5, 1, 6, 1, 1]

2. Retroactividad Total General: Las estructuras de datos Retroactivas Totales son similares a sus hermanas las Estructuras de Datos Retroactivas Parciales, en el sentido de que permiten la inserción y eliminación retroactiva de operaciones. Sin embargo, las estructuras de datos totalmente retroactivas también permiten consultar el pasado en lugar de solo el presente.

A continuación se muestra el pseudocódigo de Python para el enfoque anterior:

b = MethodForFullyRetroactive([1,2,3])
b.insertAgo(appendOne, tminus = 0)
 
## This one should come last
b.insertAgo(appendSix, tminus = 0) 

## This one should come first
b.insertAgo(appendTen, tminus =2)
 
b.query()

## The current state of the data structure
[1, 2, 3, 10, 1, 6]   
b.query(1)
[1, 2, 3, 10, 1]
b.query(2)
[1, 2, 3, 10]
b.query(3)

## The state of the data structure way back
## in the past
[1, 2, 3]   

Producción:

>>b.query(1) :
[1, 2, 3, 10, 1, 6]
>>b.query(2) :
[1, 2, 3, 10]
>>b.query(3) :
[1, 2, 3]

Aplicaciones: A continuación se enumeran algunas aplicaciones de estructuras de datos retroactivas.

• Recuperación: si tenemos un chip de hardware que se dañó y se perdieron los datos, pero ahora se reparó, y podemos leer los datos del sensor, y queremos que los datos se vuelvan a insertar en el sistema como si el hardware fuera nunca dañado.
• Corrección de errores: en caso de ingreso incorrecto de datos, los datos deben corregirse y los efectos secundarios del ingreso incorrecto deben eliminarse.
• Manipulación de datos en intervalos de pasatiempos: la modificación de datos en pasatiempos puede ayudar a prevenir el control de daños en los casos en que se hayan inyectado datos falsos debido a un error del sistema o un error manual.
• Datos incorrectos: cuando se trata de ingresar datos en un sistema grande, particularmente en sistemas como sensores en mal funcionamiento de la red meteorológica que requieren grandes cantidades de transferencia de datos automatizada, la basura y los datos incorrectos pueden causar un gran daño a las aplicaciones, la solución ideal será eliminar los datos incorrectos. en operaciones pasadas mediante el uso de estructuras de datos retroactivas para crear un escenario como si nunca se hubieran producido datos incorrectos.

Ventajas de las estructuras de datos retroactivas:

• Nos brinda flexibilidad para corregir actualizaciones basadas en el tiempo sin el uso de operaciones de reversión rentables cada vez que ocurre un bloqueo de datos.
• Estas estructuras de datos se pueden aplicar de manera más efectiva para buscar problemas, como mantener el conjunto k de algunos objetos desconocidos que están sujetos a operaciones como insertar, eliminar y consultar (x, s), ya que aquí podemos tener el privilegio de modificar la estructura de datos por retrocediendo de nuevo en la secuencia de tiempo y recuperando nuestra consulta deseada.
• Estas estructuras de datos nos ayudan a resolver problemas de búsqueda descompuestos, como realizar consultas de la forma consulta (x, AuB) = f (consulta (x, A), consulta (x, B)) que se ejecuta en tiempo O (1).
• Ayudan a dinamizar Algoritmos estáticos de manera efectiva.

Desventajas de las estructuras de datos retroactivas:

• Estas estructuras de datos exigen grandes recursos informáticos y de almacenamiento, ya que se ejecutan en tiempos polinómicos más altos.
• Estas estructuras de datos funcionan bien en aplicaciones complejas que prosperan únicamente con actualizaciones basadas en el tiempo sin objetivos basados ​​en el orden adecuado, pero no se recomiendan en aplicaciones simples y escalables que generan actualizaciones oportunas basadas en reglas estrictas como el Sistema de gestión de asistencia de empleados, el generador de contraseñas de un solo uso porque implementando esta estructura de datos puede crear errores para cambiar y modificar la información.
• Implica altos costos de mantenimiento debido a la ejecución de altas transformaciones polinómicas.
• Si las aplicaciones implementadas con estructuras de datos retroactivas no se cubrieron con estándares de algoritmos de encriptación efectivos, existe una gran posibilidad de manipulación intencional de datos que ni siquiera se puede rastrear ya que no habrá registros de tiempo disponibles.

Retroactividad automática: surge una duda natural en nuestras mentes sobre la posibilidad de convertir estructuras de datos automáticamente en forma retroactiva mediante el uso de una técnica general, por ejemplo, como convertir un modelo de máquina de puntero en una estructura de datos parcialmente retroactiva efectiva. Una técnica general de este tipo complementaría muy bien las estructuras de datos de persistencia existentes, pero en el caso de las estructuras de datos retroactivas, la retroactividad es fundamentalmente diferente de la persistencia, y las técnicas generalmente conocidas no se aplican.

Un enfoque simple para este problema general es el método de reversión, donde la información auxiliar se almacena a medida que cada operación realiza todos los cambios en las estructuras de datos de tal manera que cada cambio podría revertirse dinámicamente, por ejemplo, para permitir una reversión de la memoria. -En la operación de escritura almacenamos el valor que estaba previamente en la dirección, por lo tanto sus actuaciones actúan de forma diferente dependiendo del cambio retroactivo.

Tiempos de ejecución retroactivos: tome una serie de operaciones realizadas por la estructura de datos para determinar el tiempo de ejecución de las estructuras de datos retroactivos. Por ejemplo, sea m el número de operaciones realizadas sobre la estructura y sea r el número de operaciones realizadas antes de las operaciones retroactivas, y sea n el número máximo de elementos presentes en la estructura en cualquier momento.