Активная структура данных

Активная структура данных — это структура данных со связанным потоком или процессом, выполняющим внутренние операции. ^[1] Более конкретно, активная структура данных связана с вычислительным ресурсом , который содержит один или несколько одновременно выполняемых процессов, и данные, связанные с этими процессами. Коммуникация моделируется с использованием удаленных вызовов процедур , в отличие от общей памяти или передачи сообщений . Внутреннее устройство активной структуры данных скрыто за ее интерфейсом RPC и доступно одновременно. Типичные примеры включают базы данных и файловые системы. Активные структуры данных могут выполнять обслуживание, когда в противном случае ресурсы простаивают, и представлять несколько представлений данных. ^[2]

Пример

Очередь , предоставляемая оборудованием или операционной системой, обычно не является неограниченной, а имеет конечную емкость. Предположим, что к приложению предъявляется строгое требование никогда не терять элементы очереди. Затем процесс записи необходимо изменить для сохранения элементов на носителе данных большой емкости, если очередь заполнена, а процесс чтения должен прочитать элементы обратно. Используя концепцию активных структур данных, вместо этого можно рассмотреть «активную очередь», которая управляет сохранением и извлечением элементов из хранилища большой емкости. Хотя теперь выполняется три процесса вместо двух, что потенциально усложняет синхронизацию, абстракция высокого уровня чтения-записи для использования активной очереди по-прежнему проста и понятна.

Формализация

Самонастраивающиеся вычисления — это метод создания дополнительных вычислительных программ, которые поддерживают внутреннее состояние и могут адаптироваться к новым входным данным более эффективно, чем повторные вычисления с нуля. Это предполагает, что активные структуры данных могут быть формализованы путем введения понятия времени в типичную алгебраическую характеристику структур данных. В частности, Канат Тангвонгсан предполагает, что активная структура данных представляет собой алгебру со следующими тремя метаоперациями: ^[3]

Perform("operation _i (·)", t) выполнит операцию Operation _i в момент времени t. Если операция _i (·) возвращает значение r _i , то метаоперация возвращает значение r _i .
Метаоперация undo(t) вызывает отмену операции в момент времени t. Это используется для моделирования дополнительных вычислений.
Метаоперация update(t) сообщает структуре данных о необходимости «синхронизироваться» до момента времени t. Сюда входит информация о других процессах.

См. также

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

Ссылки

^ «активная структура данных» . xlinux.nist.gov .
^ Эндрюс, Грегори Р.; Добкин, Дэвид П. (9 марта 1981 г.). Активные структуры данных . 5-я Международная конференция по разработке программного обеспечения, ICSE, 1981. Компьютерное общество IEEE. стр. 354–362.
^ Танвонгсан, Канат (5 мая 2006 г.). Активные структуры данных и приложения к динамическим и кинетическим алгоритмам (PDF) (Диссертация).

В этой статье использованы общедоступные материалы из Пол Э. Блэк. «Активная структура данных» . Словарь алгоритмов и структур данных . НИСТ .

[1] «активная структура данных» . xlinux.nist.gov .

[2] Эндрюс, Грегори Р.; Добкин, Дэвид П. (9 марта 1981 г.). Активные структуры данных . 5-я Международная конференция по разработке программного обеспечения, ICSE, 1981. Компьютерное общество IEEE. стр. 354–362.

[3] Танвонгсан, Канат (5 мая 2006 г.). Активные структуры данных и приложения к динамическим и кинетическим алгоритмам (PDF) (Диссертация).

[1]

[2]

[3]