Как ускорить рекурсию питон

Кэширование функций в Python

В сегодняшней статье мы рассмотрим как оптимизировать время выполнения программы в Python c помощью операции кэширования. Мы рассмотрим данную операцию на примере рекурсивной функции в Python. Но сначала — пара слов о рекурсии. Рекурсия — это понятие в программировании, при котором функция вызывает сама себя один или несколько раз. Данные типы функций часто сталкиваются с проблемами скорости, из-за того, что функция постоянно вызывает сама себя. Операция рекурсии занимает достаточно много памяти из за постоянного повторения одних и тех же шагов. Кэшировнаие или Мемоизация (англ. memoization от англ. memory и англ. optimization) помогает этому процессу, сохраняя значения, которые уже были рассчитаны для последующего использования. Давайте сначала вспомним что такое рекурсивные функции. Давайте посмотрим несколько примеров!

Написание факториальной функции.

Факториалы — один из самых простых примеров рекурсии, и является результатом умножения всех чисел меньших на единицу чем данное:

def factorial(n):
# установите базовый случай!
if n return 1
else:
return factorial( n – 1 ) * n

print( factorial(5) ) # результат от умножения 5 * 4 * 3 * 2 * 1

Последовательность Фибоначчи. Последовательность Фибоначчи — одна из самых известных формул в математике. Это также одна из самых известных рекурсивных функций в программировании. Каждое число в последовательность — это сумма двух предыдущих чисел, таких, что fib(5) = fib(4) + fib(3). Вычислим ее для 20.

from datetime import datetime
import time

def fib(n):
if n return n
else:
return fib( n — 1 ) + fib( n — 2 )

9227465
0:00:17.647056 # время вычисления

Как видно на вычисление результата для числа 35, ушло целых 17 секунд.

По мере того, как растет количество передаваемых данных, растет структура и количество рекурсивных вызовов . Он экспоненциальный, что может значительно замедлить работу программы. Даже попытка выполнить fib(40) может занять пару минут, а fib(100) обычно не работает из-за проблем с максимальной глубиной рекурсии. Что приводит нас к нашей следующей теме о том, как решить эту проблему… кэширование .

Понимание мемоизации.

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

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

Чтобы применить ее к последовательности Фибоначчи, мы должны понять, какой наилучший метод кэширования значений. В Python словари дают нам возможность для хранения значений на основе заданного ключа. Благодаря скорости и уникальной ключевой структуре словарей мы можем использовать их для хранения значение каждой последовательности Фибоначчи. Таким образом, как только одна последовательность, такая как fib(3), рассчитывается, его не нужно вычислять снова. Он просто сохраняется в кэше и извлекаются по мере необходимости. Давайте попробуем:

cache = < >
def fib(n):
if n in cache:
return cache[ n ]
result = 0

if n < = 1:
result = n
else:
result = fib( n – 1 ) + fib( n -2 )
cache[ n ] = result
return result

Использование @lru_cache

Теперь, когда мы знаем, как самостоятельно создать систему кэширования, давайте воспользуемся встроенными средствами Python. способ запоминания. Он известен как lru_cache.

from functools import lru_cache

@lru_cache( ) # встроенный инструмент кэширования
def fib(n):
if n return n
else:
return fib( n – 1 ) + fib( n – 2 )

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

Создано 26.04.2022 09:31:08

Михаил Русаков

Копирование материалов разрешается только с указанием автора (Михаил Русаков) и индексируемой прямой ссылкой на сайт (http://myrusakov.ru)!

Добавляйтесь ко мне в друзья ВКонтакте: http://vk.com/myrusakov.
Если Вы хотите дать оценку мне и моей работе, то напишите её в моей группе: http://vk.com/rusakovmy.

Если Вы не хотите пропустить новые материалы на сайте,
то Вы можете подписаться на обновления: Подписаться на обновления

Если у Вас остались какие-либо вопросы, либо у Вас есть желание высказаться по поводу этой статьи, то Вы можете оставить свой комментарий внизу страницы.

Порекомендуйте эту статью друзьям:

Если Вам понравился сайт, то разместите ссылку на него (у себя на сайте, на форуме, в контакте):

1. Кнопка:
   Она выглядит вот так:
2. Текстовая ссылка:
   Она выглядит вот так: Как создать свой сайт
3. BB-код ссылки для форумов (например, можете поставить её в подписи):

Комментарии ( 0 ):

Для добавления комментариев надо войти в систему.
Если Вы ещё не зарегистрированы на сайте, то сначала зарегистрируйтесь.

Copyright © 2010-2023 Русаков Михаил Юрьевич. Все права защищены.

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

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

Введение

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

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

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

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

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

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

Обратите внимание, что функция вызывается с одним и тем же входом несколько раз. В частности, 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 
Теперь дерево рекурсии для fibonacci(4) не имеет узлов, которые встречаются более двух раз. Время работы теперь растет линейно, что гораздо быстрее экспоненциального роста.

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






from functools import cache @cache def fibonacci(n): if n 
Поскольку cache не нуждается в отбрасывании последних использованных элементов, он одновременно меньше и быстрее, чем lru_cache с ограничением размера.
Заключение
Мемоизация повышает производительность за счет кэширования результатов вызовов функций и возврата кэшированного результата при повторном вызове функции с теми же входными данными.
Python 3 позволяет легко реализовать мемоизацию. Просто импортируйте lru_cache или cache из functools и примените декоратор.

Рекурсия в Python
Если очень просто, то рекурсивными функциями считаются те функции, которые вызывают сами себя. 
Например, напишем функцию для вычисления факториала:
factorial(5) = 120 factorial(3) = 6 factorial(7) = 5040
Сначала сделаем это с помощью цикла:
def factorial(number): x = 1 for i in range(1, number+1): x *= i return x factorial(5) #returns 120
И теперь решение с помощью рекурсивной функции:






def factorial(number): if number == 1: return 1 return number * factorial(number - 1) factorial(5) #returns 120
Рекурсия применяется тогда, когда решение становится более понятным. Применение рекурсии не ускоряет работу программы, а наоборот, может ее замедлить. Но рекурсия делает код более понятным для программиста и в такой код проще вносить изменения.
Стек вызовов
Для понимая того как работают рекурсивные функции, нужно понимать, что такое стек вызовов.
В каждой программе есть специальный стек, в котором сохраняется информация о вызовах функций. Он называется стек вызовов и именно с его помощью программа запоминает, куда она должна вернуться и ещё множество других вещей. Стеки работает по принципу LIFO (last in, first out).
Стек вызовов работает так:

При вызове вложенной функции, основная функция, откуда был вызов останавливается и создается блок памяти по новый вызов.
В ячейку памяти записываются значения переменных и адрес возврата (место, откуда была вызвана функция).
Если вызовов других функций нет, то из вложенной функции управление возвращается в основную.

Когда вы вызываете функцию из функции, вызывающая функция временно приостанавливается в частично завершенном состоянии.
Лучше всего схематично посмотреть на то, как выглядит стек. По сути это некая стопка, где программа хранит определенные данные, некий контекст вызова (значения, адрес возврата и пр.).






Более схематично разобраться с тем, как работает рекурсивная функцию можно на pythontutor.com для примера возьмите код, который был дан выше.
Рекурсивный и базовый случаи
Так как рекурсивная функция вызывает саму себя, то достаточно легко ошибиться и сделать такой вызов бесконечным ��
P.S. На самом деле бесконечным он не будет, так как рано или поздно переполниться стек. Но если что-то пошло не так нажмите в терминале Ctrl (Cmd) + C.
Итак, рекурсия всегда делится на базовый и рекурсивный случаи.
Когда вы пишите рекурсивную функцию, то обязательно нужно указать случай, когда рекурсия должна прерваться — это и есть базовый случай.
Рекурсивный случай отвечает за рекурсию и приведению к базовому случаю.






Вернемся к примеру с вычислением факториала:
def factorial(number): if number == 1: return 1 return number * factorial(number - 1)
Здесь за базовый случай отвечает кусок кода:
if number == 1: return 1
А за рекурсивный:
return number * factorial(number - 1)
В рекурсивном случае мы на каждом новом вызове функции уменьшаем значение number и тем самым, с каждым шагом, становимся всё ближе к базовому случаю. Если бы на последней строке мы указали return number * factorial(number) , то функция бы зависла, так как значение number оставалось бы неизменным.
Примеры
Напишем несколько рекурсивных функций, чтобы чуть больше разобраться с тем как это устроено: функцию для суммирования массива чисел, функцию для поиска наибольшего числа в массиве и бинарный поиск.
Функция sum_numbers
Для начала нам нужно определить базовый и рекурсивный случай. 
Базовым случаем здесь может быть пустой массив или массив из одного элемента. В случае с пустым массивом нам нужно будет вернуть 0, а с одним элементом — его значение. Я буду придерживаться того, что базовый случай это пустой массив.






def sum_numbers(numbers): if len(numbers) == 0: return 0 return numbers[0] + sum_numbers(numbers[1:])
Выше в коде происходит следующее:

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


Вот как это выглядит при визуализации на pythontutor.com 
Важно отметить, что этот пример академический и его не стоит использовать в работе, т.к. в питоне есть встроенная функция sum() .
Поиск наибольшего числа в массиве
def get_max_value(numbers): if len(numbers) == 2: if numbers[0] > numbers[1]: return numbers[0] else: return numbers[1] max_value = get_max_value(numbers[1:]) if numbers[0] > max_value: return numbers[0] else: return max_value
Тут нужно понять следующее — с помощью рекурсии мы сокращаем наш массив до базового случая, когда остается всего лишь два числа. Эти числа мы сравниваем между собой и возвращаем наибольшее число из двух. 
В max_value на «обратном проходе» сначала сохранится результат сравнения двух последних чисел массива, далее в последнем блоке if мы будем сравнивать что больше — текушее максимальное значение или первый элемент массива, который сейчас в блоке стека.







Опять же, данный пример скорее академический, потому что код с циклом будет выглядеть гораздо проще и читабельнее:
def get_max_value(numbers): max_value = 0 for number in numbers: if number > max_value: max_value = number return max_value
Бинарный поиск
def bin_search(target, numbers, left_position, right_position): if right_position target: return bin_search(target, numbers, left_position, mid_position) else: return bin_search(target, numbers, mid_position + 1, right_position)
На вход нам нужно получить помимо целевого числа для поиска и отсортированного массива нужно получить левую позицию и правую (начало и конец массива). Внутри функции их определить не выйдет, так как они будут на каждом проходе рекурсии меняться.
Далее по алгоритму:

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

На каждом проходе значение mid_position сдвигается правее или левее, но сам массив остается неизменным.
Устранение рекурсии в Python
Привет, Хабр! Представляю вашему вниманию перевод статьи "Removing a recursion in Python, part 1" автора Эрика Липперта (Eric Lippert).






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

Игрок находится в произвольной клетке на пронумерованном поле;
Цель вернуться в клетку №1;
Если игрок находится на чётной клетке, он платит одну монету и проходит половину пути к клетке №1;
Если игрок находится на нечётной клетке, он может заплатить 5 монет и сразу перейти на первую клетку или заплатить одну монету и сделать один шаг к клетке №1 — на чётную клетку.

Вопрос заключается в следующем: какое наименьшее количество монет необходимо заплатить, чтобы вернуться из текущей клетки в первую.
Задача имеет очевидное рекурсивное решение:
def cost(s): if s 

Однако эта программа падала, достигая максимальной глубины рекурсии, вероятнее всего из-за того, что автор вопроса экспериментировал с очень большими числами. 
Следовательно возникает вопрос: как превратить рекурсивный алгоритм в итерационный на Python?






Перед тем как мы начнем, хочу отметить, что конечно существуют более быстрые решения этой конкретной задачи, сама по себе она не очень интересна.
Скорее эта задача послужила лишь отправной точкой в вопросе, как в общем случае избавиться от единственного рекурсивного вызова в программе на Python.
Смысл в том, что можно преобразовать любой простой рекурсивный метод и избавиться от рекурсии, а это всего лишь пример, который оказался под рукой.
Техника, которую я собираюсь показать, конечно не совсем соответствует тому, как принято писать на Python, вероятно решение в Python-стиле использовало бы генераторы или другие возможности языка.
Что я хочу показать здесь, так это как избавиться от рекурсии, используя последовательность маленьких и безопасных преобразований, приводящих функцию к такой форме, в которой легко произвести замену рекурсии на итерацию.
Для начала давайте посмотрим как привести программу к такой форме.






На первом шаге нашего преобразования я хочу чтобы вычисления производимые до рекурсивного вызова сводились к вычислению аргумента, а вычисления, после рекурсивного вызова, производились в отдельном методе, который принимает результат рекурсивного вызова.
def add_one(n): return n + 1 def get_min(n): return min(n + 1, 5) def cost(s): if s 

Вторым шагом я хочу вынести вычисление аргумента в отдельную функцию:
# . def get_argument(s): if s % 2 == 0: return s // 2 return s - 1 def cost(s): if s 

На третьем шаге, я хочу добавить вспомогательную функцию, которая будет выбирать функцию-продолжение, вызываемую после возврата из рекурсии.
Обратите внимание, что вспомогательная функция возвращает функцию.
#. def get_after(s): if s % 2 == 0: return add_one return get_min def cost(s): if s  

Теперь запишем это в более общей и краткой форме:
#. def is_base_case(s): return s  

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

В базовом случае: 

вычисляем значение, которое нужно вернуть;
возвращаем его.


вычисляем аргумент рекурсии;
производим рекурсивный вызов;
вычисляем возвращаемое значение;
возвращаем его.

Кое-что важное на что необходимо обратить внимание на этом шаге — это то, что after не должен сам содержать вызовов cost .
Способ, который я показываю здесь, удаляет единственный рекурсивный вызов.
Если у вас 2 и более рекурсии, то нам понадобится другое решение.
Как только мы привели наш рекурсивный алгоритм к такой форме, преобразовать его в итеративный уже просто.
Хитрость в том, чтобы представить, что происходит в рекурсивной программе.
Как мы делаем рекурсивный спуск: мы вызываем get_argument перед рекурсивным вызовом и вызываем функцию after после возврата из рекурсии.
То есть, все вызовы get_argument происходят перед всеми вызовами after. 
Поэтому мы можем преобразовать это в 2 цикла: первый вызывает get_argument и формирует список функций after, а второй вызывает все функции after:
#. def cost(s): # Создаём стек из функций "after". Все эти функции # принимают результат рекурсивного вызова и возвращают # значение, которое вычисляет рекурсивный метод. afters = [ ] while not is_base_case(s): argument = get_argument(s) after = get_after(s) afters.append(after) s = argument # Теперь у нас есть стек функций "after" : result = base_case_value(s) while len(afters) != 0: after = afters.pop() result = after(result) return result
Больше никакой рекурсии!
Выглядит как магия, но все что мы здесь делаем — то же самое, что делала рекурсивная версия программы и в том же порядке.
Этот пример отражает мысль, которую я часто повторяю о стеке вызовов: его цель сообщить то, что произойдёт дальше, а не то, что уже произошло!
Единственная полезная информация в стеке вызовов в рекурсивной версии программы — это какое значение имеет after, поскольку эта функция вызывается следующей, а все остальное на стеке не важно.
Вместо использования стека вызовов, как неэффективного и громоздкого способа хранения стека after, мы можем просто хранить стек функций after.
В следующий раз мы рассмотрим более сложный способ удаления рекурсии на Python.


Похожие публикации:

Font awesome что это
Zxx что это
Как найти хакера
Что означает protected