效率、迭代器与生成器

回到篇三那个优雅的 fib：代码和数学定义一字不差，美不美？美。快不快？一点都不快。
当 n 大到 40，它能卡到让你怀疑人生。为什么"正确的代码"会这么慢？又该怎么救？
本篇先给你一把尺子（大 O）量效率，再用"迭代"和"记忆化"两把刀修掉 fib，最后引出 Python 里最被低估的利器——生成器，它让"无限序列"成为可能。

一、增长阶（大 O）：规模翻倍时耗时怎么变

是什么：衡量算法效率，不看"跑了 3 毫秒还是 5 毫秒"（那取决于机器和常数），而看输入规模 n 增长时，步数怎么随 n 变化。忽略常数倍，只看"增长趋势"，就是大 O 记号。

坑：大 O 丢掉了常数，所以"O(n) 一定比 O(n²) 快"只在 n 足够大时成立。n 很小的时候，一个常数巨大的 O(n) 可能反而慢。但趋势决定上限——当 n 奔着百万去，O(n²) 直接不可接受。

本质一句话：大 O 量的是"规模增长时步数的增长趋势"，忽略常数、看上限。

二、为什么朴素 fib 那么慢

篇三的 fib 是教科书级 O(2ⁿ)。问题不在递归本身，而在重复子问题：fib(5) 要算两遍 fib(3)、三遍 fib(2)……调用树疯狂重叠。n 每加 1，调用数约翻倍，n=40 就上亿次。

1
2
3
4
5
6
7
8

fib(5) 的调用树（大量重叠 = 指数爆炸）：
                fib(5)
             /          \
        fib(4)          fib(3)
        /    \          /    \
    fib(3)  fib(2)   fib(2)  fib(1)
    /  \     ...      (fib(2) 被算了两遍以上)
 fib(2) fib(1)

修法一：迭代（O(n)，空间 O(1)）——只保留"滑动窗口"两个值，不保留整棵树：

1
2
3
4
5
6
7

def fib_iter(n):
    a, b = 0, 1
    for _ in range(n):
        a, b = b, a + b
    return a

print([fib_iter(i) for i in range(8)])   # [0, 1, 1, 2, 3, 5, 8, 13]

修法二：记忆化（O(n)，空间 O(n)）——把算过的答案缓存起来，重复问直接查表：

1
2
3
4
5
6
7
8

from functools import lru_cache
@lru_cache(maxsize=None)
def fib(n):
    if n < 2:
        return n
    return fib(n - 1) + fib(n - 2)

print(fib(40))     # 102334155，瞬间出（不再是上亿次调用）

输出（修法一）：

1

[0, 1, 1, 2, 3, 5, 8, 13]

坑：记忆化爽，但递归深度仍在——fib(5000) 会先撞上 Python 默认的递归深度上限（RecursionError），而不是性能问题。极大 n 还是得靠迭代。

本质一句话：朴素 fib 慢在重复子问题（O(2ⁿ)）；迭代或记忆化都能压到 O(n)，但超大 n 要绕开递归深度。

三、迭代器协议：for 循环背后是什么

是什么：任何能用 for x in obj 遍历的对象，都实现了迭代器协议，核心两个方法：

• __iter__()：返回迭代器自身（或可迭代对象的迭代器）；
• __next__()：返回下一个元素，没了就抛 StopIteration。

1
2
3
4
5
6
7
8
9
10
11
12
13

class CountUp:
    def __init__(self, n):
        self.n = n
        self.i = 0
    def __iter__(self):
        return self
    def __next__(self):
        if self.i >= self.n:
            raise StopIteration
        self.i += 1
        return self.i

print(list(CountUp(3)))      # [1, 2, 3]

输出：

1

[1, 2, 3]

list(...) 在背后就是不断调用 __next__()，直到 StopIteration 才停。这就是 for 循环的本质。

坑：迭代器是一次性、单向的。一个迭代器走完再 for 一遍，什么都拿不到（已经 exhausted）。想要重来，得重新 __iter__() 造一个新的。

本质一句话：迭代器协议 = __iter__ + __next__；for 循环就是"反复调 next 直到 StopIteration"。

四、生成器：用 yield 写迭代器

是什么：手写 __next__ 又烦又容易错。Python 给了生成器（generator）——函数里出现 yield，它就不再是普通函数，而是"暂停—恢复"的生成器。每次执行到 yield 就暂停并返回值，下次从暂停处继续。

1
2
3
4
5
6
7
8
9

def gen_fib():
    a, b = 0, 1
    while True:                 # 无限循环也没事，因为惰性
        yield a
        a, b = b, a + b

g = gen_fib()
for _ in range(8):
    print(next(g), end=" ")     # 0 1 1 2 3 5 8 13

输出：

1

0 1 1 2 3 5 8 13

坑：生成器是惰性的——调用 gen_fib() 时一个值都没算，只有 next() 才推进一步。所以它能表示无限序列（上面的 while True 永不终止却完全安全）。相反，若用列表硬存所有斐波那契数，内存会爆。

本质一句话：生成器（yield）= 写迭代器最省事的方式；惰性求值让它天然支持无限序列。

五、惰性求值：不提前造全，要一个给一个

是什么：range(10**9) 不会真造十亿个数，它惰性地按需产生——这就是迭代器的价值：省内存、能表示无限流。

C++ 对照：C++ 没有生成器语法糖。"惰性序列"要写迭代器类（重载 operator++/operator*），或借助 C++20 的 std::ranges。远比 Python 生成器随手——这正是动态语言在"描述数据流"上省力的体现。

本质一句话：惰性求值 = 不提前造全、按需产生；迭代器/生成器用 O(1) 状态换掉 O(n) 内存，还能表达无限序列。

小结

• 效率看增长阶（大 O）：量趋势、丢常数。朴素 fib 是 O(2ⁿ)。
• 修 fib：迭代 O(n)/O(1) 空间；记忆化 O(n)/O(n) 空间但受递归深度限制。
• 迭代器协议 = __iter__ + __next__；for 循环靠它驱动，且一次性、单向。
• 生成器（yield） 是写迭代器最省事的方式，天然支持惰性求值与无限序列。

🐾 最后一篇讲 Scheme 解释器、尾递归与声明式 SQL——换一种语言范式给 CS61A 收官，你会看到"编程语言本身也是程序"。