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

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

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

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

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

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

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

Смотрите также

использованная литература

  • Слеатор, Д .; Tarján, R. (1985), "Амортизационная эффективность обновлените список и пейджинговые правил", коммуникации АСМА , 28 (2): 202-208, DOI : 10,1145 / 2786,2793 .
  • Аспнес, Джеймс (1998), «Конкурентный анализ распределенных алгоритмов», в Fiat, A .; Woeginger, GJ (eds.), Online Algorithms: The State of the Art , Lecture Notes in Computer Science, 1442 , pp. 118–146, doi : 10.1007 / BFb0029567. .
  • Бородин, А .; Эль-Янив, Р. (1998), Онлайн-вычисления и конкурентный анализ , Cambridge University Press, ISBN   0-521-56392-5 .
  • Awerbuch, B .; Куттен, С .; Пелег, Д. (1992), «Конкурентное распределенное планирование работ», ACM STOC, Виктория, Британская Колумбия, Канада .