Альтернативные показатели эффективности онлайновых алгоритмов: различия между версиями

В процессе конкурентного анализа эффективность онлайнового алгоритма сравнивается с эффективностью его всемогущего соперника на входных данных, относящихся к наихудшему случаю. Коэффициент конкурентоспособности алгоритма A определяется как наихудшее возможное отношение <math>R_A = max_x \frac{A(x)}{opt(x)}</math>, где x пробегает все возможные входные данные задачи, а A(x) и opt(x) представляют собой стоимость решений, полученных алгоритмом A, и оптимальный оффлайновый алгоритм для входного значения x, соответственно [''Все задачи в данной статье предполагаются онлайновыми задачами минимизации, следовательно, цель заключается в минимизации затрат. Все представленные здесь результаты действительны и для онлайновых задач максимизации с соответствующими корректировками в определениях'']. Это понятие может быть расширено для определения коэффициента конкурентности задачи как минимального коэффициента конкурентности алгоритма ее решения, а именно <math>R = min_A R_A = min_A max_x \frac{A(x)}{opt(x)}.</math>

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

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

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

Коэффициентом конкурентоспособности алгоритма A на базе распределения входных данных <math>\Delta</math> является инфимум c, такой, что алгоритм является c-конкурентным в случае, если входные данные ограничены этим классом. Это имеет место, если существует такая константа d, что для всех распределений <math>D \in \Delta</math> выполняется соотношение <math>\mathcal{E}_D (A(x)) \le c \mathcal{E}_D (opt(x)) + d</math>, где <math>\mathcal{E}_D</math> обозначает математическое ожидание для входных данных, подчиняющихся распределению D. Коэффициентом конкурентоспособности <math>R(\Delta)</math> класса распределений <math>\Delta</math> является минимальный коэффициент конкурентоспособности, достижимый онлайновым алгоритмом на базе распределения <math>\Delta</math>.

Доказательство этого утверждения основывается на понятии ''рабочей функции'', введенном в [5], которое используется в качестве инструмента отслеживания поведения оптимального оффлайнового алгоритма и оценки оптимальной стоимости последовательности запросов, а также тех же параметров для ''консервативных соперников'', которые назначают более высокие вероятности недавно запрошенным страницам. Этот тип соперника согласуется с ''локальностью ссылок'' – понятием, которое всегда было связано с алгоритмами подкачки и конкурентным анализом (хотя в работе [1] другое семейство распределений было предложено и проанализировано в рамках данной структуры, точнее отражающей это понятие).

Первый результат говорит о том, что для любого соперника <math>D \in \Delta_{\epsilon}</math> существует консервативный соперник <math>\hat{D} \in \Delta_{\epsilon}</math>, такой, что коэффициент конкурентоспособности LRU относительно <math>\hat{D}</math> не меньше, чем коэффициент конкурентоспособности LRU относительно <math>D</math>. Было показано, что для любого консервативного соперника <math>D \in \Delta_{\epsilon}</math> относительно LRU существует консервативный соперник <math>D' \in \Delta_{\epsilon}</math> относительно онлайнового алгоритма A, такой, что коэффициент конкурентоспособности LRU относительно D не превышает коэффициент конкурентоспособности A относительно D'. Иными словами, для любого <math>\epsilon</math> LRU имеет оптимальный коэффициент конкурентоспособности <math>R(\Delta_{\epsilon})</math> для диффузной модели соперника. Это основной результат первой части работы [4].

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

Это понятие можно проиллюстрировать тем, насколько выигрышным может оказаться наличие некоторого ''просмотра вперед'' для алгоритмов решения [[системы_метрических_задач|систем метрических задач]] (Metrical Task Systems, MTS). MTS – это абстрактная модель, предложенная в работе [2], которая обобщает обширное семейство онлайновых задач, среди которых задача подкачки, k-серверная задача, доступ к спискам и многие другие. В системе метрических задач сервер может перемещаться по точкам метрического пространства (состояниям) при обслуживании последовательности запросов, или задач. Стоимость обслуживания задачи зависит от состояния, в котором находится сервер, а общая стоимость последовательности задается суммой пройденных расстояний плюс стоимость обслуживания всех задач. Значение просмотра вперед в этом контексте заключается в том, что сервер может решить, какую задачу обслужить следующей, не только на основании своих предыдущих перемещений и выходных данных, но и на основании некоторого количества будущих запросов.

Наконец, было показано, что для конкретной метрической системы задач эффективность просмотра вперед строго меньше вышеуказанной: для задачи подкачки сравнительное отношение составляет в точности min{''l + 1, k''}, то есть преимущество использования просмотра представляет собой минимальное из значений размера кэша и размера окна просмотра вперед плюс 1.

Как было отмечено во введении к [4], представленные в этой работе идеи позволяют получить более качественный и точный анализ эффективности онлайновых алгоритмов. Кроме того, диффузная модель соперника может оказаться полезной для отражения характеристик входных данных, являющихся вероятностными по своей природе (таких как локальность). Примером подобного направления является статья Беккетти [1], в которой диффузная модель соперника сипользуется для более точного моделирования феномена локальности ссылок, характеризующего практическое применение алгоритма подкачки. В рассматриваемых в этой работе распределениях вероятность запроса страницы также является функцией от ее «возраста»; было показано, что коэффициент конкурентоспособности LRU по мере роста локальности становится константным.

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

Остается нерешенной задача определения точного коэффициента конкурентоспособности при применении диффузной модели соперника известных алгоритмов (таких как FIFO) для решения задачи подкачки. Известно, что на практике FIFO работает хуже, чем LRU, так что доказательство субоптимального выполнения первого для некоторых значений " обеспечит поддержку этой модели.

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

* [[Онлайн-алгоритм интервальной раскраски]]