4817
правок
Онлайн-алгоритм обновления списков: различия между версиями
Материал из WEGA
Онлайн-алгоритм обновления списков (посмотреть исходный код)
Версия от 07:16, 25 августа 2025
, 25 август→Постановка задачи
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 3: | Строка 3: | ||
== Постановка задачи == | == Постановка задачи == | ||
Обновление списков представляет собой классическую онлайновую задачу и, наряду с задачей о подкачке, является первой проблемой, которая была изучена с точки зрения конкурентоспособности. Задача обновления списков заключается в поддержании словаря в виде несортированного линейного списка. Рассмотрим множество элементов, представленное в виде линейного цепного списка. Системе предъявляется последовательность запросов | Обновление списков представляет собой классическую онлайновую задачу и, наряду с задачей о подкачке страниц, является первой проблемой, которая была изучена с точки зрения конкурентоспособности. Задача обновления списков заключается в поддержании словаря в виде несортированного линейного списка. Рассмотрим множество элементов, представленное в виде линейного цепного списка. Системе предъявляется последовательность запросов <math>\sigma</math>, где каждый запрос представляет собой одну из следующих операций. Это может быть (1) ''доступ'' к элементу списка, (2) ''вставка'' нового элемента в список или (3) ''удаление'' элемента. Чтобы выполнить доступ к элементу, алгоритм обновления списков начинает с первых элементов списка и линейно перебирает элементы, пока не будет найден нужный. Для вставки нового элемента алгоритм сначала сканирует весь список, чтобы убедиться, что этого элемента еще нет, а затем вставляет его в конец списка. Для удаления элемента алгоритм сканирует список в поисках элемента, а затем удаляет его. | ||
При обработке запросов алгоритм обновления списков несет накладные расходы. Если запрос является операцией доступа или удаления, то накладные расходы равны i, где i – позиция запрашиваемого элемента в списке. Если запрос является вставкой, то затраты равны n + 1, где n – количество элементов в списке перед вставкой. В процессе обработки последовательности запросов алгоритм обновления списков может перестроить список. Сразу после доступа или вставки запрошенный элемент может быть перемещен без дополнительных расходов на любую позицию, расположенную ближе к началу списка. Такие обмены называются бесплатными. При помощи бесплатных обменов алгоритм может снизить стоимость последующих запросов. В любой момент времени два соседних элемента в списке могут быть обменены с затратами 1. Такие обмены называются платными. Цель состоит в том, чтобы обработать последовательность запросов так, чтобы суммарная стоимость была как можно ниже. | При обработке запросов алгоритм обновления списков несет накладные расходы. Если запрос является операцией доступа или удаления, то накладные расходы равны <math>i</math>, где <math>i</math> – позиция запрашиваемого элемента в списке. Если запрос является вставкой, то затраты равны <math>n + 1</math>, где <math>n</math> – количество элементов в списке перед вставкой. В процессе обработки последовательности запросов алгоритм обновления списков может перестроить список. Сразу после доступа или вставки запрошенный элемент может быть перемещен без дополнительных расходов на любую позицию, расположенную ближе к началу списка. Такие обмены называются ''бесплатными''. При помощи бесплатных обменов алгоритм может снизить стоимость последующих запросов. В любой момент времени два соседних элемента в списке могут быть обменены с затратами 1. Такие обмены называются ''платными''. Цель состоит в том, чтобы обработать последовательность запросов так, чтобы суммарная стоимость была как можно ниже. | ||
Особый интерес представляют алгоритмы обновления списков, работающие в режиме онлайн, т. е. каждый запрос обрабатывается без знания о будущих запросах. Производительность онлайн-алгоритмов обычно оценивается при помощи сравнительного анализа. Здесь онлайновая стратегия сравнивается с оптимальным оффлайновым алгоритмом, который заранее знает всю последовательность запросов и может обработать ее с минимальными затратами. Пусть имеется последовательность запросов | Особый интерес представляют алгоритмы обновления списков, работающие в режиме ''онлайн'', т. е. каждый запрос обрабатывается без знания о будущих запросах. Производительность онлайн-алгоритмов обычно оценивается при помощи ''сравнительного анализа''. Здесь онлайновая стратегия сравнивается с оптимальным оффлайновым алгоритмом, который заранее знает всю последовательность запросов и может обработать ее с минимальными затратами. Пусть имеется последовательность запросов <math>\sigma</math>. Обозначим за <math>A(\sigma)</math> затраты, понесенные онлайн-алгоритмом <math>A</math> при обработке последовательности <math>\sigma</math>, а за <math>OPT(\sigma)</math> – затраты, понесенные оптимальным офлайн-алгоритмом OPT. Онлайн-алгоритм <math>A</math> называется <math>c</math>-конкурентным, если существует константа <math>\alpha</math> такая, что для списков любых размеров и всех последовательностей запросов <math>\sigma</math> выполняется соотношение <math>A(\sigma) \le c \cdot OPT(\sigma) + \alpha</math>. Коэффициент <math>c</math> также называется ''коэффициентом конкурентоспособности''. Конкурентоспособность должна быть одинаковой для ''списков любых размеров''. | ||
== Основные результаты == | == Основные результаты == | ||
