# 参考解 · lab 0003 · 列表与字典的隐藏价格

**做完四个任务再打开这里。** 这里的四个 `.py` 与任务目录里的文件同名：
把它们拷进 `lab/0003-python-list-dict-cost/` 覆盖同名文件，再跑 `py run_tests.py`，应当四个任务全过。
（参考解是自包含的：不 import 任务目录里的任何东西，拷过去直接就能跑。）

## 逐个任务看什么

| 任务 | 参考解里补上的关键几行 | 要看的趋势 | 本机参考值（非通用） |
| --- | --- | --- | --- |
| 1 | 三段 `t0 = time.perf_counter()` / 循环 / `t1` / 相减 | 列表 `in` 要一个个比过去，集合与字典走哈希直接落位 | 列表 1.50 秒 / 集合 0.000018 秒 / 字典 0.000016 秒 |
| 2 | `q.pop(0)` 出队那段；`collections.deque()` + `append` + `popleft()` 那段 | 出队顺序一样，代价差两个数量级 | `pop(0)` 2.74 秒 / `popleft` 0.013 秒（约 200 倍） |
| 3 | `seen_set = set()` 与 `seen_set.add(x)`（只动这两处） | 结果一模一样，耗时从 `O(n^2)` 降到 `O(n)` | 列表版约 0.3-0.5 秒 / 集合版约 0.002-0.01 秒（差两个数量级） |
| 4 | 四个 `TODO` 位置各补一段计时 | 扩大十倍：列表涨约 10 倍、集合几乎不动 | 列表约 10 倍 / 集合约 1 倍 |

## 每个任务的「为什么」

- **任务 1**：`x in lst` 从头逐个比较，这 200 个目标都在末尾附近，所以每次几乎把整个列表扫完，是 $O(n)$；
  `x in s`、`x in d` 先算哈希值、直接算出该去哪个槽位，平均 $O(1)$，与元素个数无关。
  两行数字差约 5 个数量级——这就是「换容器」能救回一道超时题的原因。
- **任务 2**：列表元素挨着放，`pop(0)` 拿走头元素后剩下 n-1 个都要往左挪一格，一次 $O(n)$、出 n 个 $O(n^2)$；
  `deque` 是双端队列，`popleft()` 只挪队头指针，$O(1)$。两者出队顺序都是先进先出——
  换 `deque` 改的只是代价，不是行为。
- **任务 3**：列表版每来一个元素都要把 `seen` 从头扫一遍（最坏 n 次比较），总共 $O(n^2)$；
  集合版每次 `in` 平均 $O(1)$，总共 $O(n)$。注意 `x in seen` 那一行**不用改**——
  要换的是容器，不是查法。
- **任务 4**：「放大十倍」是把复杂度变成能看见的东西：$O(n)$ 的列表 `in` 涨十倍，
  $O(1)$ 的集合 `in` 基本不动。估算与实测对上了，你就有了一把自己机器的尺子。

## 常见错法（对照自己的写法）

- 计时把 `t0` / `t1` 夹在造数据的两侧，把造数据的时间也算进出（数值大得离谱）。
- 两个 `TODO` 段之间忘了隔开：第二段的 `t0` 跟在第一段之后没重置，量出来的是累计时间。
- 集合版里 `in` 的容器换了、但新元素还在 `append`（集合没有 `append`，会 `AttributeError`）。
- 空集合写成 `seen_set = {}`——那建的是**空字典**，`add` 会报错。
- `deque` 出队写成 `pop()`：出的是右端（后进先出），`出队顺序一致` 会变 `False`。
- `deque` 按下标访问中间是 $O(n)$——需要频繁随机访问时该用列表，`deque` 只赢在两端。