目录
1. functools.cache / lru_cache - 记忆化搜索
4. functools.total_ordering - 自动生成比较方法
5. functools.cmp_to_key - 旧版比较函数转换
| 搜索与图论 | collections.deque |
BFS（双端队列优化） |
| 贪心 / 优先队列 | heapq |
Dijkstra 算法、任务调度问题 |
| 组合数学 | itertools |
生成排列组合、枚举子集 |
| 动态规划 | functools.lru_cache |
记忆化递归（斐波那契数列等） |
| 字符串处理 | str.split()、str.join() |
文本分割与拼接 |
| 大数据输入输出 | sys.stdin.read() |
ACM 模式下的大量数据读取 |
一、random
import random
random.randint(1, 10) # 生成1到10之间的整数
random.choice([1, 2, 3]) # 从序列中随机选择一个元素二、 functools - 高阶函数工具
1. functools.cache / lru_cache - 记忆化搜索
应用场景：递归算法中的重复子问题（如斐波那契数列、背包问题、LCS 等）。
示例：斐波那契数列优化
from functools import cache
@cache
def fib(n):
if n <= 1:
return n
return fib(n-1) + fib(n-2)
# 传统递归时间复杂度 O(2^n)，加缓存后 O(n)
替代方案：若环境不支持，可手动实现缓存：
memo = {}
def fib(n):
if n in memo:
return memo[n]
if n <= 1:
res = n
else:
res = fib(n-1) + fib(n-2)
memo[n] = res
return res2. functools.reduce - 序列累积操作
应用场景：连续二元运算（如阶乘、列表元素乘积、字符串拼接）。
示例：计算阶乘
from functools import reduce
n = 5
factorial = reduce(lambda x, y: x * y, range(1, n+1), 1)
# 等价于 1*2*3*4*5 = 120
3. functools.partial - 函数参数冻结
应用场景：固定函数的某些参数，生成新的简化函数（如自定义排序规则）。
示例：自定义排序
from functools import partial
def compare(a, b, reverse=False):
return a < b if reverse else a > b
# 冻结 reverse=True，生成降序比较器
desc_compare = partial(compare, reverse=True)
sorted([3, 1, 4], key=cmp_to_key(desc_compare)) # 输出 [4, 3, 1]
4. functools.total_ordering - 自动生成比较方法
应用场景：自定义类只需定义 __eq__ 和一个其他比较方法（如 __lt__），自动生成其余比较运算符。
示例：分数类比较
from functools import total_ordering
@total_ordering
class Fraction:
def __init__(self, num, den):
self.num = num
self.den = den
def __eq__(self, other):
return self.num * other.den == self.den * other.num
def __lt__(self, other):
return self.num * other.den < self.den * other.num
# 自动支持 >, <=, >= 等比较
5. functools.cmp_to_key - 旧版比较函数转换
应用场景：将传统的比较函数（如 cmp(a, b)）转换为 key 函数（适用于 sorted、min 等）。
示例：按绝对值排序
from functools import cmp_to_key
def abs_cmp(a, b):
return abs(a) - abs(b)
sorted([-3, 1, -2], key=cmp_to_key(abs_cmp)) # 输出 [1, -2, -3]
6. 性能优化技巧
示例：带状态的装饰器（统计递归调用次数）
import functools
def count_calls(func):
@functools.wraps(func) # 保留原函数元信息
def wrapper(*args, **kwargs):
wrapper.call_count += 1
return func(*args, **kwargs)
wrapper.call_count = 0
return wrapper
@count_calls
def fib(n):
if n <= 1:
return n
return fib(n-1) + fib(n-2)
fib(5)
print(f"调用次数: {fib.call_count}") # 输出 15（未优化时）