Онлайн-алгоритм обновления списков: различия между версиями

Обновление списков представляет собой классическую онлайновую задачу и, наряду с задачей о подкачке страниц, является первой проблемой, которая была изучена с точки зрения конкурентоспособности. Задача обновления списков заключается в поддержании словаря в виде несортированного линейного списка. Рассмотрим множество элементов, представленное в виде линейного цепного списка. Системе предъявляется последовательность запросов <math>\sigma</math>, где каждый запрос представляет собой одну из следующих операций. Это может быть (1) ''доступ'' к элементу списка, (2) ''вставка'' нового элемента в список или (3) ''удаление'' элемента. Чтобы выполнить доступ к элементу, алгоритм обновления списков начинает с первых элементов списка и линейно перебирает элементы, пока не будет найден нужный. Для вставки нового элемента алгоритм сначала сканирует весь список, чтобы убедиться, что этого элемента еще нет, а затем вставляет его в конец списка. Для удаления элемента алгоритм сканирует список в поисках элемента, а затем удаляет его.

При обработке запросов алгоритм обновления списков несет накладные расходы. Если запрос является операцией доступа или удаления, то накладные расходы равны <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> также называется ''коэффициентом конкурентоспособности''. Конкурентоспособность должна быть одинаковой для ''списков любых размеров''.

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

Сначала рассмотрим алгоритмы Move-To-Front, Transpose и Frequency-Count. Отметим, что Move-To-Front и Transpose – стратегии ''без памяти'', то есть им не требуется дополнительная память для принятия решения о том, куда переместить запрошенный элемент. Таким образом, с практической точки зрения они более привлекательны, чем Frequency-Count. Слейтор и Тарьян [16] проанализировали коэффициенты конкурентоспособности этих трех алгоритмов.

'''Алгоритм «Комбинация» (Combination)''': с вероятностью <math>\frac{4}{5}</math> алгоритм обрабатывает последовательность запросов, используя Bit, и с вероятностью <math>\frac{1}{5}</math> обрабатывает последовательность запросов, используя Timestamp.

Амбюл и др. [4] представили нижнюю границу для рандомизированных алгоритмов обновления списков.

'''Теорема 5 [4]. Пусть A – рандомизированный онлайн-алгоритм для задачи обновления списков. Если A <math>c</math>-конкурентен относительно любого рассеянного соперника, то с > 1,50084.'''

До сих пор в данной статье рассматривались онлайновые алгоритмы. В оффлайновом варианте задачи обновления списков вся последовательность запросов <math>\sigma</math> известна заранее. Амбюл [3] показал, что оффлайновый вариант является NP-трудным.

Что касается истории задачи об обновлении списков, то до появления сравнительного анализа алгоритмы обновления списков изучались в сценариях, где последовательности запросов формируются в соответствии с вероятностными распределениями. Асимптотические ожидаемые затраты, понесенные онлайновым алгоритмом при обработке одного запроса, сравнивались с соответствующими затратами, понесенными при оптимальном статическом упорядочивании. Существует большой объем литературы по этой теме. Чанг и др. [11] показали, что для любого распределения асимптотическая стоимость обработки алгоритма Move-To-Front не более чем в <math>\frac{\pi}{2}</math> раз превышает стоимость обработки оптимального упорядочения.

Линейные списки представляют собой одну из возможностей представления множества элементов. Конечно, существуют и другие структуры данных, такие как сбалансированные деревья поиска или хэш-таблицы, которые, в зависимости от конкретного приложения, могут хранить множество более эффективным способом. В целом линейные списки полезны, когда множество невелико и состоит всего из нескольких десятков элементов. Наиболее важным способом применения алгоритмов обновления списков являются локально адаптивные схемы сжатия данных. Барроуз и Уилер [10] разработали схему сжатия данных с помощью линейных списков, которая обеспечивает лучшее сжатие, чем алгоритмы на основе подхода Лемпеля-Зива. Перед описанием этого алгоритма в следующем параграфе сначала приводится очень простая и легко реализуемая схема сжатия данных, предложенная Бентли и др. [8].

В задаче сжатия данных дается строка <math>S</math>, которая должна быть сжата, то есть представлена с использованием меньшего количества бит. Строка <math>S</math> состоит из символов, где каждый символ является элементом алфавита <math>\Sigma = \{ x_1, ..., x_n \}</math>. Идея схем сжатия данных с использованием линейных списков заключается в том, чтобы преобразовать строку <math>S</math> символов в строку <math>I</math> целых чисел. Кодер поддерживает линейный список символов, содержащихся в <math>\Sigma</math>, и считывает символы из строки <math>S</math>. Всякий раз, когда символ <math>x_i</math> должен быть сжат, кодер ищет текущую позицию <math>x_i</math> в линейном списке, выводит эту позицию и обновляет список с помощью правила обновления списков. Если символы, подлежащие сжатию, переместить ближе к началу списка, то часто встречающиеся символы можно закодировать небольшими целыми числами. Декодер, который получает строку <math>I</math> и должен восстановить исходную строку <math>S</math>, также ведет линейный список символов. Для каждого целого числа <math>j</math>, которое он считывает из <math>I</math>, он ищет символ, который в данный момент хранится в позиции <math>j</math>. Затем декодер обновляет список, используя то же правило обновления списков, что и кодер. В качестве правила обновления списков можно использовать любой (детерминированный) онлайн-алгоритм. Очевидно, что при реальном хранении или передаче строки <math>I</math> каждое целое число в строке должно быть закодировано с помощью префиксного кода переменной длины.

Барроуз и Уилер [10] разработали очень эффективный алгоритм сжатия данных с помощью самоорганизующихся списков. Сначала алгоритм применяет обратимое преобразование к строке <math>S</math>. Цель этого преобразования[https://ru.wikipedia.org/wiki/%D0%9F%D1%80%D0%B5%D0%BE%D0%B1%D1%80%D0%B0%D0%B7%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D0%B5_%D0%91%D0%B0%D1%80%D1%80%D0%BE%D1%83%D0%B7%D0%B0_%E2%80%94_%D0%A3%D0%B8%D0%BB%D0%B5%D1%80%D0%B0] – сгруппировать экземпляры символа <math>x_i</math>, встречающиеся в <math>S</math>. Затем полученная строка <math>S'</math> кодируется с помощью алгоритма Move-To-Front. Более точно, преобразованная строка <math>S'</math> вычисляется следующим образом. Пусть <math>m</math> – длина <math>S</math>. Сначала алгоритм вычисляет <math>m</math> поворотов (циклических сдвигов) <math>S</math> и лексикографически сортирует их. Затем он извлекает последний символ из этих поворотов. <math>k</math>-м символом <math>S'</math> является последний символ <math>k</math>-го отсортированного поворота. Алгоритм также вычисляет индекс <math>J</math> исходной строки <math>S</math> в отсортированном списке поворотов. Барроуз и Уилер предложили эффективный алгоритм восстановления исходной строки <math>S</math>, имея только <math>S'</math> и <math>J</math>. В соответствующей статье [10] дается очень подробное описание алгоритма и сообщается о результатах экспериментов. На корпусе Calgary Compression Corpus [18] этот алгоритм превосходит UNIX-утилиты compress и gzip, причем улучшение составляет 13% и 6%, соответственно.

Наиболее важной проблемой является определение строгих верхних и нижних границ коэффициента конкурентоспособности, который может быть достигнут рандомизированными алгоритмами обновления списков в режиме онлайн относительно рассеянных соперников. Неясно, какова истинная конкурентоспособность. Предполагается, что она меньше 1,6. Однако, как следует из Теоремы 5, коэффициент эффективности должен быть выше 1,5.

Ранние экспериментальные исследования алгоритмов Move-To-Front, Transpose и Frequency Count были проведены Ривестом [15], а также Бентли и Макгиох [7]. Более позднее и обширное экспериментальное исследование представили Бахрах и коллеги [ ]. Они реализовали и протестировали большое количество онлайновых алгоритмов обновления списков на последовательностях запросов, сгенерированных вероятностными распределениями и цепями Маркова, а также на последовательностях, извлеченных из корпуса Calgary Corpus. Было показано, что локальность ссылок существенно влияет на абсолютную и относительную производительность алгоритмов. Бахрах и др. также проанализировали различные алгоритмы как стратегии сжатия данных.