Альтернативные показатели эффективности онлайновых алгоритмов: различия между версиями

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

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