08 · 高频手撕代码背诵手册(Python 3)¶
核心概念¶
(a) 🗂️ 高频手撕代码地图:背模板、讲复杂度、扛追问¶
手撕代码不是考算法竞赛,而是考「面试官给模板题,你能不能在 5 分钟内写对 + 讲清复杂度 + 扛住追问」。本篇按「语言特性 → 并发 → 轮子 → 数据结构 → 设计模式 → 工具类」组织,每段代码都带注释与时空复杂度标注,可直接运行。
(该图在 GitHub/VSCode + mermaid 插件中可渲染)
flowchart TB
Hand["✍️ 高频手撕代码"]
Hand --> Dec["🎁 装饰器四件套"]
Hand --> Gen["⏳ 生成器与 yield"]
Hand --> Single["🔂 单例模式三种写法"]
Hand --> Con["🧵 线程 / 进程 / asyncio"]
Hand --> Wheel["🔧 轮子题<br/>LRU / LFU / 最小栈"]
Hand --> Ds["📚 数据结构实现<br/>栈↔队列 / KMP / 回文"]
Hand --> Pattern["🧩 设计模式可运行版"]
Hand --> Tool["🛠️ 工具类三件套"]
- 🎁 装饰器四件套:无参装饰器(两层函数)、带参装饰器(三层函数)、
functools.wraps(保留原函数元信息)、类装饰器(带状态计数)是默写底线。要能说出每段的时空复杂度(包装 O(1))与「@ 糖」的等价写法。 - ⏳ 生成器与 yield:斐波那契生成器(O(1) 空间、可无限)、无限序列 take、
yield from委托子生成器是三大模板。背清楚「惰性求值、一次性遍历」两个特性,空间复杂度永远是面试追问点。 - 🔂 单例模式三种写法:模块级(import 一次天然单例)、
__new__版(加锁保证线程安全)、装饰器版(dict 缓存首建实例)要能切换默写。追问点:线程安全、什么场景用哪个。 - 🧵 线程 / 进程 / asyncio:生产者-消费者(
threading+queue,毒丸退出)、线程池(IO 密集)、进程池(CPU 密集)、asyncio 并发与asyncio.Queue消费者模型。每个都要能报复杂度并说清选型依据(GIL)。 - 🔧 轮子题:手写 LRU Cache(OrderedDict 版是标准答案,进阶问 dict + 双向链表)、手写 LFU(频率桶 + OrderedDict)、手写最小栈(辅助栈同步法)。追问:不用 OrderedDict 怎么实现、LFU 为何频率相同再按时间淘汰。
- 📚 数据结构实现:两栈实现队列(均摊 O(1))、单队列实现栈(push O(n))、KMP 字符串匹配(O(m+n))、最长回文子串中心扩展(O(n²),追问 Manacher O(n))。复杂度与边界条件是评分关键。
- 🧩 设计模式可运行版:观察者(订阅-发布 + 回调改进)、策略(注册表字典替代 if/elif、函数即策略)、工厂(简单工厂 vs 工厂方法、开闭原则)。追问方向:新增一种产品要不要改旧代码。
- 🛠️ 工具类三件套:retry 装饰器(指数退避 0.1→0.2→0.4,注意 4xx 不重试)、计时器上下文管理器(contextmanager,异常路径也打印)、参数校验装饰器。能讲清何时该重试、
__enter__/__exit__与 contextmanager 的关系。
面向秋招算法/后端岗位的 背诵级手写代码合集。 所有代码均为 标准库实现、可直接运行,每段都带注释与 时间/空间复杂度标注。 结构:每个小节先给「考点」一句话 → 完整代码 → 「面试追问」。 背诵策略:先默写主框架,再补细节(边界条件、decorator 的 wraps、队列判空等)。
1. 装饰器四件套¶
1.1 无参装饰器¶
💡 心法(一句话):装饰器 = 在不改原函数代码的前提下,给函数「套一件外套」(计时 / 打日志 / 加权限),再把「穿着外套的函数」还给你。
🏷️ 类比:网上买书加「防摔包装」:书(原函数)不用动,快递站(装饰器)在外面包一层气泡膜(wrapper),拆开包装里面还是原来那本书。
🔍 逐步走查:执行
slow_add(1, 2)时:①@timer等价于slow_add = timer(slow_add),此时slow_add其实已是wrapper;② 进入wrapper:记下start→ 调用真函数slow_add(1, 2),睡 0.1s 后返回 3;③ 打印耗时,return 3。函数名没变、行为却多了「计时」,这就是装饰器的全部秘密。
考点:装饰器本质是"接收函数返回函数"的高阶函数;熟练写出 *args, **kwargs 万能签名并保持返回值。
# decorator_basic.py —— 无参装饰器(最基础版)
import time
def timer(func):
"""打印函数耗时的装饰器"""
def wrapper(*args, **kwargs): # 万能签名,兼容任意入参
start = time.perf_counter()
result = func(*args, **kwargs) # 调用原函数并透传参数
print(f"{func.__name__} 耗时 {time.perf_counter() - start:.4f}s")
return result # 必须返回原函数的结果
return wrapper
@timer
def slow_add(a, b):
time.sleep(0.1)
return a + b
print(slow_add(1, 2)) # 输出耗时 + 3
# 等价写法(@ 糖的本质):
# slow_add = timer(slow_add)
# 时间复杂度 O(1) 包装,空间复杂度 O(1)
1.2 带参装饰器¶
💡 心法(一句话):无参装饰器是 2 层(工厂 → 外套);带参装饰器是 3 层——先按参数「定制」一件外套(如重复 3 次),再给函数套上。
🏷️ 类比:定做西装:先跟裁缝说「要 3 粒扣」(外层
times=3参数),裁缝按参数做好版型(中层decorator),再量你的身材给现成函数套上(内层wrapper)。🔍 逐步走查:
@repeat(3)展开为hello = repeat(3)(hello):①repeat(3)先执行,返回decorator;②decorator(hello)执行,返回wrapper;③ 之后调用hello("Alice")实际走wrapper,for _ in range(3)打印 3 次。口诀:参数进外层、函数进中层、干活儿在内层。
考点:带参装饰器 = 三层函数:外层(参数) -> 中层(函数) -> 内层(wrapper);@deco(3) 先调用建参再装饰。
# decorator_param.py —— 带参装饰器(可配置重复次数)
def repeat(times: int): # 第一层:接收装饰器参数
def decorator(func): # 第二层:接收被装饰函数
def wrapper(*args, **kwargs): # 第三层:真正执行逻辑
for _ in range(times):
result = func(*args, **kwargs)
return result
return wrapper
return decorator
@repeat(3)
def hello(name: str) -> str:
print(f"Hello, {name}")
return name
hello("Alice") # 打印 3 次
# 等价写法:hello = repeat(3)(hello)
# 带参装饰器依次是 3 层,与无参装饰器 2 层区分开
1.3 functools.wraps¶
💡 心法(一句话):装饰器套外套时会把函数的「身份证」(
__name__/__doc__)换成 wrapper 的;@functools.wraps(func)负责把身份证贴回原函数。🏷️ 类比:安检口换装后证件被拿错:wrapper 顶替了原函数的名牌;
wraps就是「把名牌还给你」的柜台——调试、报错、生成文档时才能认出原函数。
考点:不带 wraps 的装饰器会把原函数的 __name__/__doc__ 覆盖成 wrapper 的;functools.wraps 用 update_wrapper 把元信息拷回。
# decorator_wraps.py —— 为什么需要 functools.wraps
import functools
def bad_log(func):
def wrapper(*args, **kwargs):
"""wrapper 自己的文档"""
return func(*args, **kwargs)
return wrapper
def good_log(func):
@functools.wraps(func) # 把 func 的 __name__/__doc__ 等拷给 wrapper
def wrapper(*args, **kwargs):
return func(*args, **kwargs)
return wrapper
@bad_log
def add(a, b):
"""两数相加"""
return a + b
@good_log
def sub(a, b):
"""两数相减"""
return a - b
print("bad :", add.__name__, add.__doc__) # wrapper / wrapper 自己的文档 ❌
print("good :", sub.__name__, sub.__doc__) # sub / 两数相减 ✅
# 面试必答:wraps = update_wrapper(wrapper, func),内省/调试/Sphinx 文档依赖它
1.4 类装饰器¶
💡 心法(一句话):类装饰器 = 让「实例」当装饰器:类实现
__call__后对象能像函数一样被调用,还能用实例属性存状态(比如数一数被调了几次)。🏷️ 类比:带计数功能的门卫:每次放人进门都「计数 +1」,计数存在门卫自己身上(实例属性
calls),而不是写在进门的人身上。
考点:类实现 __call__ 后可作为装饰器;类版本可以在实例上保存状态(如调用计数),比函数闭包更"有状态"。
# decorator_class.py —— 类装饰器(带调用计数状态)
class CountCalls:
def __init__(self, func):
self.func = func
self.calls = 0 # 实例属性保存状态
def __call__(self, *args, **kwargs):
self.calls += 1
print(f"第 {self.calls} 次调用 {self.func.__name__}")
return self.func(*args, **kwargs)
@CountCalls
def ping(x):
return f"pong:{x}"
print(ping(1))
print(ping(2)) # 计数累加为 2
# 时间复杂度 O(1) 每调用,空间复杂度 O(1)(存一个计数器)
1.5 对比表格¶
| 类型 | 层数 | 特点 | 常见写法 |
|---|---|---|---|
| 无参装饰器 | 2 层 | 最简单,@deco |
deco(func) |
| 带参装饰器 | 3 层 | 可配置参数 | deco(args)(func) |
| wraps 装饰器 | 2 层 + wraps | 保留元信息,范式 | @functools.wraps(func) |
| 类装饰器 | 类 + __call__ |
可保存状态 | class Deco: __call__ |
1.6 面试追问¶
Q1:装饰器实现原理?
语法糖:
@deco等价于func = deco(func);函数是一等公民,可作为参数与返回值传递。带参装饰器相当于func = deco(args)(func)。
Q2:函数装饰器和类装饰器区别?
函数版闭包简单无状态;类版能存实例属性(计数器、配置),但多一层对象开销。两者用
__call__/闭包都能实现,看状态需求选型。
Q3:装饰器顺序 @A @B 是谁先执行?
自下而上装饰(B 先包裹,A 再包裹),所以
A(B(func));调用时自上而下执行。例:@auth @cache,先过 auth 再过 cache。
易错点:忘写 return result(吞返回值)、忘 @wraps(丢元信息)、带参装饰器少写一层函数 —— 这三点写完自检一遍。
2. 生成器¶
2.1 斐波那契生成器¶
考点:yield 让函数变生成器,惰性求值只占 O(1) 内存;手写斐波那契是最经典热身题。
# generator_fib.py —— 斐波那契生成器
def fib():
"""无限斐波那契序列生成器"""
a, b = 0, 1
while True:
yield a # 挂起并返回当前值,下次从这继续
a, b = b, a + b # 滚动推进
g = fib()
print([next(g) for _ in range(10)]) # [0,1,1,2,3,5,8,13,21,34]
# 时间:每次 next O(1);空间:仅两个变量 O(1);可无限生成,不占内存
2.2 无限序列 take¶
💡 心法(一句话):生成器像「无限长的传送带」,
take就是只取前 n 件的截断器——防止程序在无限序列上永远等下去。🏷️ 类比:自助餐不限量供应(无限生成器),但你的盘子有限——
take(n)就是「只夹 n 个就停」的手。
考点:无限生成器必须用 take/islice 截断消费,防止死循环;这是"生成器 + 工具函数"的配合题。
# generator_take.py —— 从无限序列中取前 n 项
import itertools
def naturals():
n = 0
while True:
yield n
n += 1
def take(n, iterable):
"""手写 take:取前 n 个(用 index 控制,防止死循环)"""
result, it = [], iter(iterable)
for _ in range(n):
result.append(next(it))
return result
print(take(5, naturals())) # [0,1,2,3,4]
print(list(itertools.islice(naturals(), 5))) # 标准库版,等价
# 时间 O(n),空间 O(n)(只保存取出的 n 项,而非全部序列)
2.3 yield from¶
💡 心法(一句话):
yield from是「中转站」:把子生成器产出的每个值原封不动转发给外层调用者,相当于替外层写了一个for x in sub: yield x。🏷️ 类比:快递中转站:总站(outer)不拆包裹,收到子站(sub_gen)的件直接转发给收件人,子站的「返回值」也会带回总站。
考点:yield from 把子生成器的产出"透传"给外层,用于委托生成器 / 扁平化嵌套可迭代。
# generator_yieldfrom.py —— yield from 的两种典型用法
def sub_gen(x):
yield f"sub-start:{x}"
yield f"sub-end:{x}"
def outer():
yield "outer-before"
yield from sub_gen(1) # 将子生成器的 yield 全部透传出去
yield "outer-after"
print(list(outer()))
# ['outer-before', 'sub-start:1', 'sub-end:1', 'outer-after']
def flatten(nested):
"""yield from 扁平化嵌套列表"""
for item in nested:
if isinstance(item, (list, tuple)):
yield from flatten(item)
else:
yield item
print(list(flatten([1, [2, [3, 4]], 5]))) # [1, 2, 3, 4, 5]
# 时间 O(总元素数),空间 O(嵌套深度)(递归栈)
2.4 面试追问¶
Q1:生成器和普通函数区别?
① 生成器含
yield,调用不执行,返回生成器对象;② 每next执行到下一个yield并挂起,保存局部状态;③ 惰性求值内存占用小;④ 迭代一次即耗尽。
Q2:yield from 相比手动 for x in sub: yield x 的好处?
它还会处理返回值(
return的值变成yield from表达式的值),并能在双向通信时透传send/throw;手写 for 循环做不到这两点。
Q3:生成器有什么用(工程场景)?
① 处理超大数据/流式读取不爆内存;② 协程的基础;③ 惰性流水线(如日志解析管道)。
易错点:无限生成器忘截断 → 死循环;生成器复用后已耗尽(迭代过一次再迭代为空)。
3. 单例模式(三种实现对比)¶
考点:单例 = 一个类全局只有一个实例;三种写法(模块级 / __new__ / 装饰器)都要会,并说清线程安全问题。
3.1 模块级单例¶
# singleton_module.py —— 模块级单例(Python 原生推荐)
class Config:
def __init__(self):
self.debug = True
# 模块只被 import 一次,天然单例
config = Config()
用法:任何地方 from singleton_module import config 拿到的都是同一对象。优点:最简单、无并发问题(解释器保证模块只初始化一次);缺点:不够"类内聚",无法防外面再 Config()。
3.2 __new__ 版单例¶
考点:__new__ 在 __init__ 前创建实例;用类属性缓存实例 + 双检锁保证线程安全。
# singleton_new.py —— __new__ 版(线程安全取价版)
import threading
class Singleton:
_instance = None
_lock = threading.Lock()
def __new__(cls, *args, **kwargs):
if cls._instance is None: # 快速路径:避免每次都抢锁
with cls._lock: # 双检锁:只有一个线程能创建
if cls._instance is None:
cls._instance = super().__new__(cls)
return cls._instance
def __init__(self, name="default"):
# 注意:__init__ 每次都会执行,赋值要幂等
if not hasattr(self, "_inited"):
self.name = name
self._inited = True
a, b = Singleton("x"), Singleton("y")
print(a is b, a.name) # True 'x'(第二次 __init__ 被幂等跳过)
# 时间 O(1)(首建加锁一次),空间 O(1)
3.3 装饰器版单例¶
# singleton_deco.py —— 装饰器版(用 dict 缓存首建实例)
import threading
def singleton(cls):
instances = {}
lock = threading.Lock()
def get_instance(*args, **kwargs):
if cls not in instances: # 双检锁
with lock:
if cls not in instances:
instances[cls] = cls(*args, **kwargs)
return instances[cls]
return get_instance
@singleton
class DBConn:
def __init__(self):
self.conn_id = id(self) # 每次新实例 id 不同
c1, c2 = DBConn(), DBConn()
print(c1 is c2) # True
# 时间 O(1),空间 O(类数)
3.4 对比表格¶
| 版本 | 实现 | 线程安全 | 适用 |
|---|---|---|---|
| 模块级 | import 机制 | ✅ 天然安全 | 生产首选,最简单 |
__new__ |
类属性缓存 + 双检锁 | ✅ | 必须用类封装时 |
| 装饰器 | 闭包 dict 缓存 | ✅(加锁) | 不想侵入类内部时 |
3.5 面试追问¶
Q1:__new__ 和 __init__ 区别?
__new__是创建实例的静态方法(cls 参数,返回实例);__init__是初始化实例(self 参数,返回 None)。单例应重写__new__控制创建,__init__可用幂等标记防止重复初始化覆盖属性。
Q2:单例真的线程安全吗?怎么保证?
不加锁的"判断 + 赋值"两步在并发下可能建多个实例;标准做法是双检锁(先查后锁再查)或模块级(Python import 锁保证只执行一次)。
Q3:单例的缺点?
全局状态难测试、隐蔽依赖、违背开闭原则;"单例 vs 依赖注入"是经典的架构选择题,可答"并发安全的模块级单例 + 显式传参"折中。
易错点:__new__ 版里忘了 super().__new__(cls) 会返回 None;__init__ 重复执行把同名属性覆盖。
4. 线程 / 进程¶
4.1 生产者-消费者(threading + queue)¶
💡 心法(一句话):生产者「放货」、消费者「取货」,中间用线程安全的
queue.Queue当缓冲区;队列满时生产者阻塞、空时消费者阻塞,各自都不空转。🏷️ 类比:奶茶店:后厨(生产者)做好奶茶放进取餐台(队列),顾客(消费者)按顺序取;取餐台放满后厨就等一等,取餐台空了顾客就等一等。
🔍 逐步走查:1 个生产者、2 个消费者、容量 5:① 生产者放「P-0」→ 队列=[P-0],C0 取走 → 队列=[];② 放「P-1」→ C1 取走;③ ……放完 8 个后,生产者往队列放 2 个 None 毒丸(每个消费者一个);④ 消费者
get()到 None 就task_done()并 break——没有毒丸,消费者会永远阻塞在get(),q.join()卡死。
考点:queue.Queue 内部已带锁,是线程安全队列;用它实现生产者-消费者,配合 task_done/join 优雅收尾。
# producer_consumer.py —— 生产者-消费者模型
import threading, queue, time, random
NUM_CONSUMERS = 2
q = queue.Queue(maxsize=5) # 容量 5,满时生产阻塞
def producer(name, total=8):
for i in range(total):
item = f"{name}-{i}"
q.put(item) # 满则阻塞直到有空位
print(f"[生产者{name}] 放入 {item}, 队列大小={q.qsize()}")
time.sleep(random.uniform(0.02, 0.05))
for _ in range(NUM_CONSUMERS):
q.put(None) # 毒丸:每消费者一个,通知其退出
def consumer(name):
while True:
item = q.get() # 空则阻塞等待
if item is None: # 收到毒丸 → 标记完成并退出
q.task_done()
break
print(f"[消费者{name}] 取出 {item}")
q.task_done() # 告诉队列该任务已完成
time.sleep(random.uniform(0.05, 0.1))
threads = [threading.Thread(target=producer, args=("P",))]
threads += [threading.Thread(target=consumer, args=(f"C{i}",)) for i in range(NUM_CONSUMERS)]
for t in threads:
t.start()
threads[0].join() # 等生产者放完(含毒丸)
q.join() # 等所有任务被 task_done(含毒丸),然后消费者退出
for c in threads[1:]:
c.join() # 等消费者线程结束,脚本干净退出
print("全部线程已优雅退出")
# 时间:整体 O(任务数 × 每任务耗时),空间 O(队列容量)
# 注意:q.join() 配合 q.task_done() 缺一不可;消费者必须用毒丸(None)显式退出,否则卡死
4.2 线程池 ThreadPoolExecutor¶
💡 心法(一句话):线程池 = 一批「固定数量的临时工」,任务来了排队干、干完不辞退,省去反复开线程/关线程的开销。
🏷️ 类比:银行柜台:固定开几个窗口(
max_workers),客户(任务)排队,谁空谁办;窗口不随客户来去而增减。
考点:线程池 = 复用受控数量的线程;map 简化批量任务;注意 GIL——线程池适合 IO 任务、不适合 CPU 密集。
# thread_pool.py —— 线程池(IO 密集场景合适)
from concurrent.futures import ThreadPoolExecutor, as_completed
import time
def fetch(url, delay=0.1):
time.sleep(delay) # 模拟网络 IO
return f"{url} -> ok"
urls = [f"http://site{i}.com" for i in range(5)]
with ThreadPoolExecutor(max_workers=3) as pool: # 最多 3 个线程并发
# 方式一:map 保持输入顺序返回
results = list(pool.map(fetch, urls))
# 方式二:submit + as_completed 按完成顺序返回
futures = [pool.submit(fetch, u) for u in urls]
for f in as_completed(futures):
print("完成:", f.result())
print("顺序结果:", results)
# 时间:max_workers=3 时总耗时 ≈ 5×0.1/3(并行摊薄),空间 O(任务数)
4.3 进程池 ProcessPoolExecutor¶
考点:进程池绕开 GIL 并行 CPU 密集任务;Windows 下必须 if __name__ == '__main__': 保护,否则递归创建子进程。
# process_pool.py —— 进程池(CPU 密集场景合适)
from concurrent.futures import ProcessPoolExecutor
def cpu_heavy(n: int) -> int:
"""模拟 CPU 密集计算(Python 大整数乘法会释放 GIL 吗?不释放,
但进程各自独立解释器,可真正并行)"""
total = 0
for i in range(n):
total += i * i
return total
if __name__ == "__main__": # Windows 必备保护,否则子进程无限 fork
nums = [10_000_000] * 4
with ProcessPoolExecutor(max_workers=4) as pool:
results = list(pool.map(cpu_heavy, nums))
print("进程池结果:", results[:2], "...")
# 时间:4 个 CPU 任务 ≈ 单核耗时的 1/4(真并行);空间:每进程独立内存
4.4 对比表格¶
| 手段 | 适用 | 关键限制 | 常用 API |
|---|---|---|---|
| 线程 | IO 密集(网络/文件) | GIL 限制 CPU 并行 | threading, queue |
| 线程池 | 批量 IO 任务 | 线程切换开销、GIL | ThreadPoolExecutor |
| 进程池 | CPU 密集 | 内存/启动开销、IPC 成本 | ProcessPoolExecutor |
4.5 面试追问¶
Q1:Python 多线程能加速 CPU 密集计算吗?
不能——GIL(全局解释器锁)保证同一时刻只有一个线程执行 Python 字节码;CPU 密集场景应改多进程或用 C 扩展(numpy)释放 GIL。
Q2:queue.Queue 为什么线程安全?
内部用
deque+ 一把mutex+ 两个Condition(not_empty/not_full),put/get的"检查-等待-操作"都在锁内完成。
Q3:Q 大时生产者-消费者怎么防止数据丢失?
task_done()+q.join()确保队列中所有项都被消费完再退出;生产者在while running循环里最后放毒丸(sentinel,如 None) 通知消费者退出,避免死等。
易错点:Windows 进程池忘 if __name__ == '__main__' 会报 RuntimeError;消费者 while True 没有退出条件会卡 join。
5. asyncio 协程¶
5.1 异步并发(asyncio.sleep 模拟 IO)¶
考点:async def + await + asyncio.gather;协程在 await 处让出控制权,IO 期间切换执行其他协程——总耗时 ≈ 最慢任务,而非任务之和。
# asyncio_basic.py —— 协程并发模拟爬虫
import asyncio
async def fetch_page(name: str, cost: float) -> str:
print(f"开始抓取 {name}")
await asyncio.sleep(cost) # 模拟 IO 等待,期间让出 CPU
print(f"抓取完成 {name}")
return f"{name}:{cost}"
async def main():
# gather:并发执行 3 个协程,总耗时 ≈ max(0.1,0.2,0.05)=0.2s 而非 0.35s
results = await asyncio.gather(
fetch_page("a.com", 0.1),
fetch_page("b.com", 0.2),
fetch_page("c.com", 0.05),
)
print(results)
asyncio.run(main())
# 时间:O(max(各任务耗时)) 并发摊薄;空间:每个协程栈 O(1) 级别
# 考点:await 是"交出控制权"的挂起点,asyncio.sleep 模拟真实 IO 让事件循环周转
5.2 asyncio.Queue 消费者模型¶
💡 心法(一句话):和线程版长得几乎一样,只是
put/get变成可await的协程——队列空/满时不是阻塞线程,而是「挂起让位」给别的协程。🏷️ 类比:流水线工位:机器(协程)发现料槽(队列)空了,不是傻站着占工位,而是先去做别的事(await 让出),料到了再回来。
考点:asyncio.Queue 是协程版队列,put/get 自身是协程可 await;用于协程间解耦——生产者放、消费者取。
# asyncio_queue.py —— 异步生产者/消费者
import asyncio, random
async def producer(q: asyncio.Queue, n: int):
for i in range(n):
await q.put(i) # 满则挂起
print(f"producer 放入 {i}")
await asyncio.sleep(0.02)
async def consumer(q: asyncio.Queue, name: str):
while True:
item = await q.get() # 空则挂起
if item is None: # 毒丸:退出信号
q.task_done()
break
print(f"consumer-{name} 取出 {item}")
q.task_done()
await asyncio.sleep(0.03)
async def main():
q = asyncio.Queue(maxsize=3)
pro = asyncio.create_task(producer(q, 6))
cons = [asyncio.create_task(consumer(q, str(i))) for i in range(2)]
await pro
await q.join() # 等真实任务全部 task_done
for _ in cons:
await q.put(None) # 毒丸:向队列放 None,每个消费者一个
await asyncio.gather(*cons) # 等所有消费者协程退出
asyncio.run(main())
# 时间:生产 6 项 ≈ 6×0.02 与消费并行,总耗受众消费速度影响
# 规范收尾:每消费者一个毒丸 None(或 task.cancel()),否则 q.join()/gather 永不返回
5.3 面试追问¶
Q1:协程和线程的区别?
协程是用户态调度、单线程内协作式切换,没有内核态切换与锁竞争开销;线程是内核态抢占式调度。协程适合大量 IO 等待,不适合 CPU 密集。
Q2:asyncio.run() 做了哪些事?
创建并运行事件循环、执行主协程、最后关闭循环与默认执行器;Python 3.7+ 统一入口,替代手动的
loop.run_until_complete()。
Q3:真正的网络 IO 用什么库?
aiohttp(HTTP)、httpx.AsyncClient;asyncio.sleep只用于面试演示"挂起点让出"的机制。
易错点:忘了 await(协程不执行返回 coroutine 对象);在同步函数里 asyncio.run 会报"在运行中的事件循环";消费者退出条件缺失导致 q.join() 永不返回。
6. 轮子题(缓存/栈经典实现)¶
6.1 手写 LRU Cache(OrderedDict)¶
考点:LRU(最近最少使用):容量满时淘汰最久未访问的键。用 OrderedDict:get/move_to_end 实现"访问即置顶";popitem(last=False) 弹出"最久未使用"。
# lru_cache.py —— LRU Cache(OrderedDict 版,标准答案)
from collections import OrderedDict
class LRUCache:
def __init__(self, capacity: int):
self.capacity = capacity
self.cache = OrderedDict() # 插入序 = 访问序
def get(self, key: int) -> int:
if key not in self.cache:
return -1
self.cache.move_to_end(key) # 访问过 → 移到末尾 = 最新
return self.cache[key]
def put(self, key: int, value: int) -> None:
if key in self.cache:
self.cache.move_to_end(key) # 更新也视为"最新访问"
self.cache[key] = value
if len(self.cache) > self.capacity:
self.cache.popitem(last=False) # 弹出最旧的(队首)
cache = LRUCache(2)
cache.put(1, 1); cache.put(2, 2)
print(cache.get(1)) # 1 → 键 1 变最新,键 2 变最旧
cache.put(3, 3) # 容量满 → 淘汰 2
print(cache.get(2)) # -1
# 时间:get/put 均 O(1);空间:O(capacity)
# 进阶问法:不用 OrderedDict 怎么实现?→ dict + 双向链表 + 哈希表,同样 O(1)
6.2 手写 LFU¶
💡 心法(一句话):LFU = 「谁用得最少淘汰谁」:每个键记访问频率,满了就踢掉「频率最低 + 最早进来」的那个。
🏷️ 类比:健身房储物柜:天天来的人(高频)保留;只来过一次的人(低频)先清走;频率一样时,先占柜子的人先走(时间早的淘汰)。
🔍 逐步走查:容量 2:①
put(1,1)→ key_val={1:(1,1)},freq_map={1:{1}},min_freq=1;②put(2,2)→ key_val={1:(1,1), 2:(2,1)},freq_map={1:{1,2}};③get(1)→_touch(1):从 freq=1 桶删 1,该桶空且 freq==min_freq → min_freq=2,1 进入 freq=2 桶(随后 put 时 min_freq 会被重置为 1);④put(3,3)容量满 → 从 freq_map[1] 队首挑 victim=2 删掉,把 3 放进 freq=1 桶;⑤get(2)→ -1。
考点:LFU(最不频繁使用):淘汰"访问频率最低"的键,频率相同淘汰最早。频率桶结构:freq -> OrderedDict(键值),维护 min_freq。
# lfu_cache.py —— LFU Cache(频率桶 + OrderedDict,O(1) 版本思路)
from collections import OrderedDict, defaultdict
class LFUCache:
def __init__(self, capacity: int):
self.capacity = capacity
self.key_val = {} # key -> (value, freq)
self.freq_map = defaultdict(OrderedDict) # freq -> OrderedDict<key, None>
self.min_freq = 0
def _touch(self, key: int) -> None:
"""key 访问频率 +1,并移动频率桶"""
value, freq = self.key_val[key]
del self.freq_map[freq][key] # 从旧频率桶移除
if not self.freq_map[freq] and freq == self.min_freq:
self.min_freq += 1 # 旧最小桶空了 → 提升
self.key_val[key] = (value, freq + 1)
self.freq_map[freq + 1][key] = None # 放入新频率桶尾部
def get(self, key: int) -> int:
if key not in self.key_val:
return -1
self._touch(key)
return self.key_val[key][0]
def put(self, key: int, value: int) -> None:
if self.capacity == 0:
return
if key in self.key_val:
self.key_val[key] = (value, self.key_val[key][1])
self._touch(key)
return
if len(self.key_val) >= self.capacity:
victim = next(iter(self.freq_map[self.min_freq])) # 最小频率桶的队首
self.freq_map[self.min_freq].popitem(last=False)
del self.key_val[victim]
self.key_val[key] = (value, 1)
self.freq_map[1][key] = None
self.min_freq = 1
lfu = LFUCache(2)
lfu.put(1, 1); lfu.put(2, 2)
lfu.get(1) # 键 1 freq=2
lfu.put(3, 3) # 淘汰 freq=1 的键 2
print(lfu.get(2)) # -1
# 时间:get/put 均摊 O(1);空间:O(capacity)
# 追问:为何 LFU 要"频率相同再按时间"淘汰 → 防止一个冷键刷两次频率霸占缓存
6.3 手写最小栈¶
💡 心法(一句话):空间换时间:再开一个「最小值栈」,它的栈顶永远记录当前数据栈里的最小值,于是
get_min和push/pop一样都是 O(1)。🏷️ 类比:登山队每走一步都记一张「当前最低海拔」便签,叠成一摞;往下撤一步就撕掉一张便签,随时知道此刻的海拔最低点。
🔍 逐步走查:依次 push 3、5、2、1:
操作 stack min_stack get_min push 3 [3] [3] 3 push 5 [3,5] [3](5>3 不压) 3 push 2 [3,5,2] [3,2] 2 push 1 [3,5,2,1] [3,2,1] 1 pop(弹 1) [3,5,2] [3,2] 2 关键:
pop时若stack.pop()的值 ==min_stack栈顶,两个栈一起弹。比较用<=而非<——多个相同最小值必须都记录,否则弹掉一个后get_min会「假变」大。
考点:O(1) 取最小值的栈:辅助栈同步记录"当前栈状态下的最小值",入栈时 min_stack 只压更小的。
# min_stack.py —— 最小栈(辅助栈同步法)
class MinStack:
def __init__(self):
self.stack = [] # 数据栈
self.min_stack = [] # 辅助栈:栈顶永远是当前最小值
def push(self, val: int) -> None:
self.stack.append(val)
if not self.min_stack or val <= self.min_stack[-1]:
self.min_stack.append(val) # 新最小值入辅助栈
def pop(self) -> None:
if self.stack.pop() == self.min_stack[-1]:
self.min_stack.pop() # 弹出的是当前最小值 → 同步弹
def top(self) -> int:
return self.stack[-1]
def get_min(self) -> int:
return self.min_stack[-1]
ms = MinStack()
for v in (3, 5, 2, 1):
ms.push(v)
print(ms.get_min()) # 1
ms.pop(); print(ms.get_min()) # 2
# 时间:四个操作均 O(1);空间:O(n)(最坏辅助栈同数据栈等长)
# 追问:不借助辅助栈?→ 差值法/存 (value, min) 元组,本质一样
6.4 手写单例装饰器(复用 3.3,快速背诵版)¶
# singleton_quick.py —— 10 秒默写版:装饰器单例
import threading
def singleton(cls):
_instances, _lock = {}, threading.Lock()
def get(*args, **kwargs):
if cls not in _instances:
with _lock:
if cls not in _instances:
_instances[cls] = cls(*args, **kwargs)
return _instances[cls]
return get
@singleton
class C:
pass
assert C() is C()
print("单例 OK")
# 时间 O(1),空间 O(类数);双检锁保证线程安全
6.5 面试追问¶
Q1:LRU 为什么用双向链表 + 哈希表?(不用 OrderedDict 时)
哈希表 O(1) 定位节点,双向链表 O(1) 把节点摘到表头(单向链表删除需要前驱,做不到 O(1));在 Python 里 OrderedDict 底层就是"dict + 双向链表"。
Q2:LRU 和 LFU 应用场景差异?
LRU 适合"时间局部性"(新闻热点、图片缓存);LFU 适合"频率局部性"(广告点击、用户画像统计)。LFU 实现复杂度更高,且存在"旧热点占位"问题,业界常用 LRU-K / TinyLFU(如 Redis 近似 LFU) 折中。
Q3:get_min 的等号为什么是 <=?
多个相同最小值时,辅助栈必须都记录;如果只压
<,弹出其中一个 2 时把辅助栈的 2 弹掉,另一个 2 还在栈中但 get_min 会错误变 3。
易错点:LRU 忘 move_to_end(get 不刷新序 = 白写);LFU 忘维护 min_freq;最小栈 pop 判断用值相等而不用下标。
7. 常用数据结构实现¶
7.1 用栈实现队列¶
考点:两个栈(in/out)倒腾:入队进 in;出队时若 out 空,把 in 全部倒入 out(倒一次的反转保证 FIFO),均摊 O(1)。
# stack_to_queue.py —— 两个栈实现队列(LeetCode 232)
class MyQueue:
def __init__(self):
self.in_stack = [] # 入队专用
self.out_stack = [] # 出队专用
def _transfer(self):
if not self.out_stack: # 只有 out 空了才倒,保护顺序
while self.in_stack:
self.out_stack.append(self.in_stack.pop())
def push(self, x: int) -> None:
self.in_stack.append(x)
def pop(self) -> int:
self._transfer()
return self.out_stack.pop()
def peek(self) -> int:
self._transfer()
return self.out_stack[-1]
def empty(self) -> bool:
return not self.in_stack and not self.out_stack
q = MyQueue()
for i in (1, 2, 3):
q.push(i)
print(q.pop(), q.pop(), q.pop()) # 1 2 3(FIFO)
# 时间:push O(1);pop/peek 均摊 O(1)(每个元素最多被搬一次);空间 O(n)
7.2 用队列实现栈¶
💡 心法(一句话):队列是「先进先出」,要伪装成栈(后进先出)——每次 push 后把新元素前面的人全部挪到队尾,让新元素「插队」到队首。
🏷️ 类比:食堂排队打饭,想让最后来的人先打——管理员让新来的站队首,原来排队的人全体绕一圈站到新来的人后面。
🔍 逐步走查:push 1 → q=[1];push 2 → 先 [1,2],再把前 1 个挪到队尾 → [2,1];push 3 → 先 [2,1,3],把前 2 个挪到队尾 → [3,2,1]。此时
pop()直接popleft()得 3 → 依次 3、2、1,后进先出 ✅。代价:push 是 O(n)。
考点:单队列即可:push 时把新元素放队尾,再把前面 n-1 个元素依次挪到队尾,让新元素"垫底"变队首,pop 直接出队首。
# queue_to_stack.py —— 单个队列实现栈(LeetCode 225)
from collections import deque
class MyStack:
def __init__(self):
self.q = deque()
def push(self, x: int) -> None:
self.q.append(x)
for _ in range(len(self.q) - 1): # 把队首 n-1 个转到队尾
self.q.append(self.q.popleft())
def pop(self) -> int:
return self.q.popleft() # 队首就是"最后 push"的元素
def top(self) -> int:
return self.q[0]
def empty(self) -> bool:
return not self.q
s = MyStack()
for i in (1, 2, 3):
s.push(i)
print(s.pop(), s.pop(), s.pop()) # 3 2 1(LIFO)
# 时间:push O(n)(挪 n-1 次)、pop O(1);空间 O(n)
7.3 字符串匹配 KMP¶
💡 心法(一句话):KMP = 主串指针永不下台阶,失配时只让模式串按
next数组「聪明地后退」,把暴力法 O(mn) 的重复比较省成 O(m+n)。🏷️ 类比:翻词典找词:翻到「ababaca」中 c 对不上时,你不会退回开头重翻(暴力法),而是根据「已经对齐的部分」直接滑到下一个可能的位置——
next[i]记的就是「这一格已经对上了几个字符,可以放心跳过」。🔍 逐步走查:next 数组怎么来的?
p = "ababaca",nxt[i]=p[:i]的最长相等真前后缀长度,j是「已对齐前缀长度」:
i p[i] 比较过程 新 j nxt[i] 1 b b ≠ a,j=0 无需回退 0 0 2 a a == a → j=1 1 1 3 b b == b → j=2 2 2 4 a a == a → j=3 3 3 5 c c≠b → j=nxt[2]=1;c≠b → j=nxt[0]=0;c≠a 0 0 6 a a == a → j=1 1 1 得到
nxt = [0, 0, 1, 2, 3, 0, 1]。匹配阶段同理:主串abcababacabd遇失配只做j = nxt[j-1],主串下标i永远只前进不后退 → 线性。完整匹配时返回i - len(p) + 1。
考点:核心是 next 数组(部分匹配表):模式串失配时,主串指针不回溯,模式串跳到 next 处继续。构建 next 与匹配两段都是双指针。
# kmp.py —— KMP 字符串匹配(返回模式串在主串中首次出现的位置)
def build_next(p: str) -> list:
"""next[i] = p[:i] 的最长相等真前后缀长度(失配时跳转的偏移)"""
nxt = [0] * len(p)
j = 0 # 已匹配前缀长度
for i in range(1, len(p)):
while j > 0 and p[i] != p[j]: # 失配回退
j = nxt[j - 1]
if p[i] == p[j]: # 匹配成功,公共前后缀 +1
j += 1
nxt[i] = j
return nxt
def kmp_search(text: str, p: str) -> int:
if not p:
return 0
nxt = build_next(p)
j = 0
for i in range(len(text)):
while j > 0 and text[i] != p[j]:
j = nxt[j - 1] # 主串不回溯,只回溯模式串
if text[i] == p[j]:
j += 1
if j == len(p): # 完整匹配
return i - len(p) + 1
return -1
print(build_next("ababaca")) # [0,0,1,2,3,0,1]
print(kmp_search("abcababacabd", "ababaca")) # 3
# 时间:O(m + n)(m=主串长,n=模式串长),最坏也是线性;空间 O(n)
7.4 最长回文子串(中心扩展)¶
💡 心法(一句话):把字符串想成以每个位置(含两字符中间的空隙)为中心「向两边照镜子」,能照多远回文就有多长——一共 2n-1 面镜子。
🏷️ 类比:站在两面平行镜中间照自己:以你(单个字符)为中心看奇数长度镜像;把镜缝对准你俩中间(空隙)看偶数长度镜像。
🔍 逐步走查:
s = "babad",只跟i=1(字符 a):①expand(1,1):s[1]==s[1] → 扩到 s[0]='b' vs s[2]='b' 相等 → 再扩越界 → 返回 (0,3) → 「bab」,长 3;②expand(1,2):'a' vs 'b' 不等 → 返回 (1,1) 无效;③i=2的expand(2,2)得「aba」也是长 3,没超过就保留第一个 → 最终返回「bab」。注意return lo+1, hi是因为多扩了一步要回退一格。
考点:中心扩展:每个字符(及相邻空隙)作为回文中心向两边扩;总共有 2n-1 个中心(含字符间空隙),O(n²)。Manacher 是进阶 O(n),先背中心扩展。
# longest_palindrome.py —— 最长回文子串:中心扩展
def longest_palindrome(s: str) -> str:
if not s:
return ""
def expand(lo: int, hi: int) -> tuple:
"""从 (lo,hi) 中心向外扩,返回 (起点, 终点) 左闭右开"""
while lo >= 0 and hi < len(s) and s[lo] == s[hi]:
lo -= 1
hi += 1
return lo + 1, hi # 多扩了一步,回退一格
best = (0, 0)
for i in range(len(s)):
odd = expand(i, i) # 奇数长度中心:字符本身
even = expand(i, i + 1) # 偶数长度中心:字符间空隙
for cand in (odd, even):
if cand[1] - cand[0] > best[1] - best[0]:
best = cand
return s[best[0]:best[1]]
for t in ("babad", "cbbd", "abba", "a"):
print(t, "->", longest_palindrome(t)) # bab/aba、bb、abba、a
# 时间:O(n²)(2n-1 个中心 × 每次最坏扩 n);空间 O(1)
# 追问:O(n) 解法?→ Manacher:回文半径数组 + 最右臂界镜像对称优化
7.5 对比表格¶
| 题目 | 核心技巧 | 时间 | 空间 |
|---|---|---|---|
| 栈→队列 | 双栈倒腾,均摊 | push O(1) / pop 均摊 O(1) | O(n) |
| 队列→栈 | 入队后把队首转到队尾 | push O(n) / pop O(1) | O(n) |
| KMP | next 数组,主串不回溯 | O(m+n) | O(n) |
| 最长回文 | 中心扩展 / Manacher | O(n²) / O(n) | O(1) / O(n) |
7.6 面试追问¶
Q1:KMP 的 next 数组和"暴力"差在哪?
暴力失配时主串指针 i 回到 i-j+1 重新比(O(mn));KMP 利用模式串自身的"最长公共前后缀"信息,失配只回溯模式串指针 j 到 next[j-1],主串 i 不回退,所以线性。
Q2:中心扩展为什么有 2n-1 个中心?
n 个字符各是 1 个"奇数中心",相邻字符之间有 n-1 个"偶数中心"(空隙),共 2n-1。
Q3:栈实现队列里,为什么 out 为空才转移?
若 out 非空时也转移,会把上层还没出完的元素顺序打乱;只在 out 为空时整批倒入,保证"批内先进先出、批间顺序衔接",均摊 O(1)。
易错点:KMP 构建 next 与匹配的 while 逻辑复制粘贴易错,背熟构建段;中心扩展 return 前要"回退一步"(lo+1, hi),否则多扣边界字符。
8. 设计模式(每段可运行)¶
8.1 观察者模式¶
考点:发布-订阅:主题维护监听者列表,状态变化时通知所有订阅者;解耦"事件的产生方"与"事件的消费方"。
# observer.py —— 观察者模式(订阅-发布)
class Subject:
"""被观察的主题"""
def __init__(self):
self._observers = [] # 订阅者列表
def attach(self, observer):
self._observers.append(observer)
def detach(self, observer):
self._observers.remove(observer)
def notify(self, msg):
for obs in self._observers:
obs.update(msg) # 广播消息
class EmailNotifier:
def update(self, msg):
print(f"[邮件通知] {msg}")
class SmsNotifier:
def update(self, msg):
print(f"[短信通知] {msg}")
subject = Subject()
subject.attach(EmailNotifier())
subject.attach(SmsNotifier())
subject.notify("订单已支付") # 两个订阅者同时收到
# 时间:通知 O(订阅者数),空间 O(订阅者数)
# 追问:改进版 → 事件总线/回调函数列表;Python 也可用回调代替类接口
8.2 策略模式(含注册表字典版)¶
💡 心法(一句话):把「算运费、算折扣」这类可变算法抽成独立对象/函数,运行时像换电池一样换策略,而不是写一堆 if/elif。
🏷️ 类比:点外卖选配送方式:「标准配送」「同城急送」是两个可替换的策略,选中哪个就用哪套计价规则,APP 主体逻辑不用改。
考点:把算法族封装成可替换的策略对象,运行时切换;注册表字典是 Python 实用变体——用 dict 把策略名映射到实现,免去 if/elif 分支。
# strategy.py —— 策略模式 + 注册表字典版
class ShippingFee:
def calc(self, weight): raise NotImplementedError
class StandardFee(ShippingFee):
def calc(self, weight): return 10 + 2 * weight
class ExpressFee(ShippingFee):
def calc(self, weight): return 20 + 5 * weight
# 注册表字典:策略名 -> 策略实例(替代 if/elif 链)
REGISTRY = {"standard": StandardFee(), "express": ExpressFee()}
def calc_fee(weight: float, strategy: str) -> float:
if strategy not in REGISTRY:
raise ValueError(f"未知策略: {strategy}")
return REGISTRY[strategy].calc(weight)
print(calc_fee(5, "standard")) # 20.0
print(calc_fee(5, "express")) # 45.0
# 开闭原则:新增策略只需往 REGISTRY 注册,不改调用方
# 追问:另一种实现 → 函数直接作为策略(Python 一等公民):REGISTRY = {"standard": fn}
8.3 工厂模式(简单工厂 / 工厂方法)¶
💡 心法(一句话):把「创建对象」的细节收进工厂:简单工厂一个函数按名字造产品;工厂方法把「造哪种产品」的决定权交给子类,扩展新产品不改旧代码。
🏷️ 类比:点餐柜台:简单工厂 = 一个服务员按你点的菜名做菜;工厂方法 = 每个厨师(子工厂)只负责自己拿手的一道菜,加新菜只需多雇一个厨师。
考点:简单工厂:一个工厂函数按参数返回不同产品(if/elif 集中一处);工厂方法:把"创建逻辑"下沉到子类(每个工厂子类只创建一种产品),符合开闭原则。
# factory.py —— 简单工厂 + 工厂方法
class Animal:
def speak(self): raise NotImplementedError
class Dog(Animal):
def speak(self): return "汪汪"
class Cat(Animal):
def speak(self): return "喵喵"
# ---- 简单工厂:一个函数按名称创建不同产品 ----
class SimpleFactory:
@staticmethod
def create(kind: str) -> Animal:
if kind == "dog":
return Dog()
if kind == "cat":
return Cat()
raise ValueError(kind)
# ---- 工厂方法:每个子工厂只负责一种产品,扩展新动物不改旧代码 ----
class AnimalFactory:
def create(self) -> Animal:
raise NotImplementedError
class DogFactory(AnimalFactory):
def create(self) -> Animal:
return Dog()
class CatFactory(AnimalFactory):
def create(self) -> Animal:
return Cat()
f1 = SimpleFactory()
print(f1.create("dog").speak()) # 汪汪
for factory in (DogFactory(), CatFactory()): # 工厂方法:面向基类编程
print(factory.create().speak()) # 汪汪 / 喵喵
# 简单工厂违反开闭(加产品要改 create);工厂方法用多态扩展,不改旧类
8.4 面试追问¶
Q1:观察者和"直接调用"区别?
直接调用是编译期绑定、耦合;观察者把"谁关心"延迟到运行时注册,事件源不关心订阅者细节,方便动态增删(消息队列、事件总线都是它的宏观形态)。
Q2:策略模式和 if/elif 相比好在哪?
if/elif 每次新增策略都要改业务代码(违反开闭原则);策略模式把每个算法独立成类,配合注册表可以做到"新增策略只加一行注册",且可组合、可测试。
Q3:简单工厂 / 工厂方法 / 抽象工厂区别?
简单工厂:一个函数按参数造一种产品;工厂方法:子类决定创建一种产品;抽象工厂:一个接口创建一族产品(如 Android 主题工厂同时生成按钮+输入框)。复杂度递增,按需选型。
易错点:观察者 notify 时列表被修改(遍历时增删订阅者)→ 先拷贝 list;策略注册表 key 拼写错误被静默忽略 → 显式 raise ValueError。
9. 工具类三件套¶
9.1 retry 装饰器(指数退避)¶
💡 心法(一句话):调用不稳定的远程服务失败时,「等一会儿再试」,且每次等待翻倍(1s→2s→4s)并加随机抖动,防止所有失败者同时重试把服务打崩。
🏷️ 类比:打不进客服电话就过一会儿再打,而且越等越久(指数退避);故意错开时间打(抖动),避免所有人同一秒一起拨号造成占线风暴。
考点:重试 + 指数退避(每次等待翻倍 + 抖动),限制次数与最终异常抛出;这是线上调用任何远程服务的标配脚手架。
# retry_deco.py —— 重试装饰器(指数退避)
import time, random
def retry(max_tries: int = 3, base_delay: float = 0.1, backoff: float = 2.0):
"""max_tries: 最多尝试次数;base_delay: 首次等待;backoff: 退避倍数"""
def decorator(func):
def wrapper(*args, **kwargs):
for attempt in range(1, max_tries + 1):
try:
return func(*args, **kwargs)
except Exception as e:
if attempt == max_tries:
raise # 最后一次失败,抛出原异常
wait = base_delay * (backoff ** (attempt - 1)) # 0.1, 0.2, 0.4...
wait += random.uniform(0, wait * 0.2) # 加抖动防"惊群"
print(f"第 {attempt} 次失败({e}),{wait:.2f}s 后重试")
time.sleep(wait)
return wrapper
return decorator
@retry(max_tries=3)
def flaky_call():
if random.random() < 0.6: # 60% 概率失败
raise ConnectionError("网络抖动")
return "成功"
print(flaky_call())
# 时间:最多 O(3) 次 × 退避等待;经典退避序列 0.1 → 0.2 → 0.4
# 追问:何时不该无脑重试 → 4xx 业务错误(幂等性/参数错误)不重试,5xx/超时才重试
9.2 计时器上下文管理器(contextmanager)¶
💡 心法(一句话):把「进入 with 前」和「退出 with 后」的代码用生成器拼起来:
yield之前是__enter__,之后是__exit__,天然适合计时、加锁、关文件。🏷️ 类比:健身房存包:进门(with 进入)按秒表,出门(with 结束)停表并广播耗时——用 try/finally 保证「中途摔倒」(异常)也会停表。
考点:@contextmanager 把生成器变成上下文管理器:yield 前是 __enter__,yield 后是 __exit__(异常时也会执行 yield 后代码,可用 try/finally 包住)。
# timer_ctx.py —— 计时器上下文管理器
from contextlib import contextmanager
import time
@contextmanager
def timer(name: str = "block"):
start = time.perf_counter()
try:
yield # 进入 with 体的位置
finally:
print(f"[{name}] 耗时 {time.perf_counter() - start:.4f}s")
with timer("查询数据库"):
time.sleep(0.2) # 模拟业务
try:
with timer("批量写入"):
time.sleep(0.1)
raise RuntimeError("写入失败") # 异常也会走 finally 打印耗时
except RuntimeError as e:
print("捕获异常:", e) # 演示异常路径,脚本不崩溃
# 时间 O(任务耗时);用 try/finally 保证异常路径也能打印
# 追问:手写 __enter__/__exit__ 类版也行,contextmanager 是生成器版捷径
9.3 参数校验装饰器¶
考点:装饰器做前置校验:限制参数类型/取值范围/必填;校验失败抛 ValueError/TypeError,把"防御式检查"从业务代码里剥离。
# validate_deco.py —— 参数校验装饰器
def require_types(**expected):
"""校验关键字参数类型,如 @require_types(age=int, name=str)"""
def decorator(func):
def wrapper(*args, **kwargs):
for k, t in expected.items():
if k in kwargs and not isinstance(kwargs[k], t):
raise TypeError(f"参数 {k} 期望 {t.__name__},得到 {type(kwargs[k]).__name__}")
return func(*args, **kwargs)
return wrapper
return decorator
def require_range(name: str, lo: float, hi: float):
"""校验数值参数取值区间"""
def decorator(func):
def wrapper(*args, **kwargs):
if name in kwargs and not (lo <= kwargs[name] <= hi):
raise ValueError(f"参数 {name} 需在 [{lo}, {hi}] 内")
return func(*args, **kwargs)
return wrapper
return decorator
@require_types(age=int)
@require_range("age", 0, 150)
def register(name: str, age: int) -> str:
return f"注册成功: {name}, {age} 岁"
print(register(name="Alice", age=25)) # 注册成功
try:
register(name="Bob", age="二十五") # TypeError
except TypeError as e:
print("校验拦截:", e)
# 时间 O(校验参数个数),空间 O(参数个数)
9.4 面试追问¶
Q1:指数退避为什么还要加抖动(jitter)?
所有客户端同时失败会同时重试,等待序列一致形成重试风暴(惊群);加随机抖动让重试时刻分散,这是 AWS/Google 通用实践。
Q2:@contextmanager 的 yield 前后代码分别在什么时候执行?
yield 前在
with进入时执行(相当于__enter__);yield 后在with块结束(含异常)时执行(相当于__exit__);用 try/finally 包住 yield 可以保证异常时清理资源。
Q3:校验装饰器放业务里还是框架层?
校验是横切关注点,应收敛在装饰器/中间件统一实现(DRY);但类型校验 Python 更常用
pydantic、dataclass等声明式方案,装饰器适合轻量场景。
易错点:retry 最后一次失败忘了 raise(把异常吞成 None);contextmanager 版本忘了 try/finally(异常时不打印耗时);校验装饰器只查 kwargs 漏掉位置参数导致误判。
附录:冲刺检查清单¶
☐ 装饰器:3 层(带参) / 2 层(无参) / @wraps / return result
☐ 生成器:yield 挂起 / take 截断无限序列 / yield from 透传
☐ 单例:模块级(推荐) / __new__ 双检锁 / 装饰器 dict 缓存
☐ 线程:queue.Queue + task_done/join;进程池 Windows 要 __main__ 保护
☐ asyncio:gather 并发 / Queue 毒丸退出 / asyncio.run
☐ LRU:move_to_end + popitem(last=False);LFU:频率桶 + min_freq
☐ 最小栈:辅助栈同步最值;队列/栈互转:倒腾法
☐ KMP:next 数组构建段单独默写;最长回文:中心扩展 2n-1
☐ 观察者/策略/工厂:注册表字典 / 简单 vs 工厂方法
☐ retry 指数退避 + 抖动、contextmanager 计时、参数校验
所有代码均可用
python 文件名.py直接运行;每个文件的运行结果已写在注释行中。