使用lru_cache做记忆化递归时报unhashable type: 'list'如何解决

错误原因 #

lru_cache 会将函数的所有入参作为缓存字典的键，而Python中字典的键必须是可哈希的不可变类型。你代码中传入的elements是列表类型，列表是可变对象，不支持哈希，因此触发了unhashable type: 'list'报错。

解决方案 #

方案1：将入参的序列类型改为可哈希的元组 #

元组是不可变类型，支持哈希，可以直接作为缓存键。仅需要两处修改：

• 调用函数时将列表改为元组传入
• 递归调用时切片后的元组天然可哈希，无需额外处理

修改后代码如下：

from functools import lru_cache

@lru_cache(maxsize=None)
def countWays(elements, target):
    if target < 0:
        return 0
    if target == 0:
        return 1
    total = 0
    for index, element in enumerate(elements):
       total += countWays(elements[index:], target - element) 
    return total

if __name__ == '__main__':
    # 传入元组而非列表
    print(countWays((1, 2, 3), 5))

该方案修改量最小，对原有逻辑改动最少。

方案2：改用索引标记遍历位置，避免传递序列参数 #

该方案性能更优，不需要每次切片生成新的元组，仅用整数类型的起始索引标记当前遍历的位置，对外调用接口也完全兼容原有列表传参的逻辑：

from functools import lru_cache

def countWays(elements, target):
    # 先将输入的列表转为元组作为闭包变量，供内部递归函数使用
    elements = tuple(elements)
    @lru_cache(maxsize=None)
    def dfs(start_idx, target):
        if target < 0:
            return 0
        if target == 0:
            return 1
        total = 0
        for i in range(start_idx, len(elements)):
            total += dfs(i, target - elements[i])
        return total
    return dfs(0, target)

if __name__ == '__main__':
    # 调用时可以正常传列表
    print(countWays([1, 2, 3], 5))

该方案缓存的键只有两个整数，缓存占用更小，查询效率更高。

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