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

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

Несмотря на то, что онлайновые алгоритмы изучались более тридцати лет, явное введение конкурентного анализа в основополагающих статьях Слейтора и Тарьяна [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{ \mathcal{E}_D (A(x)) \le c \mathcal{E}_D (opt(x)) + d }[/math], где [math]\displaystyle{ \mathcal{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].

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