4551
правка
Альтернативные показатели эффективности онлайновых алгоритмов: различия между версиями
Перейти к навигации
Перейти к поиску
Альтернативные показатели эффективности онлайновых алгоритмов (посмотреть исходный код)
Версия от 16:43, 1 сентября 2019
, 1 сентября 2019→Применение
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 55: | Строка 55: | ||
== Применение == | == Применение == | ||
Как было отмечено во введении к [4], представленные в этой работе идеи позволяют получить более качественный и точный анализ эффективности онлайновых алгоритмов. Кроме того, диффузная модель соперника может оказаться полезной для отражения характеристик входных данных, являющихся вероятностными по своей природе (таких как локальность). Примером подобного направления является статья Беккетти [1], в которой диффузная модель соперника сипользуется для более точного моделирования феномена локальности ссылок, характеризующего практическое применение алгоритма подкачки. В рассматриваемых в этой работе распределениях вероятность запроса страницы также является функцией от ее «возраста»; было показано, что коэффициент конкурентоспособности LRU по мере роста локальности становится константным. | |||
В работе [ ] был применен другой подход. В ней рассматривалась задача подкачки с переменным размером кэша и было показано, что подход на основе ожидаемого коэффициента конкурентоспособности на базе диффузной модели соперника может приводить к ошибкам, и предложено использование среднего коэффициента эффективности. | |||
== Открытые вопросы == | |||
Остается нерешенной задача определения точного коэффициента конкурентоспособности при применении диффузной модели соперника известных алгоритмов (таких как FIFO) для решения задачи подкачки. Известно, что на практике FIFO работает хуже, чем LRU, так что доказательство субоптимального выполнения первого для некоторых значений " обеспечит поддержку этой модели. | |||
Представленный в этой статье открытый подход заключается в рассмотрении так называемой Марковской диффузной модели соперника, которая, как понятно из названия, описывает соперника, генерирующего на выходе последовтальность запросов согласно марковскому процессу. | |||
Еще одним направлением предполагаемых исследований может быть использование идеи сравнительного анализа для сравнения эффективности агентов или роботов с разными возможностями (например, с разными диапазонами видимости) для выполнения некоторых задач (например, для построения плана окружающей обстановки). | |||
== См. также == | |||
* [[Списочное планирование]] | |||
* [[Балансировка нагрузки]] | |||
* [[Системы метрических задач]] | |||
* [[Онлайн-алгоритм интервальной раскраски]] | |||
* [[Онлайн-алгоритм обновления списков]] | |||
* [[Обмен пакетами при переключении между несколькими очередями]] | |||
* [[Обмен пакетами при помощи одного буфера]] | |||
* [[Подкачка страниц]] | |||
* [[Робототехника]] | |||
* [[Маршрутизация]] | |||
* [[Алгоритм рабочей функции для k серверов]] | |||
== Литература == | |||
1. Becchetti, L.: Modeling locality: A probabilistic analysis of LRU and FWF. In: Proceeding 12th European Symposium on Algorithms (ESA) (2004) | |||
2. Borodin, A., Linial, N., Saks, M.E.: An optimal on-line algorithm for metrical task systems. J. ACM 39, 745-763 (1992) | |||
3. Koutsoupias, E., Papadimitriou, C.H.: Beyond competitive analysis. In: Proceeding 35th Annual Symposium on Foundations of Computer Science, pp. 394-400, Santa Fe, NM (1994) | |||
4. Koutsoupias, E., Papadimitriou, C.H.: Beyond competitive analysis. SIAM J. Comput. 30(1), 300-317 (2000) | |||
5. Koutsoupias, E., Papadimitriou, C.H.: On the k-server conjecture. J.ACM42(5),971-983 (1995) | |||
6. Manasse, M.S., McGeoch, L.A., Sleator, D.D.: Competitive algorithms for on-line problems. In: Proceeding 20th Annual ACM Symposium on the Theory of Computing, pp. 322-333, Chicago, IL (1988) | |||
7. Panagiotou, K., Souza, A.: On adequate performance measures for paging. In: Proceeding 38th annual ACM symposium on The ory of computing, STOC 2006 | |||
8. Sleator, D.D., Tarjan, R.E.: Amortized efficiency of list update and paging rules. Comm. ACM. 28, 202-208 (1985) | |||
9. Young, N.E.: On-Line Paging against Adversarially Biased Random Inputs. J. Algorithms 37, 218 (2000) | |||