Понимание кеширования функций в Python
Мемоизация - это метод, используемый для хранения результатов предыдущих вызовов функций для ускорения будущих вычислений. Если повторные вызовы функций выполняются с одинаковыми параметрами, мы можем сохранить предыдущие значения вместо повторения ненужных вычислений. Это приводит к значительному ускорению вычислений. В этом посте мы воспользуемся мемоизацией, чтобы найти факториалы.
Давайте начнем!
Во-первых, давайте определим рекурсивную функцию, которую мы можем использовать для отображения первых факториалов до n.
Напоминаем, что факториал определяется для целого числа n, так что он является произведением этого целого числа и всех целых чисел под ним. Например
1! = 1,
2! = 2*1= 2
3! = 3*2*1 = 6
и так далее. Мы можем определить рекурсивную функцию следующим образом:
Здесь мы указываем базовые случаи, которые говорят, что если входное значение меньше 2, возвращается 1. Если входное значение больше или равно 2, возвращаются рекурсивные вызовы функций, принимающие произведение целого и предыдущего целочисленных значений.
Теперь напечатаем первые 10 факториалов:
Кажется, все работает нормально. Теперь давайте попробуем отобразить первые 5000 терминов:
Это возвращает следующую ошибку, которая является защитой Python от переполнения стека (нехватки памяти):
Это происходит потому, что с каждым последующим вычислением мы повторяем работу.
Рассмотрим, как рекурсивная функция вычисляет каждый член:
1! = 1,
2! = 2*1= 2
3! = 3*2! = 6
4! =4*3! = 24
Обратите внимание, на 4! повторяем расчет 3! и 2 !. Если бы у нас был способ запоминать / сохранять эти значения при их вычислении, мы бы избегали повторения вычислений. Это формирует мотивацию для метода мемоизации.
Теперь давайте пройдемся по этапам реализации метода мемоизации. Чтобы продолжить, давайте инициализируем словарь:
Далее мы определим нашу функцию мемоизации. Сначала мы проверяем, меньше ли введенное значение 2, и возвращаем 1, если это так:
Затем мы проверяем, есть ли входное значение в словаре. Если это не так, мы сохраняем значение факториала в словаре и возвращаем значение для ключа ввода:
Полная функция:
А теперь давайте попробуем отобразить факториалы до 5000! с нашей новой функцией:
И мы видим, что расчет достигает 4999! успешно (вывод усечен):
Есть более простой способ реализовать мемоизацию, используя меньше кода. Давайте рассмотрим нашу исходную рекурсивную функцию:
Мы можем импортировать декоратор из модуля functools, называемого lru_cache, который позволяет нам кэшировать наши значения. Название означает «последний использованный кеш». Мы можем достичь той же производительности, что и наш метод factorial_memo, используя этот декоратор:
Мы видим, что достигаем аналогичных показателей. На этом я остановлюсь, но я призываю вас поиграть с кодом самостоятельно.
ВЫВОДЫ
Подводя итог, в этом посте мы обсудили метод мемоизации в Python. Во-первых, мы показали, как простая реализация рекурсивной функции становится очень медленной после вычисления многих факториальных членов. Затем мы определили новый метод, в котором мы сохраняли прошлые значения, которые мы вычислили в словаре. Это приводит к значительному ускорению вычислений. Затем мы обсудили декоратор «lru_cache», который позволил нам достичь производительности, аналогичной нашему методу «factorial_memo», с меньшим количеством кода. Если вы хотите узнать больше о мемоизации, я рекомендую вам ознакомиться с руководствами на YouTube https://www.youtube.com/watch?v=Qk0zUZW-U_M&t=302s. Надеюсь, вы нашли этот пост полезным / интересным. Код в этом посте доступен на GitHub https://github.com/spierre91/medium_code/blob/master/data_structures_and_algorithms/memo_factorial.py. Спасибо за чтение!
