Retroaktiv datastruktur
Inom datavetenskap är en retroaktiv datastruktur en datastruktur som stöder effektiva modifieringar av en sekvens av operationer som har utförts på strukturen. Dessa ändringar kan ta formen av retroaktiv infogning, radering eller uppdatering av en operation som utfördes någon gång i det förflutna.
Vissa tillämpningar av retroaktiva datastrukturer
I den verkliga världen finns det många fall där man skulle vilja modifiera en tidigare operation från en sekvens av operationer. Nedan listas några av de möjliga tillämpningarna:
- Felkorrigering : Felaktig inmatning av data. Uppgifterna bör korrigeras och alla sekundära effekter av felaktiga uppgifter tas bort.
- Dålig data : När man har att göra med stora system, särskilt de som involverar en stor mängd automatiserad dataöverföring, är det inte ovanligt. Anta till exempel att en av sensorerna för ett vädernätverk inte fungerar och börjar rapportera skräpdata eller felaktig data. Den idealiska lösningen skulle vara att ta bort all data som sensorn producerade eftersom den inte fungerade tillsammans med alla effekter som de dåliga data hade på det övergripande systemet.
- Återställning : Antag att en hårdvarusensor var skadad men nu är reparerad och data kan läsas från sensorn. Vi skulle vilja kunna infoga data tillbaka i systemet som om sensorn aldrig hade skadats i första hand.
- Manipulation av det förflutna : Att förändra det förflutna kan vara till hjälp i fall av skadekontroll och retroaktiva datastrukturer är utformade för avsiktlig manipulation av det förflutna.
Tid som rumslig dimension
Det är inte möjligt att betrakta tid som en ytterligare rumslig dimension. För att illustrera detta antar vi att vi kartlägger tidsdimensionen på en rymdaxel. Datastrukturen vi kommer att använda för att lägga till den rumsliga tidsdimensionen är en min-hög. Låt y-axeln representera nyckelvärdena för objekten i högen och x-axeln är den rumsliga tidsdimensionen. Efter flera insättningar och delete-min-operationer (alla gjorda icke-retroaktivt) skulle vår min-hög se ut som i figur 1. Anta nu att vi retroaktivt infogar noll i början av operationslistan. Vår min-hög skulle se ut som i figur 2. Lägg märke till hur den enda operationen producerar en kaskadeffekt som påverkar hela datastrukturen. Således kan vi se att medan tid kan ritas som en rumslig dimension, producerar operationer med tid inblandad beroende som har en krusning när modifieringar görs med avseende på tid.
Jämförelse med uthållighet
Vid första anblicken verkar begreppet retroaktiva datastrukturer mycket likna beständiga datastrukturer eftersom de båda tar hänsyn till tidsdimensionen. Den viktigaste skillnaden mellan beständiga datastrukturer och retroaktiva datastrukturer är hur de hanterar tidselementet. En beständig datastruktur upprätthåller flera versioner av en datastruktur och operationer kan utföras på en version för att producera en annan version av datastrukturen. Eftersom varje operation producerar en ny version blir varje version alltså ett arkiv som inte kan ändras (endast nya versioner kan skapas från det). Eftersom varje version inte ändras ändras inte heller beroendet mellan varje version. I retroaktiva datastrukturer tillåter vi att ändringar görs direkt till tidigare versioner. Eftersom varje version nu är beroende av varandra, kan en enda ändring orsaka en krusning av ändringar av alla senare versioner. Figurerna 1 och 2 visar ett exempel på denna porlande effekt.
Definition
Vilken datastruktur som helst kan omformuleras i en retroaktiv miljö. I allmänhet innefattar datastrukturen en serie uppdateringar och frågor som görs under en viss tidsperiod. Låt U = [u t 1 , u t 2 , u t 3 , ..., u t m ] vara sekvensen av uppdateringsoperationer från t 1 till t m så att t 1 < t 2 < ... < t m . Antagandet här är att högst en operation kan utföras under en given tid t.
Delvis retroaktivt
Vi definierar datastrukturen till att vara delvis retroaktiv om den kan utföra uppdaterings- och frågeoperationer vid den aktuella tidpunkten och stödja insättnings- och raderingsoperationer i det förflutna. För delvis retroaktiv verkan är vi därför intresserade av följande operationer:
- Infoga(t, u): Infoga en ny operation u i listan U vid tidpunkten t.
- Ta bort(t): Ta bort operationen vid tidpunkten t från listan U.
Med tanke på ovanstående retroaktiva operationer skulle en standardinsättningsoperation nu vara i form av Insert(t, "insert(x)"). Alla retroaktiva förändringar av datastrukturens verksamhetshistorik kan potentiellt påverka all verksamhet vid tidpunkten för operationen fram till idag. Till exempel, om vi har t i-1 < t < t i+1 , då skulle Insert(t, insert(x)) placera en ny operation, op , mellan operationerna op i-1 och op i+1 . Det aktuella tillståndet för datastrukturen (dvs: datastrukturen för närvarande) skulle då vara i ett tillstånd så att operationerna op i-1 , op och op i+1 alla skedde i en sekvens, som om operationen op var alltid där. Se figur 1 och 2 för ett visuellt exempel.
Fullt retroaktivt
Vi definierar datastrukturen till att vara helt retroaktiv om vi utöver de delvis retroaktiva operationerna även tillåter en att utföra frågor om det förflutna. I likhet med hur standardoperationen insert(x) blir Insert(t, "insert(x)") i den delvis retroaktiva modellen, har operationsfrågan(x) i den helt retroaktiva modellen nu formen Query(t, "query( x)").
Retroaktiva körtider
Körtiden för retroaktiva datastrukturer baseras på antalet operationer, m , utförda på strukturen, antalet operationer r som utfördes innan den retroaktiva operationen utfördes och det maximala antalet element n i strukturen vid varje enskild tid.
Automatisk retroaktivitet
Huvudfrågan angående automatisk retroaktivitet med avseende på datastrukturer är om det finns en generell teknik som kan omvandla vilken datastruktur som helst till en effektiv retroaktiv motsvarighet. Ett enkelt tillvägagångssätt är att göra en återställning av alla ändringar som gjorts i strukturen innan den retroaktiva åtgärden som ska tillämpas. När vi väl har återställt datastrukturen till lämpligt tillstånd kan vi sedan tillämpa den retroaktiva operationen för att göra den ändring vi önskade. När ändringen väl är gjord måste vi återigen tillämpa alla ändringar som vi rullade tillbaka tidigare för att sätta datastrukturen i sitt nya tillstånd. Även om detta kan fungera för vilken datastruktur som helst, är det ofta ineffektivt och slösaktigt, särskilt när antalet ändringar som vi behöver återställa är stort. För att skapa en effektiv retroaktiv datastruktur måste vi ta en titt på egenskaperna hos själva strukturen för att avgöra var hastighetshöjningar kan realiseras. Det finns alltså inget allmänt sätt att omvandla någon datastruktur till en effektiv retroaktiv motsvarighet. Erik D. Demaine , John Iacono och Stefan Langerman bevisar detta.