Разработка рандомизированного алгоритма маркировки

Только что рассмотренный неудачный пример для LRU показывает, что если вы хотите получить лучшую границу для алгоритма оперативного кэширования, рас- суждать на уровне полностью обобщенных алгоритмов маркировки не удастся.
Вместо этого мы определим простой рандомизированный алгоритм маркировки и покажем, что он никогда не порождает более чем в О(log к) раз больше промахов, чем оптимальный алгоритм — экспоненциально улучшенная граница.

Рандомизация является естественным выбором для предотвращения нежела- тельных серий «ошибочных» выборов из плохого примера для LRU. Чтобы полу- чить эту плохую последовательность, нужно было определить последовательность, которая всегда вытесняет ошибочный элемент. Рандомизация позволит политике «в среднем» вытеснять непомеченный элемент, который по крайней мере не пона- добится немедленно. А конкретно, строка

Иначе вытеснить из кэша непомеченный элемент
в общем описании алгоритма, не уточняющая, как именно должен выбираться непомеченный элемент, в рандомизированном алгоритме маркировки заменяется следующим правилом:

Иначе вытеснить из кэша непомеченный элемент, выбранный случайным образом с равномерным распределением

Пожалуй, это самый простой способ включения рандомизации в механизм маркировки[21].

<< | >>
Источник: Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика Computers Science. 2016

Еще по теме Разработка рандомизированного алгоритма маркировки:

  1. Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика Computers Science, 2016
  2. Sшrvig Morten. Базовые алгоритмы Qt 4 (Qt 4's Generic Algorithms), 2000
  3. АЛГОРИТМ
  4. АЛГОРИТМ УДАЧИ
  5. Алгоритм исцеления:
  6. Алгоритм избавления от боли
  7. § 2. АЛГОРИТМ АНАЛИЗА ПСИХОЛОГО-ПЕДАГОГИЧЕСКИХ СИТУАЦИЙ
  8. Алгоритм обработки результатов.
  9. 2. Специфика и алгоритмы работы с источниками.
  10. СИСТЕМНАЯ ДИАГНОСТИКА АЛГОРИТМ ОБНАРУЖЕНИЯ И УСТРАНЕНИЯ ПРИЧИН ПОВРЕЖДЕНИЙ ВСЕХ СЕМИ ТЕЛ ЧЕЛОВЕКА.
  11. Э. ТАНЕНБАУМ, А. ВУДХАЛЛ. ОПЕРАЦИОННЫЕ СИСТЕМЫ Разработка и реализация 3-е издание, 2007
  12. Разработка Плана
  13. 2.7. Разработка анкеты
  14. 6. Разработка перспектив
  15. Разработка и принятие Основного закона
  16. Состояние научной разработки проблемы.
  17. Правило разработки веера версий