Retroaktivní datová struktura - Retroactive data structure

v počítačová věda A zpětná datová struktura je datová struktura který podporuje efektivní úpravy sledu operací, které byly na struktuře provedeny. Tyto úpravy mohou mít formu zpětného vložení, smazání nebo aktualizace operace, která byla provedena někdy v minulosti.[1]

Některé aplikace retroaktivních datových struktur

V reálném světě existuje mnoho případů, kdy by někdo chtěl upravit minulou operaci ze sledu operací. Níže jsou uvedeny některé z možných aplikací:

  • Oprava chyb: Nesprávné zadání dat. Údaje by měly být opraveny a odstraněny všechny vedlejší účinky nesprávných údajů.
  • Špatná data: Pokud jde o velké systémy, zejména ty, které zahrnují velké množství automatizovaného přenosu dat, není to neobvyklé. Předpokládejme například, že jeden ze senzorů nefunguje správně v meteorologické síti a začne hlásit nesmyslná data nebo nesprávná data. Ideálním řešením by bylo odstranit všechna data, která senzor vyprodukoval, protože selhal spolu se všemi efekty, které měla špatná data na celý systém.
  • Zotavení: Předpokládejme, že hardwarový senzor byl poškozen, ale je nyní opraven a ze senzoru lze číst data. Chtěli bychom mít možnost vložit data zpět do systému, jako by senzor vůbec nebyl nikdy poškozen.
  • Manipulace s minulostí: Změna minulosti může být užitečná v případech kontroly poškození a retroaktivní datové struktury jsou navrženy pro úmyslnou manipulaci s minulostí.

Čas jako prostorová dimenze

Není možné považovat čas za další prostorovou dimenzi. Pro ilustraci předpokládejme, že mapujeme dimenzi času na osu prostoru. Datová struktura, kterou použijeme k přidání prostorové časové dimenze, je halda min. Nechte osu y představovat klíčové hodnoty položek v haldě a osa x je prostorová časová dimenze. Po několika operacích vložení a odstranění min (vše provedeno bez zpětné účinnosti) by se naše min halda objevila jako na obrázku 1. Předpokládejme, že zpětně vložíme nulu na začátek seznamu operací. Naše min halda by vypadala jako na obrázku 2. Všimněte si, jak jediná operace vytváří kaskádový efekt, který ovlivňuje celou datovou strukturu. Můžeme tedy vidět, že zatímco čas lze nakreslit jako prostorovou dimenzi, operace s časem zahrnují závislost, která má zvlnění, když se provádějí úpravy s ohledem na čas.

Obrázek 1. Min. Hromada s časovou osou.
Obrázek 2. Min. Hromada a časová osa po zpětném provozu.

Srovnání s perzistencí

Na první pohled se pojem retroaktivní datové struktury jeví velmi podobný trvalé datové struktury protože oba berou v úvahu rozměr času. Klíčový rozdíl mezi perzistentními datovými strukturami a retroaktivními datovými strukturami je jak zvládají prvek času. Trvalá datová struktura udržuje několik verzí datové struktury a lze v jedné verzi provádět operace, které vytvářejí další verzi datové struktury. Protože každá operace vytváří novou verzi, každá verze se tak stává archivem, který nelze změnit (lze z něj vytvořit pouze nové verze). Protože se každá verze nemění, nemění se ani závislost mezi každou verzí. V retroaktivních datových strukturách umožňujeme provádět změny přímo v předchozích verzích. Vzhledem k tomu, že každá verze je nyní vzájemně závislá, může jedna změna způsobit zvlnění změn ve všech novějších verzích. Obrázky 1 a 2 ukazují příklad tohoto vlnícího se efektu.

Definice

Jakoukoli datovou strukturu lze přeformulovat se zpětným nastavením. Obecně datová struktura zahrnuje řadu aktualizací a dotazů provedených v průběhu určitého časového období. Nechť U = [ut1, ut2, ut3, ..., utm] je posloupnost aktualizačních operací od t1 až tm takový, že t1 2 <... m. Zde se předpokládá, že pro danou dobu t lze provést nejvýše jednu operaci.

Částečně se zpětnou platností

Definujeme datovou strukturu jako částečně retroaktivní, pokud může v aktuálním čase provádět operace aktualizace a dotazování a podporovat operace vkládání a mazání v minulosti. Částečně zpětně nás tedy zajímají následující operace:

  • Vložit (t, u): Vložit novou operaci u do seznamu U v čase t.
  • Odstranit (t): Vymazat operaci v čase t ze seznamu U.

Vzhledem k výše uvedeným zpětným operacím by standardní operace vložení měla nyní formu Vložit (t, „vložit (x)“). Všechny zpětné změny provozní historie datové struktury mohou potenciálně ovlivnit všechny operace v době operace až do současnosti. Například pokud máme ti-1 i + 1, pak Insert (t, insert (x)) by umístil novou operaci, opmezi operacemi opi-1 a opi + 1. Aktuální stav datové struktury (tj .: datová struktura v současné době) by pak byl ve stavu, jako jsou operace opi-1, op a opi + 1 vše se stalo v pořadí, jako by operace op vždy tam byl. Viz obrázek 1 a 2 pro vizuální příklad.

Plně retroaktivní

Definujeme datovou strukturu tak, aby byla plně retroaktivní, pokud kromě částečně retroaktivních operací umožníme i jedné provádět dotazy o minulosti. Podobně jako u standardní operace insert (x) se stává Insert (t, "insert (x)") v částečně retroaktivním modelu, operační dotaz (x) v plně retroaktivním modelu má nyní formulář Query (t, "query ( X)").

Zpětné doby chodu

Doba provozu retroaktivních datových struktur je založena na počtu operací, m, provedené na struktuře, počet operací r které byly provedeny před provedením zpětné operace, a maximální počet prvků n ve struktuře najednou.

Automatická retroaktivita

Hlavní otázkou týkající se automatické retroaktivity s ohledem na datové struktury je, zda existuje obecná technika, která může převést jakoukoli datovou strukturu na efektivní retroaktivní protějšek. Jednoduchým přístupem je provedení vrácení zpět ke všem změnám provedeným ve struktuře před zpětnou operací, která má být použita. Jakmile vrátíme datovou strukturu do příslušného stavu, můžeme použít retroaktivní operaci a provést požadovanou změnu. Jakmile je změna provedena, musíme znovu použít všechny změny, které jsme dříve vrátili, abychom uvedli datovou strukturu do nového stavu. I když to může fungovat pro jakoukoli datovou strukturu, je to často neefektivní a nehospodárné, zvláště když je velký počet změn, které potřebujeme vrátit zpět. Chcete-li vytvořit účinný se zpětnou strukturou dat se musíme podívat na vlastnosti samotné struktury, abychom zjistili, kde lze zrychlení realizovat. Neexistuje tedy žádný obecný způsob, jak převést jakoukoli datovou strukturu na efektivní retroaktivní protějšek. Erik D. Demaine, John Iacono a Stefan Langerman dokaž to.[1]


Viz také

Reference

  1. ^ A b Demaine, Erik D.; Iacono, Johne; Langerman, Stefan (2007). „Retroaktivní datové struktury“. Transakce ACM na algoritmech. 3. doi:10.1145/1240233.1240236. Citováno 21. dubna 2012.