HW5：前缀命中与容量推导

先修：第 10 讲、Lab4、HW2。沿用原 15 周蓝图中的 HW5 编号，不代表 HW3/4 已发布。预计 2–3 小时。编辑 course/hw/hw05/hw05.py，只用标准库，不修改测试与 reference。

以下命令从课程根目录 deepinfer/ 执行；该目录包含 course/。个人主页源码仓库中的对应目录是 _courses/deepinfer/。每题先提交纸笔预测，再实现、运行、解释差异。

1. 公共契约：验证不因空输入而消失

所有数量、token ID、时间戳是非负整数且排除 bool；B 必须为正整数。列表内容必须完整验证。所有函数保留输入，要求返回列表时返回新列表；规定的非法输入抛 ValueError。不要因为另一边为空或当前没有候选，就忽略非法输入。

2. Q1：最长公共前缀，不是相同子串

prefix_hit_tokens(cached, query, block_size)：两个输入为 token ID 列表，空列表合法。返回从位置 0 起的公共前缀中完整块的 token 数。

按三个台阶思考：

1. 暂不考虑块，逐对比较，遇到首个差异就停，得到 common。
2. 将 common 向下对齐到 B 的倍数，而不是向上取整。
3. 把完整输入验证放在可能提前返回之前，包括短序列无法配对的尾部。

手算 cached=[1,2,3,4,5]、query=[1,2,3,9]、B=2：前三个位置相同，common=3；一个完整块，结果 2，不是 3 或 4。自造反例应体现“首位不同、后面相同”，而不只是两个完全不同的列表。

检查点：相同列表 [1,2,3] 在 B=2 下只能命中 2；[True] 对 [] 必须报错。如果最后一例返回 0，重点检查是不是只验证了 zip 遍历到的位置。

python course/tools/grade.py hw05 --question q1 --unlock
python course/tools/grade.py hw05 --question q1 --failfast
python course/tools/grade.py hw05 --question q1 --hint 1

3. Q2：先画每条私有尾部，再求和

shared_prefix_slots(lengths, prefix_tokens, block_size)：lengths 是请求长度列表；P 是 B 的倍数，且不超过任一长度。公共前缀只存一份，每条私有后缀分别向上取整。没有请求返回 0，但仍验证公共参数。

推导步骤：先算每条 length−P，再算每条私有页数，再乘 B 转槽位，最后加一份 P。不要把所有尾长先相加。这里没有额外常驻前缀副本，与 HW2 某个缓存开销情景口径不同。

手算总量为 4+4+4+8=20，不共享为 8+8+12=28。请再独立写两张小表：全部长度等于 P；P=0。它们应该分别退化为一份前缀和普通逐请求分页。

最小反例：[1,1]、P=0、B=4 需要 8 槽，不是 4。边界检查：[]、P=4、B=4 返回 0；P=1 则非法；[3]、P=4 也非法。只用整数运算，[2**60+1]、P=0、B=16 应为 2**60+16。

调试时输出三列中间量：私有长度、私有页数、私有槽位。若少了一整页，先查取整；若多了 P，先查是否数了额外前缀副本；若非法空输入没有报错，查早返回的位置。

4. Q3：先决定资格，再决定顺序

eviction_order(refcounts, last_used)：两个等长列表，位置就是物理 ID。只返回 refs=0 的 ID，排序键为 (last_used[ID], ID)，升序。空输入返回 []。不改引用数、不删除缓存条目，真正淘汰由调用者完成。

refs=[1,0,0,0]、times=[0,9,3,3]：先排除仍在使用的 0；剩余 1、2、3；按时间得到 2、3 在前，同时间按 ID，结果 [2,3,1]。如果得到 [0,2,3,1]，错在资格筛选，不在排序方向。

检查点：全有引用时返回空列表；refs=[0,2,0]、times=[7,0,7] 得 [0,2]；两列表长度不等必须报错。再自行设计一例，证明排序不应该改变原列表。

5. 从通过测试到解释结论

python course/tools/grade.py hw05

每题仍为 10 分：代码 5、推导 3、反例 2，总分 30，仅用于本 Unit2 批次验收。交付实现、三个手算、一个失败后修复记录。记录必须包含最小输入、期望、实际、根因、回归命令，不能只写“修复了一个 bug”。

出口自测：两个负载的请求命中率同为 50%，为何 token 命中率可以差很多？节省 8 槽为何不等于某个固定加速比？refs=0 为何不意味着旧内容被擦除？