Вопрос-Ответ

What is memoization and how can I use it in Python?

Что такое запоминание и как я могу использовать его в Python?

Я только что запустил Python и понятия не имею, что такое memoization и как его использовать. Также, могу я привести упрощенный пример?

Переведено автоматически
Ответ 1

Запоминание эффективно относится к запоминанию ("запоминание" → "меморандум" → для запоминания) результатов вызовов методов на основе входных данных метода и последующего возврата запомненного результата, а не повторного вычисления результата. Вы можете рассматривать это как кэш для результатов метода. Для получения дополнительной информации смотрите определение на стр. 387 в Введение в алгоритмы (3e), Cormen et al.

Простой пример вычисления факториалов с использованием запоминания в Python был бы примерно таким:

factorial_memo = {}
def factorial(k):
if k < 2: return 1
if k not in factorial_memo:
factorial_memo[k] = k * factorial(k-1)
return factorial_memo[k]

Вы можете усложнить и инкапсулировать процесс запоминания в класс:

class Memoize:
def __init__(self, f):
self.f = f
self.memo = {}
def __call__(self, *args):
if not args in self.memo:
self.memo[args] = self.f(*args)
#Warning: You may wish to do a deepcopy here if returning objects
return self.memo[args]

Тогда:

def factorial(k):
if k < 2: return 1
return k * factorial(k - 1)

factorial = Memoize(factorial)

В Python 2.4 была добавлена функция, известная как "декораторы", которая теперь позволяет вам просто написать следующее, чтобы выполнить то же самое:

@Memoize
def factorial(k):
if k < 2: return 1
return k * factorial(k - 1)

В библиотеке Python Decorator есть аналогичный декоратор с именем memoized, который немного более надежен, чем Memoize класс, показанный здесь.

Ответ 2

functools.cache декоратор:

Python 3.9 выпустил новую функцию functools.cache. Он кэширует в памяти результат функции, вызванной с определенным набором аргументов, который называется memoization . Он прост в использовании.:

import functools
import time

@functools.cache
def calculate_double(num):
time.sleep(1) # sleep for 1 second to simulate a slow calculation
return num * 2

При первом вызове caculate_double(5) это займет секунду и вернет 10. При втором вызове функции с тем же аргументом calculate_double(5) она мгновенно вернет 10.

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

(Редактировать: в предыдущем примере число фибоначчи было вычислено с использованием рекурсии, но я изменил пример, чтобы избежать путаницы, отсюда и старые комментарии.)

functools.lru_cache декоратор:

Если вам нужно поддерживать более старые версии Python, functools.lru_cache работает в Python 3.2+. По умолчанию он кэширует только 128 самых последних использованных вызовов, но вы можете установить значение maxsize на None, чтобы указать, что срок действия кэша никогда не должен истекать:

@functools.lru_cache(maxsize=None)
def calculate_double(num):
# etc

Ответ 3

Другие ответы довольно хорошо описывают, что это такое. Я не повторяю это. Просто некоторые моменты, которые могут быть вам полезны.

Обычно запоминание - это операция, которую вы можете применить к любой функции, которая вычисляет что-то (дорогостоящее) и возвращает значение. Из-за этого она часто реализуется как декоратор. Реализация проста, и это было бы что-то вроде этого

memoised_function = memoise(actual_function)

или выраженный в виде декоратора

@memoise
def actual_function(arg1, arg2):
#body
Ответ 4

Я нашел это чрезвычайно полезным

from functools import wraps


def memoize(function):
memo = {}

@wraps(function)
def wrapper(*args):

# add the new key to dict if it doesn't exist already
if args not in memo:
memo[args] = function(*args)

return memo[args]

return wrapper


@memoize
def fibonacci(n):
if n < 2: return n
return fibonacci(n - 1) + fibonacci(n - 2)

fibonacci(25)
python