Python 空间换时间技巧与实例解析

Python中“空间换时间”的典型做法是用字典、集合、缓存等额外内存避免重复计算或加速查找：集合/字典成员判断为O(1)，@lru_cache缓存函数结果，预编译正则、构建映射表、复用字符串方法、使用布尔数组标记状态。

Python 中“空间换时间”最典型的做法，就是用额外的内存（比如字典、集合、缓存结构）来避免重复计算或加速查找，从而显著提升运行速度。

用字典/集合替代列表做成员判断

列表的 in 操作是 O(n) 时间复杂度，而集合（set）和字典（dict）的键查找平均是 O(1)。当需要高频判断某个元素是否在数据中时，把列表转成集合能极大提速。

• ❌ 慢： if x in [1, 2, 3, 1000, ...] # 每次遍历
• ✅ 快： valid_set = {1, 2, 3, 1000, ...}; if x in valid_set

使用 @lru_cache 缓存函数结果

对纯函数（尤其递归或参数范围有限的函数），用 functools.lru_cache 自动缓存返回值，避免重复执行。斐波那契就是一个经典例子：

• 未缓存版本：递归调用指数级增长，f(40) 可能卡顿
• 加缓存后：@lru_cache(None) 让 f(100) 瞬间返回

预计算并存储中间结果

当某类计算固定、频繁、开销大（如字符串处理规则、数值映射表、正则编译对象），提前算好存在变量里，比每次临时生成更高效。

• 正则：用 re.compile(r'\d+') 一次编译，多次 .match() 复用
• 映射表：如把月份名转数字，建字典 {'Jan': 1, 'Feb': 2, ...}，而不是每次 index() 查找
• 字符串方法：str.strip 或 str.lower 是绑定方法，直接赋给变量可省去属性查找开销（小优化，但体现思路）

用布尔数组或位图标记状态

在处理范围明确的整数集合（如 0–10000）时，用长度固定的列表或 bytearray 表示“是否存在”或“是否已访问”，比用集合或字典更省内存且更快索引。

• 例如筛质数：用 is_prime = [True] * (n+1)，下标即数字，O(1) 查状态
• 对比用 set() 存质数，虽然灵活但内存更大、缓存局部性差

这些做法本质一致：接受一点内存增长，换来算法时间复杂度下降或常数级加速。实际选哪种，取决于数据规模、访问模式和内存约束。