16
правок
Изменения
Нет описания правки
{{Определение
|definition=
'''Кэш промах''' (англ. ''cache miss'') {{---}} результат обрабатываемого запроса отсутствует в кэше и чтобы его получить необходимо обращаться к внешней памяти. При получении ответа мы так же можем сохранить новое значение в кэш, вытеснив(удалив) некоторое старое.
}}
{{Определение
'''Временем работы алгоритма кэширования''' будем называть количество кэш промахов случившихся при обработке всех запросов.
}}
При анализе случайных алгоритмов под временем работы будем использовать подразумевать матожидание количества кэш промахов при всех возможных случайных выборах, но для фиксированной последовательности запросов.
{{Определение
|definition=
|id=def_a-opt
|definition=
'''<tex>\alpha</tex>-оптимальность''' {{---}} свойство онлайн алгоритма, означающее что время работы этого алгоритма на любых входных данных не более чем в <tex>\alpha</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>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>
