16
правок
Изменения
Нет описания правки
Посчитаем матожидание количества промахов на фазе <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></tex> <tex>\begin{align}E(T_\text{rnd}) &= \sum\limits_{i}\left(m_i + \sum\limits_{j \;\text{старый запрос фазы}\; i}E(\text{кэш промах на}\; j)\right) = \\ &= \sum\limits_{i}\left(m_i + \sum\limits_{j \;\text=1}^{старый запрос фазы}\; ik-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}) \geqslant \sum\limits_{i}m_iH_k = H_k\sum\limits_{i}m_i\end{align}</tex>
== Источники ==
