16
правок
Изменения
Нет описания правки
== Оценка времени работы алгоритма ==
Будем рассматривать только те запросы, которые ставят метку в кэше. Из алгоритма понятно, что если запрос не ставит метку, то кэш работает с уже помеченным значением, а значит это кэш попадание. Разобьём эти запросы на фазы так, чтобы границей между фазами был запрос, который сбрасывает все пометки. Так, первый запрос в первой фазе {{---}} это первый запрос во всей последовательности, а первый запрос в других фазах {{---}} это запрос, выполняющий сброс всех пометок. Пронумеруем фазы от <tex>1</tex> до <tex>p</tex>. Рассмотрим фазу <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>.
&= \sum\limits_{i}\left(m_i + \sum\limits_{j=1}^{k-m_i}\frac{m_i}{k-j+1}\right) = \sum\limits_{i}m_i\left(1 + \sum\limits_{j=1}^{k-m_i}\frac{1}{k-j+1}\right) = \\
&= \sum\limits_{i}m_i\left(1 + \sum\limits_{j=m_i+1}^{k}\frac{1}{j}\right) = \sum\limits_{i}m_i(1 + H_k - H_{m_i+1}) \leqslant \sum\limits_{i}m_iH_k = H_k\sum\limits_{i}m_i
\end{align}
</tex>
Теперь оценим снизу время работы оптимального алгоритма. Рассмотрим фазы <tex>i</tex> и <tex>i-1</tex>. Среди запросов этих фаз всего <tex>k + m_i</tex> различных значений, а потому оптимальный алгоритм обязан промахнуться хотябы <tex>m_i</tex> раз.
<tex>
\begin{align}
E(T_\text{opt}) &= \sum\limits_{i=1}^{p}E(\text{кэш промах на}\; i) = \\
&= \frac{1}{2}\left(\sum\limits_{i=1}^{p-1}\left(E(\text{кэш промах на}\; i) + E(\text{кэш промах на}\; i+1)\right) + E(\text{кэш промах на}\; 1) + E(\text{кэш промах на}\; p)\right) \geqslant \\
&\geqslant \frac{1}{2}\sum\limits_{i=1}^{p-1}m_i
\end{align}
</tex>
