4551
правка
Альтернативные показатели эффективности онлайновых алгоритмов: различия между версиями
Перейти к навигации
Перейти к поиску
Альтернативные показатели эффективности онлайновых алгоритмов (посмотреть исходный код)
Версия от 23:47, 28 августа 2019
, 28 августа 2019→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 33: | Строка 33: | ||
'''Сравнительный анализ''' | '''Сравнительный анализ''' | ||
Сравнительный анализ представляет собой обобщение конкурентного анализа; он позволяет сравнивать не только отдельные алгоритмы, но и классы алгоритмов. Эта новая идея может использоваться для выявления контраста в поведении алгоритмов, следующих произвольным информационным режимам. Информационный режим представляет собой класс алгоритмов, получающих знание о входных данных одинаковым образом или с одинаковой «скоростью». Классы онлайновых и оффлайновых алгоритмов являются иллюстрациями этого понятия (первый получает входные данные шаг за шагом, второй получает всю информацию до того, как выдает какое-либо выходное значение). | |||
Идея сравнительного анализа заключается в измерении относительного качества двух классов алгоритмов на основе максимально возможного отношения результатов, полученных алгоритмами каждого класса для одних и тех же исходных данных. | |||
Более формально, если A и B – классы алгоритмов, сравнительное отношение R(A, B) определяется как | |||
ЖЛ, 2) = max min maxA (ВеВ А€Л x B(x) | |||
В рамках этого определения, если класс B представляет все алгоритмы, а класс A – онлайновые алгоритмы, то сравнительное отношение совпадает с конкурентным отношением , или коэффициентом конкурентоспособности. | |||
Это понятие можно проиллюстрировать тем, насколько выигрышным может оказаться наличие некоторого просмотра вперед для алгоритмов решения систем метрических задач (Metrical Task Systems, MTS). MTS – это абстрактная модель, предложенная в работе [ ], котороая обобщает обширное семейство онлайновых задач, среди которых задача подкачки, k-серверная задача, доступ к спискам и многие другие. В системе метрических задач сервер может перемещаться по точкам метрического пространства (состояниям) при обслуживании последовательности запросов, или задач. Стоимость обслуживания задачи зависит от состояния, в котором находится сервер, а общая стоимость последовательности задается суммой пройденных расстояний плюс стоимость обслуживания всех задач. Значение просмотра вперед в этом контексте заключается в том, что сервер может решить, какую задачу обслужить следующей, не только на основании своих предыдущих перемещений и выходных данных, но и на основании некоторого количества будущих запросов. | |||
Основной результат (помимо определения самой модели) заключается в том, что для систем метрических задач сравнительное отношение для класса онлайновых алгоритмов относительно класса алгоритмов с просмотром вперед на l шаг (L0 и Ll, соответственно) составляет не более 2l + 1. Иначе говоря, для этого семейства задач преимущество, получаемое в результате просмотра вперед, не более чем в два раза превышает величину просмотра плюс 1. Результат дополняется примерами конкретных задач, для которых имеет место равенство. | |||
Наконец, было показано, что для конкретной метрической системы задач эффективность просмотра вперед строго меньше вышеуказанной: для задачи подкачки сравнительное отношение составляет в точности min {l + 1, k}, то есть преимущество использования просмотра представляет собой минимальное из значений размера кэша и размера окна просмотра вперед плюс 1. | |||
== Применение == | |||