Memoization python

Question

Что такое memoization, как он используется в python? а также то, как он отличается от рекурсии. Где-то я натолкнулся на утверждение, что для сокращения времени выполнения рекурсивной программы или функции мы должны использовать memoization вместо рекурсии. для например:

def factorial(n): 
    if n <1: # base case 
     return 1 
    else: 
     return n * factorial(n - 1) # recursive call 

Если это рекурсивная функция для вычисления факториала, каким будет изменение, когда используется запоминанием?

Answer 1

Memoization - это сохранение результатов для будущего использования. Модуль functools Python включает простой декоратор, lru_cache, который обрабатывает это для вас. Итак, для вашего примера:

@lru_cache(maxsize=None) 
def factorial(n): 
    ... 

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

Эти ответы могут также быть полезными для вас: What is memoization and how can I use it in Python?

Answer 2

Если функция чистая, она всегда будет давать один и тот же ввод. Мы можем воспользоваться этим, вспомнив результаты выполнения функции, сохраняя работу для дорогостоящих функций, таких как факториал. Результаты выглядят примерно так:

factorialAns = {} 
def factorial(n): 
    global factorialAns 
    if n in factorialAns: 
     return factorialAns[n] 
    if n <1: # base case 
     return 1 
    else: 
     factorialAns[n] = n * factorial(n - 1) # recursive call 
     return factorialAns[n]