第 11 讲 · 讲义
课件的每一页，配上讲这一页时说的话。幻灯片是网页原生渲染的，文字可以选中、可以搜索，也可以直接打印。
L10结束于三个问题：实现要做多少工作、失败归谁处理、凭什么相信它是对的。本讲分别回答。
分两个45分钟；后面32页完整机制与旧例供课后查阅，不计入课堂必讲。
| Way 方式 | Symptom 症状 | This lecture 本讲的应对 |
|---|---|---|
| Too slow | small data is fine, real data never finishes | growth and cost |
| It crashes | unexpected input ends the program | exception handling |
| Quietly wrong | no error, wrong answer | assertions and tests |
三种失败对应三种证据，后面每一段回收一条。
三者看起来无关，其实是同一个问题的三个面：凭什么说这段程序真的可用。
真实世界不承诺输入合法、数据干净、规模不大；这一讲给三种证据。
| Run 运行 | Observed 观察 |
|---|---|
| Small sample | both finish instantly |
| Full file | one finishes, one does not |
先回答：凭什么说其中一个更好？What makes one of them better?
先不给代码，只给两种实现在一小段和完整数据上的表现。让学生说出判断依据。
计时是最直接的做法，但下一页用一道题把这个依据变成可检验的问题。
开场只考已经学过的循环与函数，不涉及复杂度记号。
先让学生动手数一遍，第9页回顾原题分布，不重复提交。
顺序由问题推进：先量化成本，再处理可预期的失败，然后检查不该发生的错误，最后用在本周作业上。
没有单独的AI政策页；第11周实验按Level 1要求声明。
本讲与第12周同属第五部分。本讲负责成本、异常与测试；第12周处理随机数、编码与文件。
先建立「工作量」这个可比较的量，再谈失败和证据。
先承认计时的作用，再说明它为什么不能单独作为比较依据。
替代方案是数步数：只依赖输入规模，不依赖机器。
| What changes 影响因素 | Why it matters 为什么影响结论 |
|---|---|
| Machine speed | the same code takes different seconds on different laptops |
| Background load | the number moves when the machine is busy |
| Interpreter version | a newer CPython optimizes different things |
| Input value | same size, different data, different work |
计时只回答「这一次多久」，不回答「这个算法多贵」。
同一段代码在不同条件下差别明显，计时给出的结论不稳固。
所以需要一个与机器无关的量：数基本操作的次数。下一页给出这个量。
total = 0 once, for runs n times, the body once per pass, return once回顾开场题：内层一共 6 次，就是把每一步加起来的结果。
步数只依赖输入规模。把 n+2 换成 n²，两者的差别在下一页用表讲清楚。
| Expression 表达式 | Kept 保留 | Dropped 丢掉 |
|---|---|---|
| n^2 + 3n + 5 | n^2 | 3n and 5 are lower order |
| 5n | n | the constant factor 5 |
| 100n | n | a bigger constant is still a constant |
| 3 | 1 (written O(1)) | no n at all |
O(...) 描述形状；具体多少步要看实现。
只关心 n 很大时的趋势，所以去掉低阶项和常数系数。
这是描述增长形状，不是精确步数：O(n) 不意味着正好 n 步。
O(1) a[i] · O(log n) binary search · O(n) walking a list · O(n log n) sorted(a) · O(n^2) a loop inside a loop · O(2^n) naive recursive Fibonacci. 曲线只表示形状，不是实测点。
这张图是本讲的坐标系：阶数越高，曲线越早离开底部。右边一列例子全是学生已经写过的代码，不是新知识。
下一页给一个本机的量级锚点，让他们能估算一个规模跑不跑得完。
| Measurement 测量 | n | Best of 3 取最小 |
|---|---|---|
| Python loop | 3,000,000 steps | 0.043 s |
| Built-in sum | 2,000,000 items | 0.012 s |
| Steps per second | — | about 7 x 10^7 |
Measured on the build machine 本机构建时实测，同一进程内重复取最小值。
这个数字是 Python 级循环的口径：一秒约七千万次循环体。
由此可以估算：n=10^6 的 O(n) 约 0.01 秒；同样规模的 O(n^2) 是 10^12 步，要跑几个小时。内置函数在 C 中执行，会快一到两个数量级，所以这个锚点是下界。
1 def value_at(numbers: list[int], index: int) -> int: 2 total = 0 3 for i in range(len(numbers)): 4 total += 100 * i 5 return total + numbers[index]
先投票：一个常数很大的线性循环，和一个什么都没有的常数操作，谁更贵。
本页只看单次调用的表面，下一页让 n 变大再比较。
| n | 100n (O(n)) | n^2 (O(n^2)) | Smaller 更少的一方 |
|---|---|---|---|
| 10 | 1,000 | 100 | O(n^2) |
| 100 | 10,000 | 10,000 | tie |
| 1,000 | 100,000 | 1,000,000 | O(n) |
| 10,000 | 1,000,000 | 100,000,000 | O(n) |
常数大只输在小规模；阶数高迟早输。
n
| Operation 操作 | Cost 复杂度 | Note 说明 |
|---|---|---|
| a[i], len(a) | O(1) | position is computed, length is stored |
| a.append(x), a.pop() | O(1) | touches the end only |
| a.insert(0, x), a.pop(0) | O(n) | everything after shifts |
| x in a (list) | O(n) | scans from the front |
| x in s, d[k] (set/dict) | O(1) | looked up by hash |
| sorted(a) | O(n log n) | comparison sort |
| a[i:j], s1 + s2 | O(j-i), O(n+m) | builds a new object |
列表查找线性、集合字典常数，是选容器的第一条依据。
这些是常见结论，不是全部实现细节。重点记两条：列表头部插入删除是线性，字典与集合的键查找是常数。
下一页用实测验证第二条，这正是 L06 容器选型那句结论的依据。
| Container 容器 | n = 30,000 | n = 60,000 |
|---|---|---|
| list: x in a | 0.0122 s | 0.0500 s |
| set: x in s | 0.012 ms | 0.012 ms |
同一百次查询，只换容器。列表慢约 1,050 倍，n 翻倍后时间翻约四倍。
n
1 words = ["hello"] * 80_000 2 3 result = "" 4 for word in words: 5 result += word 6 7 # or collect and join 8 same = "".join(words)
先投票，并说出理由。学生最常见的理由是「字符串不可变，所以每次都复制」。
下一页用三种写法实测校正这个直觉的适用范围。这是本讲最重要的一处修订。
| Kind 写法 | n = 20,000 | n = 80,000 |
|---|---|---|
| plain s += w | 0.467 ms | 0.00166 s |
| keeping every prefix | 0.0235 s | 1.1580 s |
| "".join(words) | 0.049 ms | 0.195 ms |
CPython 对只有一个引用的字符串原地扩展；中间结果被别处引用时就要复制。
实测：普通循环与 join 在同一量级，每次都把中间结果留活的写法慢了三个数量级。
原因是 CPython 对只有单一引用的字符串可以原地扩展。结论必须写成「取决于有没有别的引用」，不能写成「循环拼接一律平方级」。写代码仍然推荐 join，因为它不依赖这条实现细节。
| Measurement 测量 | n | Best of 3 取最小 |
|---|---|---|
| 1,000 elements | 10 comparisons | log2(1000) = 9.97 |
| 1,000,000 elements | 20 comparisons | halved 20 times |
| 1,000,000,000 elements | 30 comparisons | halved 30 times |
Measured on the build machine 本机构建时实测，同一进程内重复取最小值。
L07 写过二分查找，当时把复杂度留到这里。每比较一次候选范围减半，问题是从 n 降到 1 要除几次 2，答案是对数。
十亿个元素最多三十次比较，这就是对数复杂度，也是排好序的数据值钱的原因。
同样的记号用来描述内存占用，这一点学生第一次见。
生成器如何把 O(n) 空间降回 O(1) 在 L13 讨论，这里先建立概念。
顺序不能颠倒：内置函数快是常数变小，救不了错的算法。本机实测 sum(range(2*10^6)) 比手写循环快约 2.4 倍，两者都是 O(n)。
这就是「先降阶、再优化常数」的具体含义，也是 Knuth 那句话的落点。
检查是否理解折半次数就是对数，不涉及新记号。
第19页已经给出方法，本题验收；下页讲评原题分布。
从成本转到失败。先区分可预期的外部问题和不该发生的内部错误，这一区分在第三部分决定用异常还是断言。
顺序不能颠倒：先看得见的崩溃，再谈不声不响的错。
1 x = 10 2 y = 0 3 print(x / y)
ZeroDivisionError: division by zero
这段代码语法完全正确，Python 顺利编译了，运行时才出错。这种错误叫异常。
回溯的最后一行给出类型与消息；不处理的话程序在这里终止，后面的语句一行都不执行。
| Code 代码 | Actual exception 实际异常 |
|---|---|
| print(value + spam * 3) | NameError: name 'spam' is not defined |
| print(text + 2) # text is "2" | TypeError: can only concatenate str (not "int") to str |
NameError: a name was never defined. TypeError: two types cannot be combined. 两种都只有执行到那一行才会发生。
上一页是除零，这一页再补两种最常见的运行时错误。
共同点是名字和类型都检查不出来，必须真的执行到那里才知道。下一页开始处理它们。
1 def safe_divide( 2 a: float, 3 b: float, 4 ) -> float | None: 5 try: 6 return a / b 7 except ZeroDivisionError: 8 print("cannot divide by zero") 9 return None 10 11 print(safe_divide(10, 2)) 12 print(safe_divide(10, 0)) 13 print("program continues")
5.0 cannot divide by zero None program continues
try 体正常执行时跳过 except；一旦抛出异常，立刻跳到匹配的分支。
这正好解决了 L03 留下的问题：那时候说输入非数字程序会崩，L11 讲怎么办。
1 def parse_age(text: str) -> int | None: 2 try: 3 return int(text) 4 except ValueError: 5 print(f"{text!r} is not an integer") 6 return None 7 8 for s in ["18", "abc", "3.14", ""]: 9 print(s, "->", parse_age(s))
18 -> 18 'abc' is not an integer abc -> None '3.14' is not an integer 3.14 -> None '' is not an integer -> None
捕获具体的类型，程序可以给用户一句有用的提示并继续。
下一页把三种不同的失败放进同一段 try，说明分支顺序。
1 def classify(value: str) -> str: 2 try: 3 number = int(value) 4 except Exception: 5 return "general" 6 except ValueError: 7 return "specific" 8 else: 9 return f"ok {number}" 10 finally: 11 print("cleanup") 12 13 print(classify("abc"))
先投票：宽类型写在前面、具体类型写在后面，捕获到的会是哪一个。
常见直觉是「更具体的会先匹配」。下一页用实测结果回答，并说明裸 except 为什么更糟。
1 def classify(value: str) -> str: 2 try: 3 number = int(value) 4 except Exception: 5 return "general" 6 except ValueError: 7 return "specific" 8 else: 9 return f"ok {number}" 10 finally: 11 print("cleanup") 12 13 print(classify("abc"))
cleanup general
实际先打印 cleanup 再返回 general。异常按书写顺序从上到下匹配，宽类型在前会遮住后面的具体类型。
裸 except 等价于捕获一切，包括拼写错误和 KeyboardInterrupt；要兜底就写 except Exception as error 并把消息打印出来。
实测 10 / 2 走 else 与 finally，10 / 0 走 except 与 finally：10 / 2: / ok, result 5.0 / cleanup / 10 / 0: / failed / cleanup
else 只在 try 体没有抛异常时执行，放成功之后才该做的事；finally 无论如何都执行，放清理工作。
实测四行输出说明两条路径的差别：成功走 else 和 finally，失败走 except 和 finally。下一页检查 finally 里的 return。
1 def f() -> str: 2 try: 3 return "from try" 4 finally: 5 return "from finally" 6 7 print(f())
先投票：try 里已经准备好返回 from try，finally 里又写了一个 return，函数最终返回什么。
常见答案是 from try。下一页给出实测结果，并说明 finally 里的 return 还会抑制正在传播的异常。
1 def f() -> int: 2 try: 3 return 1 / 0 4 finally: 5 return 42 6 7 print(f())
42
实际返回 42，而不是抛出 ZeroDivisionError：finally 里的 return 既覆盖返回值，也丢弃待传播的异常。
finally 在任何离开 try 的路径上都执行，这正是清理代码不要顺手写 return 的理由。with 的异常抑制是同一类边界。
1 def set_age(age: int) -> int: 2 if age < 0: 3 raise ValueError(f"age cannot be negative: {age}") 4 if age > 150: 5 raise ValueError(f"unreasonable age: {age}") 6 return age 7 8 print(set_age(18)) 9 print(set_age(-5))
ValueError: age cannot be negative: -5
需要调用方无法忽略时用 raise。返回 None 容易被忽略，错误会在离原因很远的地方才爆发。
抛异常立刻停下，回溯直接指向出问题的位置。本周实验里的 ValueError 就是这条规则的用法。
1 class InsufficientFunds(Exception): 2 def __init__(self, balance, amount): 3 super().__init__("too low") 4 self.balance = balance 5 self.amount = amount 6 7 def withdraw(balance, amount): 8 if amount > balance: 9 raise InsufficientFunds(balance, amount) 10 return balance - amount 11 12 try: 13 withdraw(100, 500) 14 except InsufficientFunds as e: 15 print("caught:", e) 16 print("short by:", e.amount - e.balance)
caught: too low short by: 400
自定义异常继承 Exception，L10 的继承在这里派上用场。
好处是调用方能精确捕获这一种失败，而不是笼统地抓 ValueError。异常类保持简单，通常只带需要的信息。
HALFWAY
两个45分钟的分界。上半节讲了成本、异常与清理。
下半节讲假设检查、测试的写法，以及素数五法的规模与成本。
1 with open("demo.txt", "w") as handle: 2 handle.write("hello") 3 print("closed:", handle.closed) 4 5 try: 6 with open("demo.txt") as reader: 7 raise ValueError("body failed") 8 except ValueError: 9 print("still closed:", reader.closed)
closed: True still closed: True
with 保证退出时执行清理，等价于写好的 try/finally。
只有 __enter__ 成功返回，__exit__ 才会被调用；块里抛异常，文件同样关闭。文件操作的完整内容在 L12。
| Style 风格 | Shape 写法 | When it reads better 什么时候更清楚 |
|---|---|---|
| LBYL | if key in d: use it | simple preconditions |
| EAFP | try it, catch KeyError | the normal path is the main line |
| Both are correct | choose by intent | neither is a rule |
看意图，不背规则。
Python
同时检查分支顺序与 finally 的位置。所有语法在第34页前都已教完。
下页讲评原题分布，不再发同题。
进入第三种失败。断言把「我以为一定成立」写成可执行检查，测试把观察值与期望值比较。
两者都指向证据，但一个检查程序自身的前提，一个检查对外行为。
1 def average(nums: list[float]) -> float: 2 assert len(nums) > 0, "empty list" 3 return sum(nums) / len(nums) 4 5 print(average([1, 2, 3]))
2.0
assert 条件, 消息 的意思是：我认为这里条件一定成立，不成立就说明程序有 bug，立刻停下。
用法是描述「这里必须成立」，不是给用户看的提示。下一页检查它在优化模式下的行为。
1 def average(nums: list[float]) -> float: 2 assert len(nums) > 0, "empty list" 3 return sum(nums) / len(nums) 4 5 print(average([1, 2, 3]))
同一个函数，一次在普通模式下运行，一次加上 -O 参数。先预测两次的结果有什么不同。
常见直觉是「关掉断言只是少了一层检查」。下一页给出两次运行的实际结果，其中一次会以除零错误结束。
| Mode 模式 | __debug__ | Result 结果 |
|---|---|---|
| python3 example.py | __debug__ = True | AssertionError: empty list |
| python3 -O example.py | __debug__ = False | ZeroDivisionError: division by zero |
断言是开发期的检查，不能校验用户输入；那要用 if 加 raise，不会被优化掉。
正常模式下断言生效，对空列表抛出 AssertionError；-O 模式下断言被跳过，函数继续执行到除零，抛出的变成 ZeroDivisionError。
所以断言不能校验用户输入。另外 assert (条件, 消息) 写成元组永远为真，检查会完全失效。
这道题检查断言表达式里的副作用：条件看起来成立，实际却已经改了状态。
全部语法已教，下页讲评。
| Place 位置 | Written as 写成 | Catches 能查出什么 |
|---|---|---|
| Precondition | assert sorted(nums) == nums | an argument that is out of contract |
| Postcondition | assert 0 <= i < len(nums) or i == -1 | a result the code promised but did not deliver |
断言描述契约；契约变了，断言跟着变。
断言把「输入必须有序」这类前置条件写成可执行检查，比注释可靠，因为注释会过期。
后置条件同样可以写：返回的下标处确实是目标，或者返回 -1 且目标确实不在其中。下一页把同一件事交给 pytest。
test_assertpytest.raises when a failure is the expected outcomepython3 -m pip install pytestL08 用检查循环比对期望值，pytest 把这套动作标准化。规则只有三条，先记住文件名与函数名都要以 test_ 开头。
下一页给一次真实运行的输出，包括一个故意写错的用例。
...F [100%] =================================== FAILURES =================================== E ValueError: cannot divide by zero mymath.py:6: ValueError: cannot divide by zero =========================== short test summary info ============================ FAILED test_mymath.py::test_divide_by_zero - ValueError: cannot divide by zero 1 failed, 3 passed in 0.00s
这段输出来自真实执行：三个用例通过，一个失败。
输出给出三件事：哪个用例失败、它期望什么（ZeroDivisionError）、实际发生什么（ValueError）。这正是它比手写循环有用的地方。完整诊断格式与 -v、-k 参数在参考区。
| Category 类别 | Example 例子 |
|---|---|
| Normal | a typical input |
| Empty | an empty list, an empty string |
| Single | exactly one element |
| Boundary | zero, negatives, largest and smallest |
| Failure | does invalid input raise as agreed |
每个分支一个用例；空与单个最容易漏。
实用起点是每个 if 分支至少走一遍。
L08 的边界清单在这里继续使用：AI 最常漏的仍然是「空」和「一个」。下一页把这张表用在一个别人写的模块上。
def longest_word(text): words = text.split() return max(words, key=len)
本周实验给的模块，三个函数各有一句文档，都没有说空字符串怎么办。
实测三个里有两个在空串上失败。文档没有约定的输入，正是容易出问题的地方。完整模块与文档在讲义。
1 def word_count(text: str) -> int: 2 """Count the words.""" 3 return len(text.split()) 4 5 def longest_word(text: str) -> str: 6 """Return the longest word. On a tie, the first one.""" 7 words = text.split() 8 return max(words, key=len) 9 10 def average_word_length(text: str) -> float: 11 """Return the mean word length.""" 12 words = text.split() 13 return sum(len(w) for w in words) / len(words)
先让学生给出数字和理由，再往下看。
这是「文档与实现不一致」的例子，也是测试存在的意义：先把期望写下来，再看实现是否满足。
word_count: 0 longest_word: ValueError average: ZeroDivisionError
实测 word_count("") 返回 0 正常；longest_word("") 抛 ValueError，average_word_length("") 抛 ZeroDivisionError。
原因分别是 max() 收到空序列和除数为零。测试的作用是先把期望写下来，再看实现是否满足。
1 def average(nums: list[float]) -> float: 2 print(sum(nums) / len(nums)) 3 4 got = average([1, 2, 3]) 5 print(got == 2.0)
平台做的就是把返回值和期望值比较，和上面 clamp 的检查循环是同一件事。
用 print 的函数返回 None，比较永远为假——这就是从 L03 起那句「函数要 return 不要 print」背后的机制，不是一条孤立的规则。
| Question | Actual result | Reason |
|---|---|---|
| Q4 assert not events.append("hit") | 1 | append returns None, so the assert passes; the element is already in the list |
| Q5 lru_cache over a list argument | TypeError: unhashable type: 'list' | a cache must build a key from its arguments |
Q4
| Method 方法 | Time 时间复杂度 | Space 空间 | Idea 思路 |
|---|---|---|---|
| brute | O(n^2) | O(1) | every p tries every d below it |
| sqrt | O(n sqrt n) | O(1) | a factor below sqrt(p) is enough |
| 6k+-1 | O(n sqrt n) | O(1) | skip multiples of 2 and 3 |
| sieve | O(n log log n) | O(n) | mark the whole range at once |
| Miller-Rabin | O(n log^3 n) | O(1) | a few modular powers per number |
这是本周个人作业 2 的理论依据。前三种同阶、常数不同；筛法降了阶，代价是一份长度为 n 的标记数组。
复杂度只说明增长形状，实际耗时还要看常数，下一页用实测说明。
| Method 方法 | n = 2000 | n = 100000 |
|---|---|---|
| brute | 0.0042 s | too slow |
| sqrt | 0.473 ms | 0.0864 s |
| 6k+-1 | 0.195 ms | 0.0288 s |
| sieve | 0.036 ms | 0.0021 s |
| Miller-Rabin | 0.455 ms | 0.0267 s |
五种方法在小规模都得 303，大规模都得 9592；先验证再计时。
平方根剪枝与 6k±1 在同一阶，常数差约三倍；筛法一直最快，代价是那份 O(n) 空间。
报告要求先验证正确性再计时，慢方法允许选可完成的规模，但不能换成另一种算法冒充。
两题分别检查「缓存要求可哈希的参数」与「键必须唯一确定子问题」。
全部语法已教，第57页后讲评。
实测 fib(20) = 6765 calls = 21,891；fib(25) = 75025 calls = 242,785；fib(28) = 317811 calls = 1,028,457。n 加 3，调用次数大约翻四倍，结果只增长到三倍左右。
L07 发现朴素斐波那契重复计算量巨大，并把修复留到这里。图中同一个 fib(3)、fib(2) 被反复算，这就是调用次数远超结果的原因。
根源是同一个子问题被算了无数遍，解决办法是把算过的记下来。
1 def ways(amount: int, coins: list[int], index: int) -> int: 2 if amount in memo: 3 return memo[amount] 4 if amount == 0: 5 return 1 6 if amount < 0 or index >= len(coins): 7 return 0 8 memo[amount] = (ways(amount - coins[index], coins, index) 9 + ways(amount, coins, index + 1)) 10 return memo[amount] 11 12 memo: dict[int, int] = {} 13 print("key = amount: ", ways(10, [1, 2, 5, 10], 0))
正确答案是 11，只用 amount 作键得到 129。
原因是 ways 有两个会变的参数：只看 amount，会把「用前两种面额凑出 10 分」和「用全部四种凑出 10 分」当成同一个状态，于是缓存了一个属于别的子问题的值。下一页对照两种键。
| Condition 条件 | Why 理由 |
|---|---|
| The key identifies the subproblem uniquely | every varying argument belongs in it: (amount, index), not amount |
| Same input, same output | a function of the clock, of randomness or of outside state cannot be cached |
11 = 11，ways(100) = 2156, calls = 801, cache entries = 400；fib(28) = 317811, calls = 55, cache entries = 27
换成元组键之后结果正确，缓存里的条目数正好是所有 (amount, index) 的合法组合数。
记忆化把指数级降到线性，代价是存下这些结果，这是又一处空间换时间。
1 from functools import lru_cache 2 3 @lru_cache(maxsize=None) 4 def fib(n: int) -> int: 5 if n <= 1: 6 return n 7 return fib(n - 1) + fib(n - 2) 8 9 print(fib(10)) 10 i = fib.cache_info() 11 print(i.hits, i.misses, i.currsize) 12 print(fib(10)) 13 print("hits:", fib.cache_info().hits) 14 print(fib(100))
55 8 11 11 55 hits: 9 354224848179261915075
标准库提供现成实现，装饰器本身在 L14 展开。本页只讲三件事：它能用、参数必须可哈希、maxsize 会限制条目数。
cache_info 给出命中与未命中次数；第二次算 fib(10) 时命中数增加，说明没有重新递归。Q5 的 TypeError 正是这条要求的直接后果。
本周任务是素数计数；大整数的分组表示留到第12周。
按现行配置第10周启动、第11周提交，三份个人作业各占 5%。
MR 的确定性只在本题域内成立，不能外推到任意大整数。完整参考解不公开，助教核对各方法是否为真实实现。
| Situation 情形 | Method 方法 | Why 理由 |
|---|---|---|
| many numbers, modest range | sieve | one pass marks the whole range |
| one very large number | Miller-Rabin | O(1) space, a few modular powers |
| this week, n <= 100000 | any trial division | all finish; only the constant differs |
先看规模和空间，再选方法。
差别在适用规模与空间：筛法要一份长度为 n 的标记数组，适合一次问出整个区间；Miller-Rabin 每次只判断一个数，空间是常数。
本周任务限定 n ≤ 100000，三种试除法都能完成，区别在耗时，不在阶数。
| Entry 入口 | Contract 契约 |
|---|---|
| w11-complexity-measure | comparable timings; no printing |
| w11-string-build | three builders agree; build_keep is the comparison |
| w11-memoize | the key holds every varying argument |
| w11-safe-convert | specific types only; no bare except |
| w11-config-review | a missing file differs from malformed content |
| w11-custom-exception | set_celsius raises TemperatureError |
| w11-tests | four cases per function, one pytest.raises |
七项沿用现稿任务，接口在实验页写明，提交页就地展开题面。
第11周按 Level 1 要求提交使用声明；本地保存与验收不等于线上提交。
| Written 常见写法 | What actually happens 实际发生 |
|---|---|
except: catches everything safely | it swallows typos and KeyboardInterrupt |
assert validates user input | assertions are removed under -O |
return in finally just returns early | it replaces the value and discards the exception |
assert (cond, msg) adds a message | a non-empty tuple is always true |
| more tests means better tests | covering the branches matters, not the count |
| read the implementation, then write tests | write the expectation from the docstring first |
六条都对应本讲实测过的代码，不是风格偏好。
最后一条是第48页的直接结论，也是 L08「先写测试」在本周的具体要求。
回到第2页的三种失败：太慢用增长阶回答，会崩用失败边界回答，悄悄算错用可执行检查回答。
第12周处理随机数、编码与文件，那里的输入更不干净，本讲的三种证据会继续使用。主线到此结束，后面32页供课后查阅。
参考保留完整的异常机制、旧稿的复杂度与哈希知识、素数五法的完整实现与提交规格。
片段标明依赖，长程序链接完整讲义，不设独立运行按钮。
| Case 情况 | Definition 定义 | Role here 本课的处理 |
|---|---|---|
| Worst | the most expensive input at that size | the default |
| Best | the cheapest input | rarely worth quoting |
| Average | the expectation over inputs | needs a distribution assumption |
同一个算法在同样规模下，不同输入的耗时可能不同。
本课不特别说明时都按最坏情况分析；平均情况的结论离开了分布假设就不成立。
n + 2 确实被 n² 从上方界住，所以写成 O(n²) 不算错，只是不紧。
平方根剪枝与 6k±1 就是「同阶、只差常数」的例子。
5.4642884629601965e+70
400 项系数时两种写法实测相差约 37 倍，阶数相同、常数不同。
这不是新算法，是同一个式子的两种写法，值得知道有这个形式。
a[i] costs O(1); a.insert(0, x) and a.pop(0) cost O(n)这两条假设推出上面全部结论，是第15页那张表的依据。
n 翻倍时间大约翻四倍，因为每一次插入本身是线性操作，而它被调用了 n 次。旧稿手写的 insert/find/remove 实现保留在讲义。
| Idea 想法 | Consequence 推论 |
|---|---|
| A position function computes where a value is stored | lookup does not scan |
| More slots than elements | space for time |
| Two keys can land on one slot | collisions exist and have standard remedies |
字典和集合的 O(1) 来自位置函数，代价是预留空间。
本课不要求你设计哈希函数，只要求知道契约；碰撞的存在不否定平均情况下的常数查找。
| Expression 表达式 | Result 实测结果 |
|---|---|
hash(1) == hash(1.0) | True |
hash(True) == hash(1) | True |
hash((1, 2)) | works |
hash([1]) / hash({"a": 1}) | TypeError: unhashable type |
a class that defines __eq__ only | __hash__ becomes None |
相等则同哈希；可变对象不做键。
规则是「相等的对象必须有相等的哈希值」，1、1.0、True 三者相等，所以哈希值相同。
可变容器不可哈希：内容会变，如果能当键，改内容就会让键找不到。定义 __eq__ 而不定义 __hash__ 的类，实例自动变成不可哈希。
要让自己写的对象当字典键，就得同时给出一致的 __eq__ 和 __hash__。
实践中多数情况用一个元组当键就够了，不必自己实现哈希。
2 -1
保留原来的 while 实现与边界说明，和 L07 的递归版本对照。
排序前提在第三部分的断言里写成了可执行检查。
| n | Calls 调用次数 | Answer 结果 |
|---|---|---|
| 20 | 21,891 | 6,765 |
| 25 | 242,785 | 75,025 |
| 28 | 1,028,457 | 317,811 |
调用次数大约是结果的三倍多，说明绝大多数调用都在重复算已经算过的东西。
递归深度也有上限：本机 sys.getrecursionlimit() 为 1000，超过就抛 RecursionError。所以朴素 fib(2000) 不是慢，是直接崩；记忆化版本每次只往下走一层，没有这个问题。
@lru_cache(maxsize=...) caps the entriesfib(28) 记忆化后调用 55 次、缓存 27 个条目，因为只有 28 个不同的子问题。
字典与列表两种写法在讲义里都给了，区别只在查找常数和内存的实际使用量。
同样算 fib，迭代版本只用两个变量，递归版本要保留整条调用链。
L13 讲生成器时，会把「一次只产生一个值、不建整个列表」这条思路用到极致。
value: alpha logged: 'missing' the caller decides
raisefrom keeps the cause裸 raise 记下信息后继续往上抛；异常链用 from 保留因果，讲义有完整例子。
函数记下信息后用裸 raise 继续往上抛，回溯保留，最终由调用方决定怎么处理。
返回值与抛异常的选择在这里一目了然：返回 None 的话，打印出来的是一句话；抛异常的话，调用方必须表态。
| Form 写法 | Meaning 含义 |
|---|---|
except (KeyError, IndexError): | tuple form |
except: | catches everything, including KeyboardInterrupt |
except Exception as error: | catch-all with a message |
| sibling clauses | do not catch each other |
同一段 try 的多个 except 不捕获彼此抛出的异常，它会往上走。
需要兜底时先记录再 raise，这样既留下信息又没有把错误吞掉。
| Level 层级 | Purpose 作用 |
|---|---|
class ConfigError(Exception) | a base for one family of problems |
class ConfigMissing(ConfigError) | callers can catch the whole family or one subclass |
| fields | carry the values the handler needs, such as the rejected value |
一个模块里定义多个相关异常时，常见做法是先定基类再派生。
L09 的 Temperature 改成抛异常后，set_celsius 从返回 False 变成抛 TemperatureError，调用方就不能再忽略返回值了。
| Exception 异常 | Typical source 常见来源 |
|---|---|
OSError, FileNotFoundError, PermissionError | files, directories, permissions |
ValueError | a failed conversion, such as int("abc") |
TypeError | mismatched types |
KeyError / IndexError | missing key / index out of range |
with
| Form 写法 | Result 结果 |
|---|---|
assert condition | raises AssertionError with no message |
assert condition, "message" | the message is shown |
assert (condition, "message") | always true |
| side effects | still happen |
消息写在逗号后面，不要包进括号。
第三行是最容易犯的错：多写一对括号，检查就完全失效。
第四行见 Q4：assert not events.append("hit") 通过，但元素已经进了列表。
| Setting 设置 | Effect 作用 |
|---|---|
__debug__ | a constant; False under optimisation |
python3 -O | assert statements are removed |
python3 -OO | also drops docstrings |
PYTHONOPTIMIZE | the same effect through the environment |
| cached bytecode | the file name carries the optimisation level |
实测：正常模式下 __debug__ 为 True，-O 下为 False，断言被跳过。
所以断言不能用来校验用户输入，那条路径会被优化掉。
| Misuse 误用 | What goes wrong 后果 |
|---|---|
| validating user input | removed under -O, so the check disappears |
| handling an expected failure | the bug is treated as a user error |
| side effects in the expression | the effect happens even when the assert passes |
| catching AssertionError | the bug is hidden |
断言失败意味着程序有 bug，正确的做法是让它崩掉，这样才看得到回溯。
开发期与生产期的差别就在这里：断言是开发期的检查。
| Item 项目 | Meaning 含义 |
|---|---|
-v | show every test name and result |
-q | progress dots and a summary only |
-k expression | run only tests whose names match |
pytest.raises(Error) | expect the given exception |
pytest.raises(Error, match="...") | also check the message |
pytest.approx(x) == y | float comparison without precision surprises |
浮点比较值得单独说：0.1 + 0.2 == 0.3 实测为 False，二进制小数存不下这三个数。
要比较浮点结果就用 pytest.approx 或给一个容差。
两者检验的是同一件事：期望值与实际值不一致时，给出足够的信息定位问题。
讲义保留可单文件运行的说明，同时给出真实 pytest 输出，不手写终端文本。
| Situation 情形 | Result 结果 |
|---|---|
| the function returns a value | compared against the expected value |
| the function prints instead | returns None; None == expected is never true |
| the expected outcome is an exception | the test expects the type, not a return value |
平台调用你的函数，把返回值和期望值比较。
这就是从 L03 起那句「函数要 return 不要 print」背后的机制。
| Category 类别 | Examples 例子 |
|---|---|
| normal | a typical input |
| empty | an empty list, an empty string |
| single | exactly one element |
| boundary | 0, negatives, largest and smallest, equal bounds |
| repetition | duplicate elements, consecutive spaces |
| failure | does invalid input raise as agreed |
每个分支至少一个用例。
让 AI 帮忙补用例时，仍然要自己先把这张表列一遍：L08 说了，「空」和「一个」正是最容易漏掉的两类。
2 ValueError
文档只说了「返回最长的单词」，没有约定空字符串。
测试的价值就是把没约定的输入摆出来，让差异变成可见的事实。
for...else runs the else when the loop was never brokenfor...else 在这里正好合用：循环没有被 break 打断，就是一个因子都没找到，p 是素数。
两种写法在 n ≤ 2 时都返回 0。
阶数没变，只是试除次数少了约三分之二。
这是「同阶不同常数」最直观的例子，和第67页的渐近含义呼应。
筛法一直最快，代价是那份长度为 n 的标记数组。
小范围时它的初始化成本相对更高，这一点在实测表里也能看出来。
pow(a, d, n) for a few basespow(base, d, n) is the three-argument built-in适用范围必须说清楚：用底数 2 和 3，n < 1,373,653 时结论是确定的，本题域内 n ≤ 100000 成立。
超出这个界之后，这几个底数只是概率性的证据，不能称对任意大整数确定。
| Requirement 要求 | Reason 理由 |
|---|---|
| verify correctness first | all five must agree at the same small size |
| fix the size and the machine | otherwise the numbers are not comparable |
| warm up, then take the minimum | avoid scheduler noise |
| a slow method may use a smaller size | but it may not swap in another algorithm |
报告里的耗时要有可比性，所以这几条是硬要求。
本节的秒数来自构建环境一次测量，只用来比较量级与倍数，不承诺在你的机器上得到同样的数字。
| Item 项目 | Agreement 约定 |
|---|---|
| five functions | count_primes_brute / _sqrt / _6k / _sieve / _mr |
| range | 0 <= p < n；0 <= n <= 100000 |
| small values | n <= 2 returns 0 |
| invalid input | a negative n raises ValueError |
| report | method notes, timing table, call counts, usage declaration |
| weight | three solo assignments: 15% total; this one 5% |
按现行配置覆盖第10、11周，截止读统一校历。
完整参考解不公开，助教核对各方法是否为真实实现；报告里要写清楚各自能完成的规模。
| Entry 入口 | Required boundary 边界 |
|---|---|
| w11-complexity-measure | the helper returns the smallest of repeats |
| w11-string-build | the kept-prefix version is the comparison |
| w11-memoize | count_ways and count_ways_memo agree |
| w11-safe-convert | unexpected failures must escape |
| w11-config-review | the file is closed on every path |
| w11-custom-exception | a rejected update keeps the old state |
| w11-tests | the suite must fail a wrong module |
原始分不改学期权重或日历；测试题的评分不只看测试是否通过，也看是否覆盖了空、单个、边界和异常。
| Thread 主线 | Answer 回答 |
|---|---|
| Too slow | count steps and keep the leading term |
| It crashes | catch what you can handle, raise what you cannot |
| Quietly wrong | assertions inside, tests outside |
| This week | five prime methods, with correctness before timing |
| Next | randomness, Unicode and files — messier input |
本讲的三种证据会继续使用：增长阶比较算法，失败边界划分责任，可执行检查写下期望。
第12周处理随机数、编码与文件，那里的输入更不干净，正好检验本讲的失败边界与测试写法。