03篇把一次操作的昂贵成本放进整个序列分析，16篇比较了缓存替换策略。在线分析再加一个信息限制：处理当前请求时，算法看不到未来请求，却要与知道完整序列的离线最优作比较。

比较必须固定同一个输入序列、同样的资源和成本口径。若在线算法只有两个缓存页，参照却有无限容量，所得差距不能直接叫作同容量竞争比；若只报告某条轨迹的平均命中率，也没有得到对所有序列成立的保证。

租到哪天才买

每天租用成本为1，一次购买成本为整数B≥1，买后无需再付租金。总使用天数T是非负整数，每天开始时知道当天要使用，但不知道以后还要用多少天。当天选择购买就不再同时付租金。

离线算法知道T，最优成本为OPT(T)=min(T,B)。在线策略先租B−1天；若第B天仍需使用，就当天购买。T=0时不做任何操作，成本0。

若T<B，在线成本也是T，与离线相同。若T≥B，在线总成本是B−1+B=2B−1，而离线成本是B。因此对每个T都满足ALG(T)≤(2−1/B)OPT(T)。B=1时第一天直接购买，因子恰为1；T=0不需要计算0/0。

这里给的是纯乘法保证，没有加法常数。固定B后，若允许任意依赖B的加法常数，就能把有限购买成本吸收到常数项中。这个一次性问题的乘法比较便失去原意。

确定性策略为什么无法更好

一个确定性策略在连续使用的输入上，有一个首次购买日d，或者永不购买。在尚未结束之前，它观察到的历史只是“今天还要用”，所以不同总天数的共同前缀不能透露未来。

若d≤B，让输入恰好使用d天。策略花B+d−1，离线花d，比值为1+(B−1)/d，至少2−1/B。若d>B，让输入使用d天，离线花B，策略比值至少2。永远租用则在T增长时比值无界。

所以第B天购买在这个离散、确定性、无折扣模型下达到最优竞争因子。下界输入可以在看完确定性策略后构造，但一旦构造便是固定序列；不需要声称用户真的按某个恶意过程租赁。

32篇的随机化在这里也可能改变保证，不过要先规定对手是否能观察随机选择并据此决定停止时间。本篇不实现随机租赁，也不把确定性下界直接用于所有随机算法。

缓存比较需要一致的规则

输入是一串页面编号σ，缓存最多容纳k≥1页，在线和离线都从空缓存开始。命中成本0，缺页成本1；采用按需调页，处理完一次请求后，该请求页驻留缓存，不允许预先免费载入未来页面。

LRU在缺页且缓存满时，淘汰最久未被访问的页。离线OPT知道剩余全部请求，淘汰下一次使用最晚、或以后不再使用的页。16篇已经提供这两个接口，本篇复用它们，避免另外定义一个不一致的“最优缓存”。

对每条请求序列，竞争保证允许一个与序列长度无关的加法项β：LRU(σ)≤ρOPT(σ)+β。下面证明ρ=k、β=k足够。这是缺页次数的最坏序列保证，不是平均命中率，不是LRU维护链表所需CPU时间，也不要求请求独立同分布。

按至多k种页面划分阶段

从序列开头取最长前缀，使其中至多有k种不同页面，作为第一阶段。遇到第k+1种页面时开启下一阶段，继续同样划分。除最后一阶段外，每阶段恰有k种页面；下一阶段的第一页不属于前一阶段。

LRU在同一阶段里，每种页面至多缺页一次。某页在该阶段已经访问后，要在再次访问前被LRU淘汰，必须有至少k个不同的其他页面变得比它更新；阶段内总共至多k种页面，不可能满足。于是每阶段最多k次缺页。若共有P个非空阶段，LRU≤kP。

给阶段起点记为t_1到t_P。对每个i<P，考察请求时间区间(t_i,t_{i+1}]，不包含前一阶段的首个请求，包含下一阶段的首个请求。离线算法在这个区间至少缺页一次。

证明采用反证：处理完t_i后，缓存已经含有t_i请求页。若直到t_{i+1}都不缺页，整个区间所需页面必须都已在该缓存中；加上t_i页，需要容纳前一阶段的k种页面和下一阶段那个新页面，共k+1种，超过容量。

这些半开区间互不重叠，因此可以把下界相加，得到OPT≥P−1。结合LRU≤kP，有LRU≤kOPT+k。不能只说“相邻两阶段共k+1种页面，所以每阶段OPT至少缺一次”，那会把同一边界缺页重复计入多个下界。

空序列P=0时双方成本均0，单独成立。这个证明的+k已经足够，本篇不借有限枚举结果把它擅自删掉，也不将k称为与容量无关的常数。

一条轨迹的胜负不决定竞争比

循环请求k+1种页面时，LRU可能几乎每次都缺页；离线能利用未来信息保留更合适的页面。相反，重复请求单一页面，两者都只需首次缺页。这些例子说明结果依赖轨迹，却没有单独证明任何普适竞争界。

如果测量程序把预热阶段排除在LRU成本之外，却把离线从空缓存开始计费，比较条件也被改变。缓存容量、初始状态、请求序列和计费区间都必须在记录里保留。

将页面大小设为不同值、允许不同加载成本，或允许绕过缓存直接服务请求，会形成其他模型。上面的k种页面分阶段证明依赖单位页、单位缺页成本及服务后驻留条件，不能自动迁移。

可复跑检查

examples/advanced-algorithms/online_cost.py提供ski_rental(days, buy_cost)，用闭式公式计算上述固定在线策略在长度T上的成本，不用未来信息改变购买规则；计算只需常数次整数操作，位成本另计。

paging_costs(trace, k)复用16篇cache_layout.py中的lru_misses与opt_misses，并返回最大阶段数P。设请求数为L，分阶段扫描需要O(L)期望哈希操作、O(k)集合空间；离线参照逐次向后查找下一次出现，保留原实现O(L²k)的CPU工作上界。这个慢参照用于教学核对，不是推荐的高速缓存模拟器。

1
python3 examples/advanced-algorithms/check_online_cost.py

本轮检查310个租赁实例：枚举从不购买或在某一天首次购买，独立得到离线最优；检查6681个长度不超过6、容量为1–3的分页序列。分页参照用记忆化搜索枚举所有合法淘汰选择，不调用最远未来规则，结果与复用的OPT一致。LRU≤kP、OPT≥P−1及竞争不等式分别检查，另有3个非法输入拒绝。

循环k+1种页面20轮的模拟中，k=1、2、3时，请求长度分别为40、60、80；LRU缺页40、60、80次，离线OPT缺页40、31、29次。这些是逻辑缺页计数，不是硬件缓存或运行耗时。原始结果保存于writing-plans/advanced-algorithms/evidence/online-cost-results.json；有限序列检查不能替代前述一般竞争证明。

练习

  1. B=5时分别列出第4、5、6天才购买的策略，在T=4、5、6和20时的成本。找出足以区分三种策略最坏表现的停止时间。
  2. k=2、请求序列为a,b,a,c,b,c,a。按正文划分阶段，列出互不重叠的(t_i,t_{i+1}]区间，再手算LRU和离线OPT缺页数。

参考资料