关卡回放已经知道完整资源访问顺序时,可以用它作为理想对照,看看普通缓存策略离最少加载还差多少。空间满了就优先淘汰未来最晚再次使用的资源,永远不会再用的资源排在最后。
本例规则与输入
本例每个资源占一个槽,缓存最初为空,命中不占加载次数,缺失后必须将所需资源放入缓存。空间已满时比较所有已缓存资源的下一次使用位置;从不再出现记为无穷远。同样远时淘汰编号较小者,以便复算。
4个等容量槽,访问串[1, 0, 1, 3, 5, 4, 5, 2, 3, 3, 2, 5, 0, 3, 5, 2, 0, 4, 1, 1, 2, 1];未来位置22表示本串不会再用。
逐步计算记录
位置、请求 | 命中 | 淘汰 | 候选下次使用 | 缓存 0,1 | False | None | [] | [1] 1,0 | False | None | [] | [0, 1] 2,1 | True | None | [] | [0, 1] 3,3 | False | None | [] | [0, 1, 3] 4,5 | False | None | [] | [0, 1, 3, 5] 5,4 | False | 1 | [[0, 12], [1, 18], [3, 8], [5, 6]] | [0, 3, 4, 5] 6,5 | True | None | [] | [0, 3, 4, 5] 7,2 | False | 4 | [[0, 12], [3, 8], [4, 17], [5, 11]] | [0, 2, 3, 5] 8,3 | True | None | [] | [0, 2, 3, 5] 9,3 | True | None | [] | [0, 2, 3, 5] 10,2 | True | None | [] | [0, 2, 3, 5] 11,5 | True | None | [] | [0, 2, 3, 5] 12,0 | True | None | [] | [0, 2, 3, 5] 13,3 | True | None | [] | [0, 2, 3, 5] 14,5 | True | None | [] | [0, 2, 3, 5] 15,2 | True | None | [] | [0, 2, 3, 5] 16,0 | True | None | [] | [0, 2, 3, 5] 17,4 | False | 0 | [[0, 22], [2, 20], [3, 22], [5, 22]] | [2, 3, 4, 5] 18,1 | False | 3 | [[2, 20], [3, 22], [4, 22], [5, 22]] | [1, 2, 4, 5] 19,1 | True | None | [] | [1, 2, 4, 5] 20,2 | True | None | [] | [1, 2, 4, 5] 21,1 | True | None | [] | [1, 2, 4, 5] 合计缺失并加载8次。
表中编号用于区分本例对象,不代表任何真实产品的默认规则。输入、处理顺序与边界约定都属于题目的一部分;请先按相同规则复算,再比较不同实现。分数保留精确值,若自行改用小数,应把显示舍入与实际计算误差分开。
独立核对方法
逐项表列出访问资源、命中与否、被淘汰对象和处理后的集合。独立验收会枚举缺失时所有合法淘汰选择,找出最低总加载次数,再与这次策略的结果比较。这种小规模枚举适合当作正确性对照。
不要把最近最少使用与未来最晚使用混为一谈,二者查看的时间方向不同。遇到最后一次访问以后不再需要的资源,留在缓存也可能没有坏处;只有真正发生满缓存缺失时才需要作出淘汰选择。
适用边界
这依赖已经知道未来,不能当成在线游戏加载器随时能做到的保证。资源大小、加载成本不同,或允许提前加载时,优化目标都会改变。本例只统计等大小资源的缺失次数,不估算硬盘速度或帧时间。
改变输入后,建议先找到第一处不同的中间结果,再追查它所依赖的条件。不要仅因为最后一个数看起来接近,就认定全过程相同。把原始记录、选择理由与边界情况保留下来,更容易区分机制差异和实现失误。
