Проблема с обновлением списка

Обновление списка или проблема доступа к списку — это простая модель, используемая при изучении конкурентного анализа онлайн -алгоритмов . Учитывая набор элементов в списке, где стоимость доступа к элементу пропорциональна его расстоянию от начала списка, например, связанный список , и последовательность запросов на доступ, проблема состоит в том, чтобы придумать стратегию изменения порядка список, чтобы свести к минимуму общую стоимость доступа. Повторный заказ можно сделать в любое время, но это потребует дополнительных затрат. Стандартная модель включает в себя два действия по изменению порядка:

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

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

Было высказано предположение, что наряду с первоначальным использованием эта проблема имеет большое сходство с проблемами улучшения глобального контекста и сжимаемости после преобразования Берроуза-Уиллера . После этого преобразования файлы, как правило, имеют большие области с локально высокими частотами, а эффективность сжатия значительно повышается за счет методов, которые имеют тенденцию перемещать часто встречающиеся символы к нулю или к началу «списка». В связи с этим методы и варианты Move-to-Front и подсчета частоты часто следуют алгоритму BWT для улучшения сжимаемости.

Модели противника

Противник — это объект, который может выбирать последовательность запросов. $\sigma$ для алгоритма ALG . В зависимости от того, $\sigma$ могут быть изменены в зависимости от стратегии ALG , противникам предоставляются различные полномочия, и эффективность ALG измеряется по сравнению с этими противниками.

должен Незабывчивый злоумышленник построить всю последовательность запросов. $\sigma$ перед запуском ALG и платит оптимальную цену в автономном режиме, $OPT(\sigma )$ который сравнивается с $ALG(\sigma )$

Адаптивный онлайн-злоумышленник может сделать следующий запрос на основе предыдущих результатов онлайн-алгоритма, но платит за запрос оптимально и онлайн.

Адаптивный оффлайн-злоумышленник может сделать следующий запрос на основе предыдущих результатов онлайн-алгоритма, но платит оптимальную офлайн-цену.

Автономные алгоритмы

Конкурентный анализ многих проблем обновления списков проводился без каких-либо конкретных знаний о точной природе оптимального автономного алгоритма (OPT). Существуют алгоритмы, выполняемые за O( n 2 ^л( l -1)) время и O( l !) пространства, где n — длина последовательности запросов, а l — длина списка. ^[1] Самый известный оптимальный автономный алгоритм, зависящий от длины последовательности запросов, работает за время O(l^2(l−1)!n), опубликованный доктором Шрикришнаном Дивакараном в 2014 году. ^[2]

Платные транспозиции вообще необходимы для оптимальных алгоритмов. Рассмотрим список ( a , b , c ), где a находится во главе списка, и последовательность запросов c , b , c , b . Оптимальный оффлайн-алгоритм, использующий только бесплатные обмены, будет стоить 9 (3+3+2+1), тогда как оптимальный офлайн-алгоритм, использующий только платные обмены, будет стоить 8. Таким образом, мы не можем обойтись простым использованием бесплатных транспозиций для оптимального оффлайн-алгоритма. .

Задача оптимального обновления списка оказалась NP-трудной ( Ambühl 2000 ).

Онлайн-алгоритм

Онлайн-алгоритм ALG имеет коэффициент конкурентоспособности c, если для любого входного сигнала он работает как минимум в c раз хуже, чем OPT. т.е. если существует $\alpha \geq 0$ такой, что для всех последовательностей запросов конечной длины $\sigma$ , $ALG(\sigma )-c.OPT(\sigma )\leq \alpha$ . Онлайн-алгоритмы могут быть детерминированными или рандомизированными, и оказывается, что рандомизация в этом случае действительно может помочь против не обращающих внимания противников.

Детерминированный

Большинство детерминированных алгоритмов являются вариантами этих трех алгоритмов:

MTF (Переместиться вперед): После доступа к элементу переместите его в начало списка, не меняя порядок других элементов.
ТРАНС (Транспонирование): Получив доступ к элементу, транспонируйте его с непосредственно предыдущим элементом.
FC (счет частот): Для каждого элемента ведите счетчик частоты обращений к нему — при доступе к элементу увеличивайте его частоту и меняйте порядок списка в порядке убывания частот.

Обратите внимание, что все они используют только свободные транспозиции. Получается, что и ТРАНС, и ФК неконкурентоспособны. Классический результат с использованием метода потенциала анализа ( Sleator & Tarjan 1985 ) доказал, что MTF является 2-конкурентным. Доказательство не требует явного знания OPT, а вместо этого подсчитывает количество инверсий, т.е. элементов, встречающихся в противоположном порядке в списках MTF и OPT.

Любой детерминированный алгоритм имеет нижнюю границу $2-{\frac {2}{l+1}}$ для списка длины l , а MTF на самом деле является оптимальным детерминированным алгоритмом обновления списка. Тип противника не имеет значения в случае детерминированных алгоритмов, потому что противник может самостоятельно запустить копию детерминированного алгоритма, чтобы заранее вычислить наиболее катастрофическую последовательность.

Рандомизированный

Рассмотрим следующий простой рандомизированный алгоритм:

КУСОЧЕК: Для каждого элемента в списке оставьте немного. Инициализируйте все биты равномерно и случайным образом равными 0 или 1. При доступе к элементу переверните бит, и если он равен 1, переместите его вперед, в противном случае не делайте этого.

Этот алгоритм вряд ли является случайным — он делает все случайные выборы в начале, а не во время выполнения. Оказывается, BIT нарушает детерминированные границы — он лучше , чем MTF, против ничего не замечающих противников. Конкурентоспособность 7/4. Существуют и другие рандомизированные алгоритмы, такие как COMB, которые работают лучше, чем BIT. Борис Тейя доказал нижнюю границу 1,5 для любого алгоритма обновления рандомизированного списка. ^[3]

Связанные проблемы

Проблема обновления списка, при которой элементы могут быть вставлены и удалены, называется проблемой обновления динамического списка, в отличие от проблемы обновления статического списка, где разрешен только доступ к элементам списка. Верхняя граница $2-{\frac {2}{l+1}}$ справедливо и для динамической модели.

Существуют также разные модели стоимости. В обычной модели полной стоимости доступ к элементу, расположенному в позиции i, стоит i , но последнее сравнение неизбежно для любого алгоритма, т.е. стоит i-1 на пути i элементов . В модели частичной стоимости эти окончательные затраты сравнения, равные количеству элементов в последовательности запроса, игнорируются. Для затрат платных транспозиций, отличных от единицы, P ^д используются модели.

См. также

Примечания

^ Н. Рейнгольд и Дж. Уэстбрук. Оптимальные автономные алгоритмы обновления списка и правил подкачки. Технический отчет YALE/DcS/TR-805, Йельский университет, Нью-Хейвен, Коннектикут, август 1990 г.
^ Дивакаран, Шрикришнан (30 апреля 2014 г.). «Оптимальный автономный алгоритм обновления списка». arXiv : 1404.7638 [ cs.DS ].
^ Тейя, Борис, Нижняя граница для алгоритмов обновления рандомизированных списков, Inf. Процесс. Летт. (1993), стр. 5–9.

Ссылки

Слейтор, Д. ; Тарьян, Р. (1985), «Амортизированная эффективность обновления списков и правил подкачки», Communications of the ACM , 28 (2): 202–208, CiteSeerX 10.1.1.367.6317 , doi : 10.1145/2786.2793 , S2CID 2494305 .
Бородин А. ; Эль-Янив, Р. (1998). Онлайн-вычисления и конкурентный анализ . Издательство Кембриджского университета. ISBN 978-0-521-56392-5 .

Амбюль, К. (2000), Обновление автономного списка является np-hard , Springer, стр. 42–51.

[1] Н. Рейнгольд и Дж. Уэстбрук. Оптимальные автономные алгоритмы обновления списка и правил подкачки. Технический отчет YALE/DcS/TR-805, Йельский университет, Нью-Хейвен, Коннектикут, август 1990 г.

[2] Дивакаран, Шрикришнан (30 апреля 2014 г.). «Оптимальный автономный алгоритм обновления списка». arXiv : 1404.7638 [ cs.DS ].

[3] Тейя, Борис, Нижняя граница для алгоритмов обновления рандомизированных списков, Inf. Процесс. Летт. (1993), стр. 5–9.

[1]

[2]

[3]