小型图块缓存中先进先出与最近使用淘汰：4格缓存的十八次图块访问·练习02

反复访问几个图块时，缓存可以避免重复装入。容量有限时，按最早装入淘汰和按最久没用淘汰会保留不同内容；命中时是否更新顺序，是两种方案的重要差别。

本篇使用一组可以手算或逐行复查的虚构游戏记录。先读清操作顺序与边界，再看完整过程；它不是某一款现有游戏的隐藏公式，也不要求读者安装工具。

规则与输入

空缓存开始，每次访问一个符号图块。命中不新增数据；先进先出模式命中不改顺序，最近使用模式把命中的图块移到末尾。未命中时若已满，先删最前项再装入末尾，各模式独立记录。

容量4，访问顺序['E', 'A', 'A', 'D', 'F', 'G', 'A', 'C', 'A', 'G', 'B', 'C', 'A', 'F', 'A', 'A', 'C', 'F']

逐步计算与结果

请求1访问E，先进先出[命中,淘汰,队列][False, None, ['E']]；最近使用[命中,淘汰,队列][False, None, ['E']]。队列最前为下次满容量未命中时的淘汰对象。

请求2访问A，先进先出[命中,淘汰,队列][False, None, ['E', 'A']]；最近使用[命中,淘汰,队列][False, None, ['E', 'A']]。队列最前为下次满容量未命中时的淘汰对象。

请求3访问A，先进先出[命中,淘汰,队列][True, None, ['E', 'A']]；最近使用[命中,淘汰,队列][True, None, ['E', 'A']]。队列最前为下次满容量未命中时的淘汰对象。

请求4访问D，先进先出[命中,淘汰,队列][False, None, ['E', 'A', 'D']]；最近使用[命中,淘汰,队列][False, None, ['E', 'A', 'D']]。队列最前为下次满容量未命中时的淘汰对象。

请求5访问F，先进先出[命中,淘汰,队列][False, None, ['E', 'A', 'D', 'F']]；最近使用[命中,淘汰,队列][False, None, ['E', 'A', 'D', 'F']]。队列最前为下次满容量未命中时的淘汰对象。

请求6访问G，先进先出[命中,淘汰,队列][False, 'E', ['A', 'D', 'F', 'G']]；最近使用[命中,淘汰,队列][False, 'E', ['A', 'D', 'F', 'G']]。队列最前为下次满容量未命中时的淘汰对象。

请求7访问A，先进先出[命中,淘汰,队列][True, None, ['A', 'D', 'F', 'G']]；最近使用[命中,淘汰,队列][True, None, ['D', 'F', 'G', 'A']]。队列最前为下次满容量未命中时的淘汰对象。

请求8访问C，先进先出[命中,淘汰,队列][False, 'A', ['D', 'F', 'G', 'C']]；最近使用[命中,淘汰,队列][False, 'D', ['F', 'G', 'A', 'C']]。队列最前为下次满容量未命中时的淘汰对象。

请求9访问A，先进先出[命中,淘汰,队列][False, 'D', ['F', 'G', 'C', 'A']]；最近使用[命中,淘汰,队列][True, None, ['F', 'G', 'C', 'A']]。队列最前为下次满容量未命中时的淘汰对象。

请求10访问G，先进先出[命中,淘汰,队列][True, None, ['F', 'G', 'C', 'A']]；最近使用[命中,淘汰,队列][True, None, ['F', 'C', 'A', 'G']]。队列最前为下次满容量未命中时的淘汰对象。

请求11访问B，先进先出[命中,淘汰,队列][False, 'F', ['G', 'C', 'A', 'B']]；最近使用[命中,淘汰,队列][False, 'F', ['C', 'A', 'G', 'B']]。队列最前为下次满容量未命中时的淘汰对象。

请求12访问C，先进先出[命中,淘汰,队列][True, None, ['G', 'C', 'A', 'B']]；最近使用[命中,淘汰,队列][True, None, ['A', 'G', 'B', 'C']]。队列最前为下次满容量未命中时的淘汰对象。

请求13访问A，先进先出[命中,淘汰,队列][True, None, ['G', 'C', 'A', 'B']]；最近使用[命中,淘汰,队列][True, None, ['G', 'B', 'C', 'A']]。队列最前为下次满容量未命中时的淘汰对象。

请求14访问F，先进先出[命中,淘汰,队列][False, 'G', ['C', 'A', 'B', 'F']]；最近使用[命中,淘汰,队列][False, 'G', ['B', 'C', 'A', 'F']]。队列最前为下次满容量未命中时的淘汰对象。

请求15访问A，先进先出[命中,淘汰,队列][True, None, ['C', 'A', 'B', 'F']]；最近使用[命中,淘汰,队列][True, None, ['B', 'C', 'F', 'A']]。队列最前为下次满容量未命中时的淘汰对象。

请求16访问A，先进先出[命中,淘汰,队列][True, None, ['C', 'A', 'B', 'F']]；最近使用[命中,淘汰,队列][True, None, ['B', 'C', 'F', 'A']]。队列最前为下次满容量未命中时的淘汰对象。

请求17访问C，先进先出[命中,淘汰,队列][True, None, ['C', 'A', 'B', 'F']]；最近使用[命中,淘汰,队列][True, None, ['B', 'F', 'A', 'C']]。队列最前为下次满容量未命中时的淘汰对象。

请求18访问F，先进先出[命中,淘汰,队列][True, None, ['C', 'A', 'B', 'F']]；最近使用[命中,淘汰,队列][True, None, ['B', 'A', 'C', 'F']]。队列最前为下次满容量未命中时的淘汰对象。

先进先出命中9次，最近使用命中10次；结果只适用于本组访问顺序。

怎样独立复核

用访问历史独立确定候选：先进先出比较当前条目最近一次装入时刻，最近使用比较当前条目最近一次访问时刻。命中数加未命中数始终等于请求数，缓存内编号不重复且不超过容量。

本例把各图块大小视为相等，不计算装入耗时和并发请求。命中更高也不直接保证真实程序更快，还要考虑管理开销。本例只用于读懂淘汰差异，不对任何现有游戏缓存实现作假设。

练习时可以只改变一个输入，再预测哪一步会最先改变。保留中间记录，检查空状态、相等数值和刚好落在边界的情况。最终结果碰巧相同，并不能证明两个过程等价；反过来，采用不同规则得出不同结果，也不应立即视作程序故障。