Конкурентный анализ (онлайн-алгоритм)

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

Для многих алгоритмов производительность зависит не только от размера входных данных, но и от их значений. Например, сортировка массива элементов различается по сложности в зависимости от начального порядка. Такие зависящие от данных алгоритмы анализируются для данных среднего и наихудшего случая. Конкурентный анализ — это способ анализа наихудшего случая для онлайновых и рандомизированных алгоритмов , которые обычно зависят от данных.

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

Например, алгоритм быстрой сортировки выбирает один элемент, называемый «центр», то есть в среднем не слишком далеко от центрального значения сортируемых данных. Затем быстрая сортировка разделяет данные на две стопки, одна из которых содержит все элементы со значением меньше значения опорной точки, а другая — остальные элементы. Если быстрая сортировка выбирает ось каким-то детерминированным образом (например, всегда выбирая первый элемент в списке), то злоумышленнику легко заранее упорядочить данные, чтобы быстрая сортировка выполнялась в худшее время. Однако если быстрая сортировка выбирает какой-то случайный элемент в качестве опорного, то злоумышленник, не зная, какие случайные числа появляются, не сможет упорядочить данные так, чтобы гарантировать время выполнения быстрой сортировки в наихудшем случае.

Классической онлайн-проблемой, впервые анализируемой с помощью конкурентного анализа ( Sleator & Tarjan 1985 ), является проблема обновления списка : учитывая список элементов и последовательность запросов на различные элементы, минимизируйте стоимость доступа к списку, в котором элементы ближе к доступ к началу списка обходится дешевле. (Обычно стоимость доступа к элементу равна его положению в списке.) После доступа список можно переупорядочить. Большинство перестановок имеют свою цену. Алгоритм Move-To-Front просто перемещает запрошенный элемент на передний план после доступа без каких-либо затрат. Алгоритм транспонирования заменяет доступный элемент на элемент, расположенный непосредственно перед ним, также бесплатно. Классические методы анализа показали, что транспонирование оптимально в определенных контекстах. На практике Move-To-Front показал себя намного лучше. Конкурентный анализ был использован, чтобы показать, что противник может заставить Transpose работать сколь угодно плохо по сравнению с оптимальным алгоритмом, тогда как Move-To-Front никогда не может потребовать более чем двукратной стоимости оптимального алгоритма.

В случае онлайн-запросов с сервера используются конкурентные алгоритмы для преодоления неопределенности относительно будущего. То есть алгоритм не «знает» будущее, а воображаемый противник («конкурент») «знает». Аналогично, конкурентные алгоритмы были разработаны для распределенных систем, где алгоритм должен реагировать на запрос, поступающий в одно место, не «зная», что только что произошло в удаленном месте. Эта установка была представлена в ( Awerbuch, Kutten & Peleg 1992 ).

См. также

Ссылки

Слейтор, Д. ; Тарьян, Р. (1985), «Амортизированная эффективность правил обновления списков и пейджинга», Communications of the ACM , 28 (2): 202–208, doi : 10.1145/2786.2793 .
Аспнес, Джеймс (1998), «Конкурентный анализ распределенных алгоритмов», в Fiat, A .; Воегингер, Г.Дж. (ред.), Онлайн-алгоритмы: современное состояние , Конспект лекций по информатике, том. 1442, стр. 118–146, doi : 10.1007/BFb0029567 , ISBN. 978-3-540-64917-5 .
Бородин А. ; Эль-Янив, Р. (1998), Онлайн-вычисления и конкурентный анализ , издательство Кембриджского университета, ISBN 0-521-56392-5 .
Авербух, Б.; Каттен, С. ; Пелег, Д. (1992), «Конкурентоспособное распределенное планирование заданий», ACM STOC, Виктория, Британская Колумбия, Канада .