4551
правка
Альтернативные показатели эффективности онлайновых алгоритмов: различия между версиями
Материал из WEGA
Альтернативные показатели эффективности онлайновых алгоритмов (посмотреть исходный код)
Версия от 00:10, 29 августа 2019
, 29 августа 2019→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 40: | Строка 40: | ||
Более формально, если A и B – классы алгоритмов, сравнительное отношение R(A, B) определяется как | Более формально, если <math>\mathcal{A}</math> и <math>\mathcal{B}</math> – классы алгоритмов, ''сравнительное отношение'' <math>R(\mathcal{A}, \mathcal{B})</math> определяется как <math>R(\mathcal{A}, \mathcal{B}) = max_{B \in \mathcal{B}} \; min_{A \in \mathcal{A}} \; max_x \frac{A(x)}{B(x)}.</math> | ||
В рамках этого определения, если класс <math>\mathcal{B}</math> представляет все алгоритмы, а класс <math>\mathcal{A}</math> – онлайновые алгоритмы, то сравнительное отношение совпадает с конкурентным отношением, или коэффициентом конкурентоспособности. | |||
Это понятие можно проиллюстрировать тем, насколько выигрышным может оказаться наличие некоторого ''просмотра вперед'' для алгоритмов решения ''систем метрических задач'' (Metrical Task Systems, MTS). MTS – это абстрактная модель, предложенная в работе [2], которая обобщает обширное семейство онлайновых задач, среди которых задача подкачки, k-серверная задача, доступ к спискам и многие другие. В системе метрических задач сервер может перемещаться по точкам метрического пространства (состояниям) при обслуживании последовательности запросов, или задач. Стоимость обслуживания задачи зависит от состояния, в котором находится сервер, а общая стоимость последовательности задается суммой пройденных расстояний плюс стоимость обслуживания всех задач. Значение просмотра вперед в этом контексте заключается в том, что сервер может решить, какую задачу обслужить следующей, не только на основании своих предыдущих перемещений и выходных данных, но и на основании некоторого количества будущих запросов. | |||
Основной результат (помимо определения самой модели) заключается в том, что для систем метрических задач сравнительное отношение для класса онлайновых алгоритмов относительно класса алгоритмов с просмотром вперед на ''l'' шагов (<math>\mathcal{L}_0</math> и <math>\mathcal{L}_1</math>, соответственно) составляет не более ''2l + 1''. Иначе говоря, для этого семейства задач преимущество, получаемое в результате просмотра вперед, не более чем в два раза превышает величину просмотра плюс 1. Результат дополняется примерами конкретных задач, для которых имеет место равенство. | |||
Наконец, было показано, что для конкретной метрической системы задач эффективность просмотра вперед строго меньше вышеуказанной: для задачи подкачки сравнительное отношение составляет в точности min {l + 1, k}, то есть преимущество использования просмотра представляет собой минимальное из значений размера кэша и размера окна просмотра вперед плюс 1. | |||
Наконец, было показано, что для конкретной метрической системы задач эффективность просмотра вперед строго меньше вышеуказанной: для задачи подкачки сравнительное отношение составляет в точности min{''l + 1, k''}, то есть преимущество использования просмотра представляет собой минимальное из значений размера кэша и размера окна просмотра вперед плюс 1. | |||
== Применение == | == Применение == | ||
