Мемоизация в Python: как заставить код помнить

[ALxMrk]

import time
from functools import lru_cache

# === Плотный CFG с высокой связностью (как в obfuscated IoT firmware) ===
NODES = list(range(20))
EXEC_GRAPH = {
    i: [j for j in range(i+1, min(i+5, 20))] + [max(0, i-2), max(0, i-1)]
    for i in NODES
}
EXEC_GRAPH[19] = []  # exit

def count_paths_raw(node, depth):
    if depth <= 0 or node not in EXEC_GRAPH:
        return 1
    total = 0
    for child in EXEC_GRAPH[node]:
        total += count_paths_raw(child, depth - 1)
    return total

@lru_cache(maxsize=None)
def count_paths_memo(node, depth):
    if depth <= 0 or node not in EXEC_GRAPH:
        return 1
    total = 0
    for child in EXEC_GRAPH[node]:
        total += count_paths_memo(child, depth - 1)
    return total

# ТЕСТ: глубина, при которой без кэша будет ОЧЕНЬ больно
depth = 35

print(f"→ Стресс-тест: подсчёт путей (глубина {depth}, 20 узлов, плотные связи)...")

# Только мемоизированный запуск — иначе ждать минуты!
t0 = time.perf_counter()
memo_result = count_paths_memo(0, depth)
t1 = time.perf_counter()

print(f"С мемоизацией: {t1 - t0:.6f}s | Путей: {memo_result}")

# Попробуй раскомментировать — и увидишь, почему все используют кэш:
# t0 = time.perf_counter()
# raw_result = count_paths_raw(0, depth)
# print(f"Без мемоизации: {time.perf_counter() - t0:.6f}s")

[dyadyaSerezha]

Чтобы это работало, аргументы функции должны быть хэшируемыми (неизменяемыми)

Нет. Аргументы функции могут быть какими угодно. Хэшируемыми должны быть ключи кэша.

if n in cache:

return cache[n]

Здесь поиск по ключу вызывается два раза. Лучше использовать cache.get()

[dyadyaSerezha]

Кстати, убивают меня такие размазанные фразы типа "должны быть хэшируемыми (неизменяемыми)". Так хэшируемыми или неизменяемыми? Или это одно и то же? А вы точно уверены, что объекты некого типа не могут быть изменяемые, но хэшируемые (или наоборот, неизменяемые, но не хэшируемые? Я вот уверен, что могут и легко.

[enamored_poc]

Классический пример: кортеж (сам по себе неизменяемый), который содержит изменяемый/нехэшируемый элемент.​Например, (1, [2, 3]) — кортеж нельзя “поменять” как кортеж, но внутри лежит список, и поэтому такой кортеж не хэшируется.

[dyadyaSerezha]

Да почему нет? Не меняйте список и все дела.

[Tishka17]

Почему функции работают долго?
Обычно это происходит по трем причинам:

3) Рекурсия — когда функция вызывает саму себя.

Нет, рекурсия не является причиной проблемы

И рекурсивный код и нерекурсивный могут работать одинаково долго просто потому что код так написан (с ошибками или намеренно для упрощения реализации).

[tenzink]

Неужели нельзя приводить менее одиозные примеры? Реализация fib в примере имеет экспоненциальную сложность, и это при живом несложном алгоритме, работающим за логарифм

[cmyser]

Хотелось бы конечно инвалидацию кэша

Как здесь https://mol.hyoo.ru/#!section=docs/=qxmh6t_sinbmb

Тогда это стало бы применимо почти для всего

[Novenkij]

 В современном программировании память стоит дешево

Уже неактуально )) В современном мире память резко подорожала