Участник:Vlad SG - История изменений

Vlad SG в 18:04, 27 января 2022

2022-01-27T18:04:08Z

Vlad SG в 17:48, 27 января 2022

2022-01-27T17:48:02Z

Vlad SG в 09:01, 27 января 2022

2022-01-27T09:01:34Z

Vlad SG в 08:41, 27 января 2022

2022-01-27T08:41:53Z

Vlad SG в 08:35, 27 января 2022

2022-01-27T08:35:43Z

Vlad SG в 08:29, 27 января 2022

2022-01-27T08:29:13Z

Vlad SG в 08:15, 27 января 2022

2022-01-27T08:15:57Z

Vlad SG в 08:09, 27 января 2022

2022-01-27T08:09:09Z

Vlad SG в 08:03, 27 января 2022

2022-01-27T08:03:27Z

Vlad SG в 07:45, 27 января 2022

2022-01-27T07:45:47Z

@@ Строка 9: / Строка 9: @@
 {{Определение
 |definition=
-'''Кэш промах''' (англ. ''cache miss'') {{---}} результат обрабатываемого запроса отсутствует в кэше и чтобы его получить необходимо обращаться к внешней памяти. При получении ответа мы так же можем сохранить новое значение в кэш, вытеснив(удалив) некоторое старое.
+'''Кэш промах''' (англ. ''cache miss'') {{---}} результат обрабатываемого запроса отсутствует в кэше и чтобы его получить необходимо обращаться к внешней памяти. При получении ответа мы можем сохранить новое значение в кэш, вытеснив(удалив) некоторое старое.
 }}
 {{Определение
@@ Строка 15: / Строка 15: @@
 '''Временем работы алгоритма кэширования''' будем называть количество кэш промахов случившихся при обработке всех запросов.
 }}
-При анализе случайных алгоритмов будем использовать матожидание количества кэш промахов при всех возможных случайных выборах, но для фиксированной последовательности запросов.
+При анализе случайных алгоритмов под временем работы будем подразумевать матожидание количества кэш промахов при всех возможных случайных выборах, но для фиксированной последовательности запросов.
 {{Определение
 |definition=
@@ Строка 27: / Строка 27: @@
 |id=def_a-opt
 |definition=
-'''<tex>\alpha</tex>-оптимальность''' {{---}} свойство онлайн алгоритма, означающее что время работы этого алгоритма на любых входных данных не более чем в <tex>\alpha</tex> раз больше, чем у любого оффлайнового, с точностью до аддитивной константы.
+'''<tex>\alpha</tex>-оптимальность''' {{---}} свойство онлайн алгоритма, означающее что время работы этого алгоритма на любых входных данных не более чем в <tex>\alpha</tex> раз больше, чем у оптимального оффлайнового алгоритма, с точностью до аддитивной константы.
 }}
@@ Строка 40: / Строка 40: @@
 Теперь построим <tex>\sigma_n</tex>. В последовательности будем использовать только <tex>k + 1</tex> различных запросов. Первыми <tex>k</tex> запросами возьмём любые различные, а дальше, каждым следующим запросом поставим тот, результата которого нет в данный момент в кэше детерминированного алгоритма. Это хоть и не явное, но корректное задание последовательности, потому что имея алгоритм, мы можем вычислить каждый запрос в <tex>\sigma_n</tex> на основе предыдущих. Очевидно, что <tex>T_\text{det}(\sigma_n) = n</tex>.
-Посмотрим как на <tex>\sigma_n</tex> будет работать следующий, возможно оптимальный оффлайн алгоритм (индекс mopt). Первые k элементов алгоритм добавит в кэш, так как они все различные. Когда случается промах, алгоритм среди значений в кэше и только что обработанного запроса вытесняет то, которое в последующих запросах встречается первый раз как можно позже или не встречается совсем. При таком выборе, следующий кэш промах случится не менее чем через <tex>k</tex> запросов. Предположим, что это не так, и кэш промах случился через <tex>m < k</tex> запросов. Так как количество различных запросов на 1 больше размера кэша, то этот промах произошёл на запросе, который мы вытеснили из кэша в предыдущий раз. Из <tex>m < k</tex> следует, что есть запросы, которые мы не встретили среди первых <tex>m</tex>, а значит их первое вхождение будет после того значения, которое мы вытеснили. Получили противоречие, а значит предположение не верно. Оценим время работы возможно оптимального оффлайн алгоритма <tex>T_\text{mopt} \leqslant k + \lceil\frac{n-k}{k+1}\rceil \leqslant \frac{n}{k}</tex>. Последнее неравенство выполнено, т.к. <tex>n \gg k</tex>. Очевидно <tex>T_\text{opt}(\sigma_n) \leqslant T_\text{mopt}(\sigma_n)</tex>, откуда <tex>T_\text{opt}(\sigma_n) \leqslant \frac{n}{k}</tex>
+Посмотрим как на входе <tex>\sigma_n</tex> будет работать следующий, возможно оптимальный оффлайн алгоритм (индекс mopt). Первые k элементов алгоритм добавит в кэш, так как они все различные. Когда случается промах, алгоритм среди значений в кэше и только что обработанного запроса вытесняет то, которое в последующих запросах встречается первый раз как можно позже или не встречается совсем. При таком выборе, следующий кэш промах случится не менее чем через <tex>k</tex> запросов. Предположим, что это не так, и кэш промах случился через <tex>m < k</tex> запросов. Так как количество различных запросов на 1 больше размера кэша, то этот промах произошёл на запросе, который мы вытеснили из кэша в предыдущий раз. Из <tex>m < k</tex> следует, что есть запросы, которые мы не встретили среди первых <tex>m</tex>, а значит их первое вхождение будет после того значения, которое мы вытеснили. Получили противоречие, а значит предположение не верно. Оценим время работы возможно оптимального оффлайн алгоритма <tex>T_\text{mopt} \leqslant k + \lceil\frac{n-k}{k+1}\rceil \leqslant \frac{n}{k}</tex>. Последнее неравенство выполнено, т.к. <tex>n \gg k</tex>. Очевидно <tex>T_\text{opt}(\sigma_n) \leqslant T_\text{mopt}(\sigma_n)</tex>, откуда <tex>T_\text{opt}(\sigma_n) \leqslant \frac{n}{k}</tex>
 <tex>T_\text{det}(\sigma_n) = n = k \cdot \frac{n}{k} \geqslant k \cdot T_\text{opt}(\sigma_n) \Rightarrow T_\text{det}(\sigma_n) \geqslant k \cdot T_\text{opt}(\sigma_n) + 0</tex>

@@ Строка 36: / Строка 36: @@
 Любой <tex>\alpha</tex>-оптимальный онлайн детерминированный алгоритм кэширования имеет <tex>\alpha \geqslant k</tex>.
 |proof =
-Обозначим <tex>T_\text{opt}(\sigma)</tex> и <tex>T_\text{det}(\sigma)</tex> как время работы оптимального и детерминированного алгоритма на входе <tex>\sigma</tex>. По определению <tex>\alpha</tex>-оптимальности имеем <tex>\forall\sigma \; T_\text{det}(\sigma) < \alpha \cdot T_\text{opt}(\sigma) + C</tex>. Покажем, что достаточно построить для любого <tex>n</tex> такую последовательность запросов <tex>\sigma_n</tex>, что <tex>T_\text{det}(\sigma_n) \geqslant k \cdot T_\text{opt}(\sigma_n) + C_0</tex>. Так как <tex>\lim\limits_{n->\infty}T = \infty</tex>, получаем <tex>\lim\limits_{n->\infty}\frac{T_\text{det}(\sigma_n)}{T_\text{opt}(\sigma_n)} \geqslant k</tex>. С другой стороны можно раскрыть квантор для значения <tex>\sigma_n</tex>: <tex>T_\text{det}(\sigma_n) < \alpha \cdot T_\text{opt}(\sigma_n) + C</tex>, а потом снова перейти к пределу <tex>\lim\limits_{n->\infty}\frac{T_\text{det}(\sigma_n)}{T_\text{opt}(\sigma_n)} \leqslant \alpha</tex>. Перепишем неравенства в следующем виде <tex>k \leqslant \lim\limits_{n->\infty}\frac{T_\text{det}(\sigma_n)}{T_\text{opt}(\sigma_n)} \leqslant \alpha</tex>, откуда очевидно, что <tex>\alpha \geqslant k</tex>.
+Обозначим <tex>T_\text{opt}(\sigma)</tex> и <tex>T_\text{det}(\sigma)</tex> как время работы оптимального и детерминированного алгоритма на входе <tex>\sigma</tex>. По определению <tex>\alpha</tex>-оптимальности имеем <tex>\forall\sigma \; T_\text{det}(\sigma) < \alpha \cdot T_\text{opt}(\sigma) + C</tex>. Покажем, что достаточно построить для любого <tex>n</tex> такую последовательность запросов <tex>\sigma_n</tex>, что <tex>T_\text{det}(\sigma_n) \geqslant k \cdot T_\text{opt}(\sigma_n) + C_0</tex>. Так как <tex>\lim\limits_{n->\infty}T = \infty</tex>, получаем <tex>\lim\limits_{n->\infty}\frac{T_\text{det}(\sigma_n)}{T_\text{opt}(\sigma_n)} \geqslant k</tex>. С другой стороны можно подставить в неравенство с квантором значение <tex>\sigma_n</tex> и получить <tex>T_\text{det}(\sigma_n) < \alpha \cdot T_\text{opt}(\sigma_n) + C</tex>, а потом снова перейти к пределу <tex>\lim\limits_{n->\infty}\frac{T_\text{det}(\sigma_n)}{T_\text{opt}(\sigma_n)} \leqslant \alpha</tex>. Перепишем неравенства в следующем виде <tex>k \leqslant \lim\limits_{n->\infty}\frac{T_\text{det}(\sigma_n)}{T_\text{opt}(\sigma_n)} \leqslant \alpha</tex>, откуда очевидно, что <tex>\alpha \geqslant k</tex>.
 Теперь построим <tex>\sigma_n</tex>. В последовательности будем использовать только <tex>k + 1</tex> различных запросов. Первыми <tex>k</tex> запросами возьмём любые различные, а дальше, каждым следующим запросом поставим тот, результата которого нет в данный момент в кэше детерминированного алгоритма. Это хоть и не явное, но корректное задание последовательности, потому что имея алгоритм, мы можем вычислить каждый запрос в <tex>\sigma_n</tex> на основе предыдущих. Очевидно, что <tex>T_\text{det}(\sigma_n) = n</tex>.

@@ Строка 36: / Строка 36: @@
 Любой <tex>\alpha</tex>-оптимальный онлайн детерминированный алгоритм кэширования имеет <tex>\alpha \geqslant k</tex>.
 |proof =
-Обозначим <tex>T_\text{opt}(\sigma)</tex> и <tex>T_\text{det}(\sigma)</tex> как время работы оптимального и детерминированного алгоритма на входе <tex>\sigma</tex>. По определению <tex>\alpha</tex>-оптимальности имеем <tex>\forall\sigma \; T_\text{det}(\sigma) < \alpha \cdot T_\text{opt}(\sigma) + C</tex>. Покажем, что достаточно построить для любого <tex>n</tex> такую последовательность запросов <tex>\sigma_n</tex>, что <tex>T_\text{det}(\sigma_n) \geqslant k \cdot T_\text{opt}(\sigma_n) + C_0</tex>. Так как <tex>\lim\limits_{n->\infty}T = \infty</tex>, получаем <tex>\lim\limits_{n->\infty}\frac{T_\text{det}(\sigma_n)}{T_\text{opt}(\sigma_n)} \geqslant k</tex>. С другой стороны можно квантор раскрыть для значения <tex>\sigma_n</tex>: <tex>T_\text{det}(\sigma_n) < \alpha \cdot T_\text{opt}(\sigma_n) + C</tex>, а потом снова перейти к пределу <tex>\lim\limits_{n->\infty}\frac{T_\text{det}(\sigma_n)}{T_\text{opt}(\sigma_n)} \leqslant \alpha</tex>. Перепишем неравенства в следующем виде <tex>k \leqslant \lim\limits_{n->\infty}\frac{T_\text{det}(\sigma_n)}{T_\text{opt}(\sigma_n)} \leqslant \alpha</tex>, откуда очевидно, что <tex>\alpha \geqslant k</tex>.
+Обозначим <tex>T_\text{opt}(\sigma)</tex> и <tex>T_\text{det}(\sigma)</tex> как время работы оптимального и детерминированного алгоритма на входе <tex>\sigma</tex>. По определению <tex>\alpha</tex>-оптимальности имеем <tex>\forall\sigma \; T_\text{det}(\sigma) < \alpha \cdot T_\text{opt}(\sigma) + C</tex>. Покажем, что достаточно построить для любого <tex>n</tex> такую последовательность запросов <tex>\sigma_n</tex>, что <tex>T_\text{det}(\sigma_n) \geqslant k \cdot T_\text{opt}(\sigma_n) + C_0</tex>. Так как <tex>\lim\limits_{n->\infty}T = \infty</tex>, получаем <tex>\lim\limits_{n->\infty}\frac{T_\text{det}(\sigma_n)}{T_\text{opt}(\sigma_n)} \geqslant k</tex>. С другой стороны можно раскрыть квантор для значения <tex>\sigma_n</tex>: <tex>T_\text{det}(\sigma_n) < \alpha \cdot T_\text{opt}(\sigma_n) + C</tex>, а потом снова перейти к пределу <tex>\lim\limits_{n->\infty}\frac{T_\text{det}(\sigma_n)}{T_\text{opt}(\sigma_n)} \leqslant \alpha</tex>. Перепишем неравенства в следующем виде <tex>k \leqslant \lim\limits_{n->\infty}\frac{T_\text{det}(\sigma_n)}{T_\text{opt}(\sigma_n)} \leqslant \alpha</tex>, откуда очевидно, что <tex>\alpha \geqslant k</tex>.
 Теперь построим <tex>\sigma_n</tex>. В последовательности будем использовать только <tex>k + 1</tex> различных запросов. Первыми <tex>k</tex> запросами возьмём любые различные, а дальше, каждым следующим запросом поставим тот, результата которого нет в данный момент в кэше детерминированного алгоритма. Это хоть и не явное, но корректное задание последовательности, потому что имея алгоритм, мы можем вычислить каждый запрос в <tex>\sigma_n</tex> на основе предыдущих. Очевидно, что <tex>T_\text{det}(\sigma_n) = n</tex>.
-Посмотрим как на <tex>\sigma_n</tex> будет работать следующий, возможно оптимальный оффлайн алгоритм (индекс mopt). Первые k элементов алгоритм добавит в кэш, так как они все различные. Когда случается промах, алгоритм среди значений в кэше и только что обработанного результата вытесняет то, которое в последующих запросах встречается первый раз как можно позже или не встречается совсем. При таком выборе, следующий кэш промах случится не менее чем через <tex>k</tex> запросов. Предположим, что это не так, и кэш промах случился через <tex>m < k</tex> запросов. Так как количество различных запросов на 1 больше размера кэша, то этот промах произошёл на запросе, который мы вытеснили из кэша в предыдущий раз. Из <tex>m < k</tex> следует, что есть запросы, которые мы не встретили среди первых <tex>m</tex>, а значит их первое вхождение будет после того значения, которое мы вытеснили. Получили противоречие, а значит предположение не верно. Оценим время работы возможно оптимального оффлайн алгоритма <tex>T_\text{mopt} \leqslant k + \lceil\frac{n-k}{k+1}\rceil \leqslant \frac{n}{k}</tex>. Последнее неравенство выполнено, т.к. <tex>n \gg k</tex>. Очевидно <tex>T_\text{opt}(\sigma_n) \leqslant T_\text{mopt}(\sigma_n)</tex>, откуда <tex>T_\text{opt}(\sigma_n) \leqslant \frac{n}{k}</tex>
+Посмотрим как на <tex>\sigma_n</tex> будет работать следующий, возможно оптимальный оффлайн алгоритм (индекс mopt). Первые k элементов алгоритм добавит в кэш, так как они все различные. Когда случается промах, алгоритм среди значений в кэше и только что обработанного запроса вытесняет то, которое в последующих запросах встречается первый раз как можно позже или не встречается совсем. При таком выборе, следующий кэш промах случится не менее чем через <tex>k</tex> запросов. Предположим, что это не так, и кэш промах случился через <tex>m < k</tex> запросов. Так как количество различных запросов на 1 больше размера кэша, то этот промах произошёл на запросе, который мы вытеснили из кэша в предыдущий раз. Из <tex>m < k</tex> следует, что есть запросы, которые мы не встретили среди первых <tex>m</tex>, а значит их первое вхождение будет после того значения, которое мы вытеснили. Получили противоречие, а значит предположение не верно. Оценим время работы возможно оптимального оффлайн алгоритма <tex>T_\text{mopt} \leqslant k + \lceil\frac{n-k}{k+1}\rceil \leqslant \frac{n}{k}</tex>. Последнее неравенство выполнено, т.к. <tex>n \gg k</tex>. Очевидно <tex>T_\text{opt}(\sigma_n) \leqslant T_\text{mopt}(\sigma_n)</tex>, откуда <tex>T_\text{opt}(\sigma_n) \leqslant \frac{n}{k}</tex>
 <tex>T_\text{det}(\sigma_n) = n = k \cdot \frac{n}{k} \geqslant k \cdot T_\text{opt}(\sigma_n) \Rightarrow T_\text{det}(\sigma_n) \geqslant k \cdot T_\text{opt}(\sigma_n) + 0</tex>
@@ Строка 60: / Строка 60: @@
 Будем рассматривать только те запросы, которые ставят метку в кэше. Из алгоритма понятно, что если запрос не ставит метку, то кэш работает с уже помеченным значением, а значит это кэш попадание. Разобьём эти запросы на фазы так, чтобы границей между фазами был запрос, который сбрасывает все пометки. Так, первый запрос в первой фазе {{---}} это первый запрос во всей последовательности, а первый запрос в других фазах {{---}} это запрос, выполняющий сброс всех пометок. Пронумеруем фазы от <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>.
+Посчитаем матожидание количества промахов на фазе <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>m_i</tex> и матожиданием промахов на старых значениях.
@@ Строка 66: / Строка 66: @@
 <tex>
 \begin{align}
-T_\text{rnd} &\leqslant \sum\limits_{i}\left(m_i + \sum\limits_{j}E(\text{кэш промах на}\; j)\right) = \\
+T_\text{rnd} &\leqslant \sum\limits_{i=1}^p\left(m_i + \sum\limits_{j}E(\text{кэш промах на}\; j)\right) = \\
-     &= \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=1}^p\left(m_i + \sum\limits_{j=1}^{k-m_i}\frac{m_i}{k-j+1}\right) = \sum\limits_{i=1}^p 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
+     &= \sum\limits_{i=1}^p m_i\left(1 + \sum\limits_{j=m_i+1}^{k}\frac{1}{j}\right) = \sum\limits_{i=1}^p m_i(1 + H_k - H_{m_i+1}) \leqslant \sum\limits_{i=1}^p m_iH_k = H_k\sum\limits_{i=1}^p m_i
 \end{align}
 </tex>
@@ Строка 77: / Строка 77: @@
 \begin{align}
 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 \\
+     &= \frac{1}{2}\left(E(\text{кэш промах на}\; 1) + E(\text{кэш промах на}\; p) + \sum\limits_{i=1}^{p-1}\left(E(\text{кэш промах на}\; i) + E(\text{кэш промах на}\; i+1)\right)\right) \geqslant \\
      &\geqslant \frac{1}{2}\sum\limits_{i=1}^{p}m_i
 \end{align}

@@ Строка 66: / Строка 66: @@
 <tex>
 \begin{align}
-E(T_\text{rnd}) &\leqslant \sum\limits_{i}\left(m_i + \sum\limits_{j}E(\text{кэш промах на}\; j)\right) = \\
+T_\text{rnd} &\leqslant \sum\limits_{i}\left(m_i + \sum\limits_{j}E(\text{кэш промах на}\; j)\right) = \\
      &= \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
@@ Строка 76: / Строка 76: @@
 <tex>
 \begin{align}
-E(T_\text{opt}) &= \sum\limits_{i=1}^{p}E(\text{кэш промах на}\; i) = \\
+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}m_i
 \end{align}
 </tex>
 == Источники ==

@@ Строка 78: / Строка 78: @@
 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
+     &\geqslant \frac{1}{2}\sum\limits_{i=1}^{p}m_i
 \end{align}
 </tex>

@@ Строка 62: / Строка 62: @@
 Посчитаем матожидание количества промахов на фазе <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_{i}\left(m_i + \sum\limits_{j \;\text{старый запрос фазы}\; i}E(\text{кэш промах на}\; j)\right) = \sum\limits_{i}\left(m_i + \sum\limits_{j \;\text{старый запрос фазы}\; 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</tex>
+<tex></tex>
 == Источники ==

@@ Строка 58: / Строка 58: @@
 == Оценка времени работы алгоритма ==
+Будем рассматривать только те запросы, которые ставят метку в кэше. Из алгоритма понятно, что если запрос не ставит метку, то кэш работает с уже помеченным значением, а значит это кэш попадание. Разобьём эти запросы на фазы так, чтобы границей между фазами был запрос, который сбрасывает все пометки. Так, первый запрос в первой фазе {{---}} это первый запрос во всей последовательности, а первый запрос в других фазах {{---}} это запрос, выполняющий сброс всех пометок. Рассмотрим фазу <tex>i</tex>. Разделим все значения на 2 множества: старые {{---}} которые были в фазу <tex>i-1</tex> и новые {{---}} все остальные. Обозначим количество новых значений в фазе <tex>i</tex> как <tex>m_i</tex>. Тогда количество старых будет <tex>k-m_i</tex>.
 == Источники ==