Мемоизация в Python для ускорения медленных функций

Использование мемоизации в Python для ускорения медленных функций

В данном руководстве мы рассмотрим использование функций lru_cache и cache для оптимизации расчетов в функциях Python.

Введение

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

Числа Фибоначчи

Числа Фибоначчи — это последовательность целых чисел, где каждое число является суммой двух предыдущих чисел, начиная с чисел 0 и 1.

Функция, которая вычисляет n-ое число Фибоначчи, часто реализуется рекурсивно.

Посмотрим на пример реализации

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

Вызовы функций fibonacci(4) можно визуализировать с помощью дерева рекурсии.

Мемоизация в Python для ускорения медленных функций

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

Мемоизация в Python

В Python 3 запоминать функции невероятно просто. Модуль functools, входящий в стандартную библиотеку Python, предоставляет два полезных декоратора для мемоизации: lru_cache (новый в Python 3.2) и cache (новый в Python 3.9). Эти декораторы используют кэш с наименьшим последним использованием (LRU), который хранит элементы в порядке их использования, отбрасывая наименее недавно использованные элементы, чтобы освободить место для новых.

Чтобы избежать дорогостоящих повторных вызовов функций, fibonacci может быть обернут lru_cache, который сохраняет значения, которые уже были вычислены. Предельный размер lru_cache можно задать с помощью параметра maxsize, значение которого по умолчанию равно 128.

from functools import lru_cache


@lru_cache(maxsize=64)
def fibonacci(n):
    if n <= 1:
        return n
    return fibonacci(n - 1) + fibonacci(n - 2)

Теперь дерево рекурсии для fibonacci(4) не имеет узлов, которые встречаются более двух раз. Время работы теперь растет линейно, что гораздо быстрее экспоненциального роста.

Мемоизация в Python для ускорения медленных функций

Декоратор cache эквивалентен lru_cache(maxsize=None).

from functools import cache


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

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

Заключение

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

Python 3 позволяет легко реализовать мемоизацию. Просто импортируйте lru_cache или cache из functools и примените декоратор.

Егор Егоров

Программирую на Python с 2017 года. Люблю создавать контент, который помогает людям понять сложные вещи. Не представляю жизнь без непрерывного цикла обучения, спорта и чувства юмора.

Ссылка на мой github есть в шапке. Залетай.

Оцените автора
Егоров Егор
Добавить комментарий

  1. Сергей

    долго работает ж-(

    from functools import lru_cache
    @lru_cache(maxsize=64)
    def f(n):
    if n==0: return 0
    if n%2!=0: return f(n-1)+1
    return f(n/2)
    k=0
    for i in range(1_000_000_000):
    if f(i)==2: k+=1

    print(k)

    Ответить
  2. Виктория

    Доброго времени суток.
    Как я восхищаюсь такими людьми, с точным складом ума.
    А вот гуманитарий например.
    Множество цифр , и слово ФИБОНАЧЧИ вообще мне очень понравилось
    Егор Егоров Вы большой молодец, круто пишите на темы программирования.
    Успехов!

    Ответить
    1. Егор Егоров автор

      спасибо, очень приятнеы слова)

      Ответить