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

В 1960-х годах Лес Белади показал, что следующее простое правило всегда приво- дит к минимальному количеству промахов:

Когда элемент d. должен быть внесен в кэш,

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

Назовем его «алгоритмом отдаленного использования».

Когда приходит время вытеснить данные из кэша, алгоритм перебирает все элементы в кэше и выбирает тот из них, который будет использоваться как можно позднее.

Это очень естественный алгоритм. В то же время факт его оптимальности для всех последовательностей не столь очевиден, как может показаться на первый взгляд. Почему нужно вытеснять элемент, который используется в самом отдален- ном будущем, вместо, скажем, элемента, который будет реже всех использоваться в будущем? Или рассмотрим последовательность вида

a, b, c, d, a, d, e, a, d, b, c

с к = 3 и элементами {a, b, c}, изначально находящимися в кэше. Правило отдален- ного использования создаст план S, которое вытесняет c на четвертом шаге и b на седьмом шаге. Однако существуют и другие планы вытеснения, не уступающие этому. Например, план S', который вытесняет b на четвертом шаге и c на седьмом шаге, обеспечивает такое же количество промахов. Очень легко найти ситуации, в которых планы, построенные по другим правилам, также будут оптимальными; не может ли оказаться, что при такой гибкости отступление от правила отдален- ного использования обеспечит реальный выигрыш где-то в конце последователь- ности? Например, на седьмом шаге нашего примера план S' вытесняет элемент (c), который используется позднее, чем элемент, вытесненный в этой точке алгорит- мом отдаленного использования, так как последний вытеснил c ранее.

Это лишь некоторые факторы, которые необходимо учесть, прежде чем делать вывод об оптимальности алгоритма отдаленного использования. Если подумать над приведенным примером, вы быстро поймете: на самом деле несущественно, какой из элементов — b или c — будет вытеснен на четвертом шаге, потому что второй элемент будет вытеснен на седьмом; получив план, в котором элемент b вытесняется первым, вы можете поменять местами вытеснение b и c без изменения эффективности.

Эта причина — замена одного решения другим — дает начальное представление о методе замены, который используется для доказательства опти- мальности правила отдаленного использования.

Прежде чем углубляться в анализ, стоит прояснить один важный момент. Все алгоритмы управления кэшем, упоминавшиеся выше, строят планы, которые включают элемент d в кэш на шаге i, если данные d запрашиваются на шаге i и d еще не находится в кэше. Назовем такой план сокращенным — он выполняет мини- мальный объем работы, необходимый для заданного шага. В общем случае можно представить себе алгоритм, который строит несокращенные планы, а элементы включаются в кэш на тех шагах, на которых они не запрашиваются. Теперь мы покажем, что для любого несокращенного плана существует сокращенный план, который не уступает ему.

Пусть S — план, который может не являться сокращенным. Новый план S — со- кращение S — определяется следующим образом: на каждом шаге на котором S включает в кэш незапрошенный элемент d, наш алгоритм построения ⅞ «притво- ряется», что он это делает, но в действительности оставляет d в основной памяти. Фактически d попадает в кэш на следующем шаге j после того, как элемент d был запрошен. В этом случае кэш-промах, инициированный S на шаге j, может быть отнесен на счет более ранней операции с кэшем, выполненной S на шаге i. Следо- вательно, мы приходим к следующему факту:

(4.11) Сокращенный план S заносит в кэш не больше элементов, чем план S.

Заметьте, что для каждого сокращенного плана количество элементов, включа- емых в кэш, точно совпадает с количеством промахов.

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

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

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