Python 记忆化导致的 Memory Limit Exceeded

Python 3.9 中引入了一个新的装饰器 functools.cache 用来做缓存,刷到 DP 相关的题目,就可以很方便地做记忆化了:

 1class Solution:
 2    def maximumScore(self, nums: List[int], multipliers: List[int]) -> int:
 3        N, M = len(nums), len(multipliers)
 4
 5        @cache
 6        def dp(left: int, right: int) -> int:
 7            i = N - (right - left + 1)
 8            if i == M:
 9                return 0
10            if left == right:
11                return nums[left] * multipliers[i]
12            return max(
13                nums[left] * multipliers[i] + dp(left + 1, right),
14                nums[right] * multipliers[i] + dp(left, right - 1),
15            )
16
17        return dp(0, N - 1)

不需要再手动地维护缓存,但是需要注意的是,被装饰的方法的参数要求可以被 hash,因为要作为 key。

LeetCode #1770. Maximum Score from Performing Multiplication Operations 这道题中,遇到了一个超内存的错误。

LeetCode 在运行测试用例的时候,不会多次创建 Solution 对象,只会用同一个对象去跑所有的用例,那么这里的缓存自然是所有用例的缓存了,但是我们只需要对当前用例缓存,之前的就可以清空了。

所以总的空间占用,对应消耗空间最大的那一个测试用例,而不再是所有测试用例总共的空间占用。

装饰器提供了一个方法 cache_clear() 用来清空缓存,那么在 return 之后清空就可以了:

1try:
2    return dp(0, N - 1)
3finally:
4    dp.cache_clear()

记忆化导致超内存,并不是所有测试用例的缓存,都存在了同一个地方。 使用 id(dp) 可以看到每个测试用例都是不一样的 dp 对象,只是之前的缓存没有被回收而已。

这有点类似于按层遍历二叉树,如果维护一个当前层的 List 作为中间变量,那么其实空间复杂度是 O(N),因为每一层都创建了一个 List 对象,推荐的做法是使用双端队列 Deque,理论上来说复杂度是 O(N/2) 还是 O(N),但是最大空间占用是最长的一层的节点数量,通过左 pop 和右 append,不会出现分配完用一次就扔掉的浪费了。


另一个题外话,同样因为 LeetCode 使用同一个对象来运行所有的测试用例,维护一个全局变量,比如类的静态变量,可能会遇到上一个用例遗留脏数据的问题。

可以尝试用其他方式存信息,或者每次都要手动清空了,代码会稍微丑陋一点。