Альтернативные показатели эффективности онлайновых алгоритмов

Ключевые слова и синонимы

Диффузная модель соперника для онлайновых алгоритмов; сравнительный анализ онлайновых алгоритмов

Постановка задачи

Несмотря на то, что онлайновые алгоритмы изучались более тридцати лет, явное введение конкурентного анализа в основополагающих статьях Слейтора и Тарьяна [8] и Манасса, Макгиоха и Слейтора [6] привело к взрывному росту объема исследований этого класса задач и алгоритмов, и с тех пор оба понятия (онлайновые алгоритмы и конкурентный анализ) остаются тесно связанными друг с другом. Однако уже на раннем этапе этих исследований возникли вопросы к реалистичности и практичности модели, связанные главным образом с ее пессимизмом. Эта характеристика в некоторых случаях сказывается на способности модели к различению хороших и плохих алгоритмов. В статье 1994 года «За пределами конкурентного анализа» [3] Кутсупиас и Пападимитриу предложили и исследовали два альтернативных показателя эффективности онлайновых алгоритмов, тесно связанные с конкурентным анализом и при этом лишенные вышеупомянутых слабостей. Окончательная версия этой работы вышла в 2000 году [4].

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

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

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

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

Основные результаты

Диффузная модель соперника

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

Эта модель применяется к традиционной задаче подкачки для класса распределений [math]\displaystyle{ \Delta_{\epsilon} }[/math]. Этот класс содержит все распределения вероятностей, такие, что для заданной последовательности запросов и страницы p вероятность того, что p является следующей запрошенной страницей, не превышает [math]\displaystyle{ \epsilon }[/math]. Было показано, что хорошо известный онлайновый алгоритм LRU достигает оптимального коэффициента конкурентоспособности [math]\displaystyle{ R(\Delta_{\epsilon}) }[/math] для всех [math]\displaystyle{ \epsilon }[/math], иначе говоря, что он является оптимальным по отношению к любому сопернику, использующему распределение этого класса.

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

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

Последний оставшийся вопрос касается значения оптимального коэффициента конкурентоспособности LRU для задачи подкачки. Было показано, что вычислить это значение непросто. Для экстремальных значений [math]\displaystyle{ \epsilon }[/math] (случаев, когда соперник обладает полным контролем над входными данными и, напротив, практически не обладает им) [math]\displaystyle{ R(\Delta_1) = k }[/math], где k – размер кэша, кроме того, [math]\displaystyle{ lim_{\epsilon \to 0} R(\Delta_{\epsilon}) = 1 }[/math]. В более поздней работе Янгу [9] удалось оценить [math]\displaystyle{ R(\Delta_{\epsilon}) }[/math] с коэффициентом аппроксимации, почти равным двум. Для значений [math]\displaystyle{ \epsilon }[/math] вблизи порога 1/k оптимальный коэффициент составляет [math]\displaystyle{ \Theta(ln \; k) }[/math], для значений ниже этого порога коэффициент быстро стремится к O(1), а выше него – к [math]\displaystyle{ \Theta(k) }[/math].

Сравнительный анализ

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

Идея сравнительного анализа заключается в измерении относительного качества двух классов алгоритмов на основе максимально возможного отношения результатов, полученных алгоритмами каждого класса для одних и тех же исходных данных.

Более формально, если [math]\displaystyle{ \mathcal{A} }[/math] и [math]\displaystyle{ \mathcal{B} }[/math] – классы алгоритмов, сравнительное отношение [math]\displaystyle{ R(\mathcal{A}, \mathcal{B}) }[/math] определяется как [math]\displaystyle{ R(\mathcal{A}, \mathcal{B}) = max_{B \in \mathcal{B}} \; min_{A \in \mathcal{A}} \; max_x \frac{A(x)}{B(x)}. }[/math]

В рамках этого определения, если класс [math]\displaystyle{ \mathcal{B} }[/math] представляет все алгоритмы, а класс [math]\displaystyle{ \mathcal{A} }[/math] – онлайновые алгоритмы, то сравнительное отношение совпадает с конкурентным отношением, или коэффициентом конкурентоспособности.

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

Основной результат (помимо определения самой модели) заключается в том, что для систем метрических задач сравнительное отношение для класса онлайновых алгоритмов относительно класса алгоритмов с просмотром вперед на l шагов ([math]\displaystyle{ \mathcal{L}_0 }[/math] и [math]\displaystyle{ \mathcal{L}_1 }[/math], соответственно) составляет не более 2l + 1. Иначе говоря, для этого семейства задач преимущество, получаемое в результате просмотра вперед, не более чем в два раза превышает величину просмотра плюс 1. Результат дополняется примерами конкретных задач, для которых имеет место равенство.

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

Применение

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

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

Открытые вопросы

Остается нерешенной задача определения точного коэффициента конкурентоспособности при применении диффузной модели соперника известных алгоритмов (таких как FIFO) для решения задачи подкачки. Известно, что на практике FIFO работает хуже, чем LRU, так что доказательство субоптимального выполнения первого для некоторых значений [math]\displaystyle{ \epsilon }[/math] обеспечит поддержку этой модели.

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

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

См. также

• Списочное планирование
• Балансировка нагрузки
• Системы метрических задач
• Онлайн-алгоритм интервальной раскраски
• Онлайн-алгоритм обновления списков
• Обмен пакетами при переключении между несколькими очередями
• Обмен пакетами при помощи одного буфера
• Подкачка страниц
• Робототехника
• Маршрутизация
• Алгоритм рабочей функции для k серверов

Литература

1. Becchetti, L.: Modeling locality: A probabilistic analysis of LRU and FWF. In: Proceeding 12th European Symposium on Algorithms (ESA) (2004)

2. Borodin, A., Linial, N., Saks, M.E.: An optimal on-line algorithm for metrical task systems. J. ACM 39, 745-763 (1992)

3. Koutsoupias, E., Papadimitriou, C.H.: Beyond competitive analysis. In: Proceeding 35th Annual Symposium on Foundations of Computer Science, pp. 394-400, Santa Fe, NM (1994)

4. Koutsoupias, E., Papadimitriou, C.H.: Beyond competitive analysis. SIAM J. Comput. 30(1), 300-317 (2000)

5. Koutsoupias, E., Papadimitriou, C.H.: On the k-server conjecture. J.ACM42(5),971-983 (1995)

6. Manasse, M.S., McGeoch, L.A., Sleator, D.D.: Competitive algorithms for on-line problems. In: Proceeding 20th Annual ACM Symposium on the Theory of Computing, pp. 322-333, Chicago, IL (1988)

7. Panagiotou, K., Souza, A.: On adequate performance measures for paging. In: Proceeding 38th annual ACM symposium on The ory of computing, STOC 2006

8. Sleator, D.D., Tarjan, R.E.: Amortized efficiency of list update and paging rules. Comm. ACM. 28, 202-208 (1985)

9. Young, N.E.: On-Line Paging against Adversarially Biased Random Inputs. J. Algorithms 37, 218 (2000)