Типичные ошибок и способы исправить (коротко, с примерами).
1) Кэш создаётся внутри функции и перезаписывается при каждом вызове
Ошибка:
def fib(n):
cache = {}
if n in cache: return cache[n]
if n < 2: return n
cache[n] = fib(n-1) + fib(n-2)
return cache[n]
Проблема: кэш реинициализируется, рекурсия остаётся экспоненциальной $O(2^n)$.
Исправления (варианты):
a) Вынести кэш наружу:
cache = {}
def fib(n):
if n in cache: return cache[n]
if n < 2: return n
cache[n] = fib(n-1) + fib(n-2)
return cache[n]
b) Использовать аргумент по умолчанию (он сохранится между вызовами):
def fib(n, cache={}):
if n in cache: return cache[n]
if n < 2: return n
cache[n] = fib(n-1, cache) + fib(n-2, cache)
return cache[n]
c) Лучше — стандартный декоратор:
from functools import lru_cache
@lru_cache(maxsize=None)
def fib(n):
if n < 2: return n
return fib(n-1) + fib(n-2)
Сложность с мемоизацией обычно становится линейной $O(n)$.
2) Использование изменяемых/нехэшируемых ключей (list, dict)
Ошибка:
def ways(state_list):
cache = {}
if state_list in cache: ... # TypeError: unhashable type: 'list'
Решение: превратить состояние в неизменяемую структуру (tuple, frozenset), или сформировать кортеж всех входных параметров:
key = tuple(state_list)
или
key = (i, j, tuple(remaining))
Пример:
def dfs(state):
key = tuple(state) # вместо state
if key in cache: return cache[key]
...
3) Неправильная область видимости: переменная cache затем переопределяется (shadowing)
Ошибка:
cache = {}
def f(x):
cache = {} # тень — новый локальный словарь
...
Исправление: не переопределять, либо явно указать global/nonlocal, либо вынести кэш наружу:
cache = {}
def f(x):
if x in cache: ...
4) Ключ не отражает полного состояния (пропущены параметры) → кеш даёт неверные попадания или их нет
Ошибка:
def f(a, b):
key = a # забыли b
Решение: указывать все релевантные параметры в ключе:
key = (a, b)
5) Кэширование изменяемых объектов по ссылке, которые потом меняются
Ошибка:
cache[obj] = result # если obj мутируется, идентичность изменится/поведёт к логическим ошибкам
Решение: кешировать безопасное представление/копию (tuple, frozenset, сериализация) или ключ на основе неизменяемых полей.
Дополнительно: если используете пользовательский декоратор memoize, убедитесь, что рекурсивные вызовы идут через обёртку (имя функции в теле — замещённое), или используйте lru_cache. Пример неправильного декоратора обходящего кэш (реже встречается) — обращайте внимание, что внутренняя ссылка должна вызывать обёрнутую функцию.
Краткое резюме:
- Кэш должен существовать в правильной области видимости и не переинициализироваться.
- Ключи должны быть хешируемыми и полностью описывать состояние.
- Для удобства и безопасности используйте @lru_cache или явно вынесенный/передаваемый словарь кеша.