16
правок
Изменения
Нет описания правки
== Оценка времени работы алгоритма ==
Будем рассматривать только те запросы, которые ставят метку в кэше. Из алгоритма понятно, что если запрос не ставит метку, то кэш работает с уже помеченным значением, а значит это кэш попадание. Разобьём эти запросы на фазы так, чтобы границей между фазами был запрос, который сбрасывает все пометки. Так, первый запрос в первой фазе {{---}} это первый запрос во всей последовательности, а первый запрос в других фазах {{---}} это запрос, выполняющий сброс всех пометок. Рассмотрим фазу <tex>i</tex>. Разделим все значения на 2 множества: старые {{---}} которые были в фазу <tex>i-1</tex> и новые {{---}} все остальные. Обозначим количество новых значений в фазе <tex>i</tex> как <tex>m_i</tex>. Тогда количество старых будет <tex>k-m_i</tex>. Посчитаем матожидание количества промахов на фазе <tex>i</tex>. Оно максимально, когда в фазе сначала идут новые значения, а потом старые, потому что тогда каждое новое значение имеет шанс вытеснить старое, и при обращении к нему случится кэш промах. Так как на начало фазы <tex>i</tex> в кэше хранятся только значения фазы <tex>i-1</tex>, то понятно, что все новые запросы фазы <tex>i</tex> приведут к кэш промаху. Рассмотрим <tex>j</tex>-й среди старых запросов. Посмотрим на те значения фазы <tex>i-1</tex>, которые к текущему моменту были вытеснены или помечены. <tex>j-1</tex> старых значений пометили сами себя, потому что они были в предыдущей фазе, а <tex>m_i</tex> пометить себя не могли, а поэтому вытеснили случайное подмножество из остальных <tex>k - (j-1)</tex>. Возможно они вытеснили кого-то из первых <tex>j-1</tex> старых значений, которые при обработке вытеснили кого-то другого. Главное, что распределение это не меняет. Вероятность того, что <tex>j</tex>-й старый запрос приведёт к кэш промаху, равена тому, что он был вытеснен из кэша <tex>P_j = \frac{m_i}{k - (j - 1)}</tex>. <tex>E(T_\text{rnd}) = \sum\limits_{p \text{фаза}}\left(m_i + \sum\limits_{j \text{старый запрос} p}E(p)\right)</tex>
== Источники ==
