16
правок
Изменения
Добавлен источник
== Вероятностный алгоритм (англ. ''random marking algorithm'')==В данном алгоритме, у каждого элемента, хранящегося в кэше, может быть метка. Изначально меток ни на одном элементе нет. Когда в кэш поступает запрос:* Если кэш попадание, то просто помечаем значение.* Если кэш промах*# Если все элементы уже помечены, снимаем пометки со всех значений.*# Берём случайное не помеченное значение и вытесняeм его, а новое значение помечаем. == Оценка времени работы алгоритма ==1
== Источники ==
* [https://www.cs.cmu.edu/~sleator/papers/competitive-paging.pdf A. Fiat, R. M. Karp, M. Luby, L. A. McGeoch, D. D. Sleator, N. E. Young, Competitive Paging Algorithms, Journal of Algorithms 12, 685-699 (1991)]
* [http://static.cs.brown.edu/courses/csci2950-w/ranpagingNotes.pdf Lecture notes for Brown CS251 - Randomized paging algorithms]
[[Категория: Алгоритмы и структуры данных]]
