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

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

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

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

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

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

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

Рисунок 1. Min-Heap с временной шкалой.

Рисунок 2. Min-Heap и временная шкала после обратной операции.

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

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

Определение

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

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

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

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

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

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

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

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

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

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

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

Смотрите также

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