Python实现grid-traveller记忆化：手动memo与functools.cache疑问

我正在编码实现如下算法问题：

一个机器人位于m x n网格的左上角（即grid[0][0]位置），需要移动到网格的右下角（即grid[m - 1][n - 1]位置）。机器人任意时刻只能选择向下或者向右移动，给定两个整数m和n，请返回机器人到达右下角的所有唯一路径数量。我已经完成了该问题的基础代码编写，目前正在优化代码的运行效率。

两种实现方案 #

手动维护记忆化字典版本 #

gridTraveler_memo = {}
def gridTraveler(m,n):
    if (m and n) not in gridTraveler_memo:
        if m==1 and n==1:
            return 1
        elif m==0 or n==0:
            return 0 
        else:
            gridTraveler_memo[m,n] = gridTraveler(m-1,n) + gridTraveler(m,n-1)
    return  gridTraveler_memo[m,n]

print(gridTraveler(18,18))

基于functools.cache的版本 #

import functools

@functools.cache
def gridTraveler(m,n):
    if m==1 and n==1:
        return 1
    elif m==0 or n==0:
        return 0 
    else: 
        return gridTraveler(m-1,n) + gridTraveler(m,n-1)

print(gridTraveler(18,18))

实际测试中，第二段代码的运行速度远快于第一段代码，我作为Python初学者尚未完全理解functools.cache的运行机制。
我目前的判断是：第一种手动实现记忆化的方式更适配未来大型项目开发，且functools.cache会占用更多内存，想确认该认知是否正确。

解答 #

首先你手写版本速度异常慢的核心原因是代码有逻辑bug：判断缓存是否存在的条件写的是if (m and n) not in gridTraveler_memo，这里m and n的运算结果是整数n（当m、n都为正整数时），根本不是你存储时用的(m,n)元组键，等于缓存判断永远不命中，绝大多数递归分支都在重复计算，和手动实现记忆化本身的性能没有关系。把这行修正为if (m, n) not in gridTraveler_memo后，两个版本的性能差距会大幅缩小。

关于functools.cache的机制、内存占用和工程适用性，说明如下：

• functools.cache本质是Python标准库提供的、C层面优化的无界记忆化实现，底层同样用字典存储入参和返回值的映射关系，和你手写记忆化的核心存储逻辑没有本质区别。因为核心逻辑在C层实现，执行效率比纯Python写的键判断、赋值操作高，所以修完bug后它依然会比纯手写的记忆化版本快一点。
• 内存占用上，functools.cache和你写的全局记忆化字典没有本质差异：两者都是每遇到一组新的入参就存储对应返回值，不会多占额外内存。反而你定义的全局字典生命周期和整个程序一致，如果不手动清理，无用缓存会长期驻留内存；functools.cache绑定在对应函数对象上，函数被回收时缓存也会同步回收，还自带cache_clear()方法可以随时清空缓存，如果需要限制内存占用，还可以换成functools.lru_cache(maxsize=指定大小)实现自动的最久未使用缓存淘汰，这些能力都是手写记忆化需要额外写大量逻辑才能实现的。
• 大型项目开发中，functools.cache的适配性远高于自写记忆化。它不需要额外维护全局变量、不需要重复写缓存判断的样板代码，不会出现你这次写错缓存键判断逻辑的低级错误，还自带缓存命中统计、缓存清空等现成能力，代码可读性、可维护性、稳定性都经过了大量生产环境验证。只有当你需要自定义缓存键生成规则、特殊的缓存淘汰策略时，才有必要手动实现记忆化逻辑。

内容的提问来源于stack exchange，提问作者rexy london