知识卡片

普通读书笔记卡 · 3627.a.2

最远未来逐出有最优交换证据

理解等级:高级

离线缓存满且未命中时,任一最优方案若逐出别的块,可改为逐出未来最晚再访问的块。

两方案在此期间至多相差一个缓存块;若改后在该块下次请求时多一次未命中,之前必有一次相反的命中差补偿,之后状态重新一致。因此总未命中数不增。

这张卡片看不懂?

已有反馈 · 0 / 10 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    • 第15章 贪心算法 · 查看原书依据

      We conclude that if solution S has a cache hit and solution S′ has a cache miss upon the request for block bm, then some earlier request had the opposite result, and so solution S′ produces no more cache misses than solution S. Since S is assumed to be optimal, S′ is optimal as well.

    参考来源

    - 位置:《算法导论(第4版)》第15章《贪心算法》(OEBPS/chapter015.xhtml,文本字符[65000,70000))。 - 结论依据:定理15.5 以任一最优策略 S 与改为逐出最晚再用块的 S′ 比较;归纳保持两缓存至多差一块,若目标时刻 S′ 多未命中,之前有相反差额补偿。 - 原始内容:We conclude that if solution S has a cache hit and solution S ′ has a cache miss upon the request for block b m , then some earlier request had the opposite result, and so solution S ′ produces no more cache misses than solution S . Since S is assumed to be optimal, S ′ is optimal as well.