Ретроактивная структура данных

В информатике ретроактивная структура данных — это структура данных , которая поддерживает эффективные модификации последовательности операций, которые были выполнены над этой структурой. Эти модификации могут принимать форму обратной вставки, удаления или обновления операции, которая была выполнена когда-то в прошлом. ^[1]

Некоторые применения ретроактивных структур данных

В реальном мире существует множество случаев, когда хотелось бы изменить прошлую операцию из последовательности операций. Ниже перечислены некоторые из возможных применений:

Исправление ошибки : Неправильный ввод данных. Данные следует исправить и устранить все вторичные последствия неверных данных.
Плохие данные . При работе с большими системами, особенно с большими объемами автоматизированной передачи данных, это не редкость. Например, предположим, что один из датчиков метеорологической сети неисправен и начинает сообщать мусорные или неверные данные. Идеальным решением было бы удалить все данные, полученные датчиком, поскольку он работал со сбоями, а также все последствия, которые плохие данные оказали на всю систему.
Восстановление : Предположим, что аппаратный датчик был поврежден, но теперь отремонтирован, и данные с него можно считывать. Мы хотели бы иметь возможность вставлять данные обратно в систему, как если бы датчик никогда не был поврежден.
Манипулирование прошлым . Изменение прошлого может быть полезно в случаях контроля ущерба, а ретроактивные структуры данных предназначены для преднамеренного манипулирования прошлым.

Время как пространственное измерение

Невозможно рассматривать время как дополнительное пространственное измерение. Чтобы проиллюстрировать это, предположим, что мы наносим измерение времени на ось пространства. Структура данных, которую мы будем использовать для добавления измерения пространственного времени, представляет собой минимальную кучу. Пусть ось Y представляет ключевые значения элементов в куче, а ось X представляет собой пространственно-временное измерение. После нескольких операций вставки и удаления-min (все они выполняются без обратной силы) наша min-куча будет выглядеть так, как показано на рисунке 1. Теперь предположим, что мы задним числом вставляем ноль в начало списка операций. Наша минимальная куча будет выглядеть так, как показано на рисунке 2. Обратите внимание, как одна операция создает каскадный эффект, который влияет на всю структуру данных. Таким образом, мы видим, что, хотя время можно изобразить как пространственное измерение, операции со временем создают зависимость, которая имеет пульсацию при внесении изменений в отношении времени.

Сравнение с настойчивостью

На первый взгляд понятие ретроактивных структур данных кажется очень похожим на постоянные структуры данных, поскольку обе они учитывают измерение времени. Ключевое различие между постоянными структурами данных и ретроактивными структурами данных заключается в том, как они обрабатывают элемент времени. Постоянная структура данных поддерживает несколько версий структуры данных, и над одной версией можно выполнять операции для создания другой версии структуры данных. Поскольку каждая операция создает новую версию, каждая версия становится архивом, который нельзя изменить (из него могут быть созданы только новые версии). Поскольку каждая версия не меняется, зависимость между каждой версией также не меняется. В ретроактивных структурах данных мы допускаем внесение изменений непосредственно в предыдущие версии. Поскольку каждая версия теперь взаимозависима, одно изменение может вызвать множество изменений всех последующих версий. На рисунках 1 и 2 показан пример этого волнового эффекта.

Определение

Любая структура данных может быть переформулирована задним числом. Как правило, структура данных включает в себя серию обновлений и запросов, выполняемых в течение определенного периода времени. Пусть U = [u _{t ₁} , u _{t ₂} , u _{t ₃} , ..., u _{t _m} ] — последовательность операций обновления от t ₁ до t _m такая, что t ₁ < t ₂ < ... < t _m . При этом предполагается, что за заданное время t можно выполнить не более одной операции.

Частично имеет обратную силу

Мы определяем структуру данных как частично ретроактивную, если она может выполнять операции обновления и запроса в текущий момент и поддерживать операции вставки и удаления в прошлом. Таким образом, для частично обратной силы нас интересуют следующие операции:

Insert(t, u): вставить новую операцию u в список U в момент времени t.
Удалить(t): удалить операцию в момент времени t из списка U.

Учитывая вышеупомянутые ретроактивные операции, стандартная операция вставки теперь будет иметь вид Insert(t, "insert(x)"). Все ретроактивные изменения в истории операций структуры данных потенциально могут повлиять на все операции на момент операции до настоящего времени. Например, если у нас есть t _i-1 < t < t _i+1 , то Insert(t, Insert(x)) поместит новую операцию op между операциями op _i-1 и op _i+1 . Текущее состояние структуры данных (т. е. структура данных в настоящий момент) тогда будет в таком состоянии, что операции op _i-1 , op и op _i+1 происходят последовательно, как если бы операция ОП всегда была там. Наглядный пример см. на рисунках 1 и 2.

Полностью обратная сила

Мы определяем структуру данных как полностью ретроактивную, если в дополнение к частично ретроактивным операциям мы также позволяем выполнять запросы о прошлом. Подобно тому, как стандартная операция Insert(x) становится Insert(t, "insert(x)") в частично ретроактивной модели, операция query(x) в полностью ретроактивной модели теперь имеет форму Query(t, "query( х)").

Ретроактивное время работы

Время работы структур ретроактивных данных основано на количестве операций m , выполненных над структурой, количестве операций r , которые были выполнены до выполнения ретроактивной операции, и максимальном количестве элементов n в структуре в любой момент времени. время.

Автоматическая ретроактивность

Главный вопрос, касающийся автоматического ретроактивного действия в отношении структур данных, заключается в том, существует ли общий метод, который может преобразовать любую структуру данных в эффективный ретроактивный аналог. Простой подход заключается в выполнении отката всех изменений, внесенных в структуру до применения обратной операции. После того как мы откатили структуру данных до соответствующего состояния, мы можем применить обратную операцию, чтобы внести необходимые изменения. После внесения изменений мы должны повторно применить все изменения, которые мы откатили ранее, чтобы перевести структуру данных в новое состояние. Хотя это может работать для любой структуры данных, часто это неэффективно и расточительно, особенно если количество изменений, которые нам нужно откатить, велико. Чтобы создать эффективную ретроактивную структуру данных, мы должны взглянуть на свойства самой структуры, чтобы определить, где можно реализовать ускорение. Таким образом, не существует общего способа преобразования любой структуры данных в эффективный ретроактивный аналог. Эрик Д. Демейн , Джон Яконо и Стефан Лангерман доказывают это. ^[1]

См. также

Постоянная структура данных

Ссылки

^ Jump up to: ^а ^б Демейн, Эрик Д .; Яконо, Джон ; Лангерман, Стефан (2007). «Ретроактивные структуры данных» . Транзакции ACM на алгоритмах . 3 (2): 13. дои : 10.1145/1240233.1240236 . S2CID 5555302 . Проверено 21 апреля 2012 г.

[retroDS-1] Jump up to: ^а ^б Демейн, Эрик Д .; Яконо, Джон ; Лангерман, Стефан (2007). «Ретроактивные структуры данных» . Транзакции ACM на алгоритмах . 3 (2): 13. дои : 10.1145/1240233.1240236 . S2CID 5555302 . Проверено 21 апреля 2012 г.

[1]