Использование мемоизации в Python

В программировании, особенно в языках с высоким уровнем абстракции, таких как Python, оптимизация производительности часто является ключевым аспектом.

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

Что такое мемоизация?

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

Перед вызовом функции проверяется, вызывалась ли функция ранее:

1. если не вызывалась, то функция вызывается, и результат её выполнения сохраняется;
2. если вызывалась, то используется сохранённый результат.

Мемоизация может использоваться не только для увеличения скорости работы программы. Например, она используется при взаимно-рекурсивном нисходящем синтаксическом разборе в обобщённом алгоритме нисходящего синтаксического анализа.

Пример без мемоизации

Давайте рассмотрим пример функции, которая вычисляет факториал числа без использования мемоизации:

def factorial(n):
    if n == 0:
        return 1
    else:
        return n * factorial(n-1)

При каждом вызове factorial(n) эта функция будет рекурсивно вызывать себя для вычисления факториала n-1, что может привести к избыточным вычислениям.

Пример с мемоизацией

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

def memoize(func):
    cache = {}

    def memoized_func(*args):
        if args not in cache:
            cache[args] = func(*args)
        return cache[args]

    return memoized_func

@memoize
def factorial(n):
    if n == 0:
        return 1
    else:
        return n * factorial(n-1)

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

Пример использования мемоизации

Давайте рассмотрим пример использования мемоизации для вычисления факториала:

print(factorial(5))  # 120
print(factorial(3))  # 6

При первом вызове factorial(5) вычисляется факториал числа 5 и результат (120) сохраняется в кэше. При следующем вызове factorial(3) функция сначала проверяет кэш и обнаруживает, что результат уже вычислен, поэтому возвращает значение из кэша (6), без повторных вычислений.