LeetCode 1155 字典记忆化与LRU Cache性能差异原因求解

问题背景 #

我在求解LeetCode 1155「掷骰子的和等于目标值的数目」问题时，首先实现了基于字典的记忆化方案，代码如下：

class Solution:
    def numRollsToTarget(self, dices: int, faces: int, target: int) -> int:
        
        dp = {}
        def ways(t, rd):
            if t == 0  and rd == 0: return 1
            if t <= 0 or rd <= 0: return 0
            if dp.get((t,rd)): return dp[(t,rd)]
            dp[(t,rd)] = sum(ways(t-i, rd-1) for i in range(1,faces+1))
            return dp[(t,rd)]
        
        return ways(target, dices)

该解法在骰子数、面数均为15左右的测试用例上固定出现超时。后续我找到了使用functools.lru_cache实现缓存的解法，除缓存实现逻辑外其余代码完全一致，运行速度非常快，代码如下：

class Solution:
    def numRollsToTarget(self, dices: int, faces: int, target: int) -> int:
        from functools import lru_cache
        @lru_cache(None)
        def ways(t, rd):
            if t == 0  and rd == 0: return 1
            if t <= 0 or rd <= 0: return 0
            return sum(ways(t-i, rd-1) for i in range(1,faces+1))
        
        return ways(target, dices)

此前我对比过两种缓存实现，多数场景下lru_cache不会比字典缓存的性能领先这么多，因此好奇两者出现如此大性能差距的具体原因。 #

原因分析 #

• 核心原因是字典记忆化的判断逻辑存在bug，导致缓存完全失效
  你编写的if dp.get((t,rd)): return dp[(t,rd)]逻辑存在漏洞：dict.get()方法在键不存在时返回None，键存在时返回对应值，而这行代码的判断条件是「返回值为真」才会走缓存分支。本题中存在大量ways(t, rd)返回0的合法情况（比如剩余骰子数不够凑出目标值、目标值超过剩余骰子能扔出的最大值等），这些结果存入字典后，查询时返回的0会被判定为假，导致不会走缓存分支，每次都要重新递归计算，相当于缓存完全没发挥作用，性能自然极差。
  正确的字典判断写法应该是if (t, rd) in dp: return dp[(t, rd)]，只要键存在就直接返回对应值，不管值是0还是其他数值，修改后性能会和lru_cache版本处于同一量级。
• 次要原因是lru_cache的底层实现优化
  functools.lru_cache是Python标准库中用C语言实现的装饰器，参数哈希、缓存读写、函数调用的逻辑都经过底层优化，比纯Python手写的字典缓存+判断逻辑的执行效率更高，不过这个优化幅度通常在2~5倍区间，远低于修复逻辑bug带来的几十上百倍的性能提升。

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