4551
правка
Альтернативные показатели эффективности онлайновых алгоритмов: различия между версиями
Перейти к навигации
Перейти к поиску
Альтернативные показатели эффективности онлайновых алгоритмов (посмотреть исходный код)
Версия от 11:59, 26 августа 2019
, 26 августа 2019→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 21: | Строка 21: | ||
== Основные результаты == | == Основные результаты == | ||
'''Диффузная модель соперника''' | |||
Коэффициентом конкурентоспособности алгоритма A на базе распределения входных данных A является инфимум c, такой, что алгоритм является c-конкурентным в случае, если входные данные ограничены этим классом. Это имеет место, если существует такая константа d, что для всех распределений D 2 A выполняется соотношение | |||
< cED(opt(x)) + d ; | |||
где ED обозначает математическое ожидание для входных данных, подчиняющихся распределению D. Коэффициентом конкурентоспособности R(A) класса распределений A является минимальный коэффициент конкурентоспособности, достижимый онлайновым алгоритмом на базе распределения A. | |||
Эта модель применяется к традиционной задаче подкачки для класса распределений. Этот класс содержит все распределения вероятностей, такие, что для заданной последовательности запросов и страницы p вероятность того, что p является следующей запрошенной страницей, не выше e. Было показано, что хорошо известный онлайновый алгоритм LRU достигает оптимального коэффициента конкурентоспособности R(A€) для всех e, иначе говоря, что он является оптимальным по отношению к любому сопернику, использующему распределение этого класса. | |||
Доказательство этого утверждения основывается на понятии рабочей функции, введенном в [ ], которе используется в качестве инструмента отслеживания поведения оптимального оффлайнового алгоритма и оценки оптимальной стоимости последовательности запросов, а также тех не параметров для консервативных соперников, которые назначают более высокие вероятности недавно запрошенным страницам. Этот тип соперника согласуется с локальностью ссылок – понятием, которое всегда было связано с алгоритмами подкачки и конкурентным анализом (хотя в работе [1] другое семейство распределений было предложено и проанализировано в рамках данной структуры, точнее отражающей это понятие). | |||
Первый результат говорит о том, что для любого соперника D 2 A€ существует консервативный соперник D € A€, такой, что коэффициент конкурентоспособности LRU относительно с D не меньше, чем коэффициент конкурентоспособности LRU относительно D. Было показано, что для любого консервативного соперника D 2 A€ относительно LRU существует консервативный соперник D0 2 A€ относительно онлайнового алгоритма A, такой, что коэффициент конкурентоспособности LRU относительно D не превышает коэффициент конкурентоспособности A относительно D0. Иными словами, для любого e LRU имеет оптимальный коэффициент конкурентоспособности R(A€) для диффузной модели соперника. Это основной результат первой части работы [4]. | |||
Последний оставшийся вопрос касается значения оптимального коэффициента конкурентоспособности LRU для задачи подкачки. Было показано, что вычислить это значение непросто. Для экстремальных значений e (случаев, когда соперник обладает полным контролем над входными данными и, напротив, практически не обладает им) R(Ai) = k, где k – размер кэша, кроме того, lim€^.o R(A€) = 1. В более поздней работе Янга [ ] удалось оценить R(A€) с коэффициентом аппроксимации, почти равным двум. Для значений " вблизи порога 1/k оптимальный коэффициент составляет @(ln k), для значений ниже этого порога коэффициент быстро стремится к O(1), а выше него – к @{k). | |||
'''Сравнительный анализ''' | |||