Анализ алгоритмов маркировки

В этом разделе мы рассмотрим метод анализа алгоритмов маркировки, а в конце будет приведена оценка сложности, применимая ко всем алгоритмам маркировки. После этого при введении рандомизации этот анализ нужно будет усилить.

Рассмотрим произвольный алгоритм маркировки, работающий с последовательностью обращений σ. Для анализа представим оптимальный алгоритм кэширования, который работает с σ параллельно с этим алгоритмом разметки и обеспечивает общую стоимость f (σ).

Предположим, последовательность σ состоит из r фаз, определяемых алгоритмом маркировки. Чтобы упростить рассмотрение анализа, мы «дополним» последовательность σ в начале и в конце дополнительными обращениями: никаких лишних кэш-промахов в оптимальном алгоритме они не создадут (то есть не приведут к увеличению f (σ)), поэтому любая граница, доказанная для эффективности алгоритма маркировки относительно оптимума дополненной последовательности, также будет применима к σ.

А конкретно перед первой фазой вставляется «фаза 0», в которой запрашиваются все элементы, изначально находящиеся в кэше. Это никак не влияет на стоимость алгоритма маркировки или оптимального алгоритма.

Также можно представить, что за завершающей фазой r следует эпилог, в котором каждый элемент, находящийся в кэше оптимального алгоритма, запрашивается дважды по кругу. Значение f (σ) при этом не увеличивается, а к концу второго прохода в алгоритме маркировки каждый элемент будет находиться в кэше и каждый будет помечен.

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

Деление последовательности обращений σ на фазы играет ключевую роль для получения границ. Прежде всего, история фазы с точки зрения алгоритма маркировки выглядит так: в начале фазы все элементы не помечены.

Любой элемент, к которому происходит обращение в фазе, помечается маркером и затем остается в кэше в оставшейся части фазы. В ходе фазы количество помеченных элементов растет с 0 до k, а следующая фаза начинается с обращения к (k + 1)-му элементу, отличному от всех помеченных. Некоторые выводы из этого описания представлены в следующем утверждении:

(13.35) В каждой фазе σ содержит обращения ровно к k разным элементам. Последующая фаза начинается с обращения к другому (k + 1)-му элементу.

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

(13.36) Алгоритм маркировки порождает не более k промахов за фазу и не более kr промахов за все r фаз.

Для нижней границы оптимума имеется следующий факт:

(13.37) Оптимум порождает не менее r − 1 промахов. Другими словами,

f (σ) ≥ r − 1.

Доказательство. Рассмотрим любую фазу, кроме последней, в ситуации непосредственно после первого обращения (к элементу s) в этой фазе. В настоящий момент s находится в кэше, поддерживаемом оптимальным алгоритмом, и из (13.35) следует, что в оставшейся части этой фазы произойдут обращения к k – 1 другим элементам, а в первом обращении следующей фазы также произойдет обращение к k-му другому элементу. Обозначим S это множество из k элементов, отличных от s.

Заметим, что по крайней мере один из элементов S в настоящее время не находится в кэше, поддерживаемом оптимальным алгоритмом (так как после s остается место только для k – 1 других элементов), и в оптимальном алгоритме при первом обращении к этому элементу произойдет кэш-промах.

Узнай цену консультации

"Да забей ты на эти дипломы и экзамены!” (дворник Кузьмич)