Как заставить функцию запоминать 2 значения переменной функции?

#python #list #function #recursion #memoization

#python #Список #функция #рекурсия #запоминание

Вопрос:

Я хочу повысить производительность рекурсивного вычисления значений

 n = 100

def T(n,k):
    q = 0
    if n == 0 and k == 0:
        return(1)
        q = 1
    if k>n or n<0:
        return(0)
        q = 1
    if q != 1:
        return(T(n-1,k-1) n*T(n-1,k))

for i in range(n):
    for n in range(i 1):
        print(T(i,n))
    print("*********")

Однако я нашел способы сделать это только с функциями, которые принимают только 1 аргумент, например:

 def mem(f):
    memory = {}
    def inner_function(x):
        if x not in memory:            
            memory[x] = f(x)
            return memory[x]
        else:
            return memory[x]
    return inner_function

@mem
def fibonacci(n):
    if n == 1 or n == 0:
        return 1
    else:
        return fibonacci(n-1)   fibonacci(n-2)

Я думал о создании 2d-массива, но пока не знаю (предполагая, что это возможно), как поможет идея сделать это со списками списков.

1. Добро пожаловать в SO! Что именно делает эта рекурсивная функция? Однобуквенные переменные мне не очень помогают…. После двух ветвей остается мертвый код return . В общем, однако, если вы хотите запоминать функции с несколькими аргументами, просто добавьте больше аргументов inner_function и хэшируйте их как кортеж memo . Это может быть сложно, если эти аргументы являются изменяемыми или иным образом не хэшируемыми, что, похоже, здесь не так.

2. if q != 1: также всегда верно….

Ответ №1:

Вы можете использовать functools.lru_cache для этого

 from functools import lru_cache

@lru_cache(maxsize=32)
def T(n,k):
    q = 0
    if n == 0 and k == 0:
        return(1)
        q = 1
    if k>n or n<0:
        return(0)
        q = 1
    if q != 1:
        return(T(n-1,k-1) n*T(n-1,k))

Вы можете использовать этот декоратор для запоминания вызовов функций, в частности, с помощью этой функции это позволит сохранить до maxsize самых последних вызовов.

Обратите внимание, что в данном конкретном случае подавляющее большинство времени фактически тратится на запись в консоль из-за ваших print утверждений. Если вы удалите это (но все же оставите свой T(i,n) вызов), ваш код завершится почти мгновенно.

1. совет: используйте изменяемые аргументы по умолчанию для создания функций с сохранением состояния, которые затем могут эффективно кэшироваться. На самом деле не профессионал-совет Никогда этого не делает.

2. Вы также можете использовать @cache , чтобы сделать кеш неограниченным.

Ответ №2:

Вы можете легко расширить свой mem декоратор для работы с переменными *args параметрами, просмотрев их в memory . Это тоже будет работать **kwargs , но вам придется преобразовать их в хэшируемый тип, например frozenset . of tuples . И, конечно, для этого все параметры должны быть хешируемыми.

 def mem(f):
    memory = {}
    def inner_function(*args):
        if args not in memory:            
            memory[args] = f(*args)
        return memory[args]
    return inner_function

Протестировано с вашей T функцией, работает нормально. Однако на практике вы все равно можете захотеть использовать functools.lru_cache .