Python, рекурсивная функция и различные ускорения!
Сегодня я хотел бы изучить, как можно ускорить простую саморекурсивную функцию с помощью фреймворков/библиотек, таких как Python functools , numba , dask и tensorflow .
Рекурсивные функции необходимы для динамического программирования, которое, возможно, является наиболее интуитивным способом решения многих проблем, поскольку очень похоже на то, как мы думаем о процедуре решения этих проблем. Однако программистам обычно мешают ошибки «слишком глубокой рекурсии» и кажущееся бесконечным время ожидания даже для простой рекурсивной функции. Тщательная разработка алгоритма — один из способов решения этой проблемы. В этой статье основное внимание будет уделено использованию существующих фреймворков/библиотек для ускорения. Давайте начнем.
Наш базовый уровень
Этот алгоритм используется для решения проблемы, с которой я столкнулся на региональном соревновании по науке о данных на Data Squad Techjam 2018.
Проблема хотела, чтобы я нашел пароль к zip-файлу. Пароль представляет собой объединение нескольких возможных способов произношения этих слов.
Существует множество подходов к решению этой простой проблемы, но давайте не будем усложнять, взяв этот за основу.
147 мс — это время выполнения этой функции getWaysOfReading(20) на моем MacBook Pro.
Я использовал n=20 , потому что при n=30 время выполнения становится слишком большим.
lru_cache functools
Кэширование функции recurve — один из способов повысить скорость этой функции. Существует стандартная библиотека Python под названием functools . Он имеет функцию кэширования памяти lru_cache . Его можно использовать как декоратор Python. Я добавил строку кода, подобную этой.
Каждый раз, когда эта функция вызывается с одним и тем же набором аргументов (одними и теми же значениями), lru_cache будет пытаться найти ее в таблице, если кеш попал или нет. Если он сработает, вместо этого он вернет предыдущий вывод функции.
190 мкс — время выполнения. Удивительно, но я наблюдал примерно ускорение в 1000 раз с этой одной строкой кода.
Существует реализация дискового кэширования из библиотеки joblib , которая также отлично работает. В случае, если вам нужно кэширование больше памяти.
Своевременный компилятор Numba
Представьте, что наш код Python может быть таким же быстрым, как скорость чистого железа C/C++. numba купила это волшебство сообществу Python под эгидой Pydata.
Это будет реализация.
К сожалению, этот код выдаст ошибку. Потому что нумба-рекурсия еще не реализована в текущей реализации.
Многопроцессная автоматизация Dask
Dask использует неиспользуемые процессорные ядра, которые ранее были ограничены Python GIL. Подход с использованием нескольких ядер может увеличить время выполнения из-за узкого места связи между несколькими ядрами. В сочетании со многими тривиальными рабочими нагрузками, доставляемыми на каждое ядро, я не ожидаю значительного увеличения времени выполнения. В любом случае, давайте попробуем.
На эту функцию тратится 15 мс. Вау, это дает удивительное 10-кратное ускорение. Он также хорошо масштабируется, когда я увеличил n в 10 раз до n=200 за 16,6 мс (всего +1,1 мс).
Стремительное выполнение Tensorflow
Мы приближаемся к месту назначения
. Tensorflow — последний фреймворк, который стоит попробовать. Он использует тот же подход, что и numba. Он преобразует код в эффективный код, который работает на машинном уровне. Посмотрим, куда это нас приведет.
При таком подходе используется 31 сек с использованием тех же параметров и той же машины. Хорошая новость заключается в том, что мы знаем, что tensorflow можно легко запрограммировать рекурсивным образом. Плохая новость заключается в том, что существует много накладных расходов. Это в 100 раз медленнее, чем наш базовый уровень.
Номер 1 означает рррррррррррр….
Далее, dask , наша базовая линия и tensorflow
numba не могу. Попробуй еще раз на
Вот и все. Я надеюсь, что эта статья прольет свет на эти фреймворки/библиотеки, чтобы в следующий раз вы лучше поняли, какой из них больше всего подходит для вашей работы.
Does Python optimize tail recursion?
I have the following piece of code which fails with the following error:
RuntimeError: maximum recursion depth exceeded
I attempted to rewrite this to allow for tail recursion optimization (TCO). I believe that this code should have been successful if a TCO had taken place.
Should I conclude that Python does not do any type of TCO, or do I just need to define it differently?
8 Answers 8
No, and it never will since Guido van Rossum prefers to be able to have proper tracebacks:
You can manually eliminate the recursion with a transformation like this:
I published a module performing tail-call optimization (handling both tail-recursion and continuation-passing style): https://github.com/baruchel/tco
Optimizing tail-recursion in Python
It has often been claimed that tail-recursion doesn’t suit the Pythonic way of coding and that one shouldn’t care about how to embed it in a loop. I don’t want to argue with this point of view; sometimes however I like trying or implementing new ideas as tail-recursive functions rather than with loops for various reasons (focusing on the idea rather than on the process, having twenty short functions on my screen in the same time rather than only three «Pythonic» functions, working in an interactive session rather than editing my code, etc.).
Optimizing tail-recursion in Python is in fact quite easy. While it is said to be impossible or very tricky, I think it can be achieved with elegant, short and general solutions; I even think that most of these solutions don’t use Python features otherwise than they should. Clean lambda expressions working along with very standard loops lead to quick, efficient and fully usable tools for implementing tail-recursion optimization.
As a personal convenience, I wrote a small module implementing such an optimization by two different ways. I would like to discuss here about my two main functions.
The clean way: modifying the Y combinator
The Y combinator is well known; it allows to use lambda functions in a recursive manner, but it doesn’t allow by itself to embed recursive calls in a loop. Lambda calculus alone can’t do such a thing. A slight change in the Y combinator however can protect the recursive call to be actually evaluated. Evaluation can thus be delayed.
Here is the famous expression for the Y combinator:
With a very slight change, I could get:
Instead of calling itself, the function f now returns a function performing the very same call, but since it returns it, the evaluation can be done later from outside.
The function can be used in the following way; here are two examples with tail-recursive versions of factorial and Fibonacci:
Obviously recursion depth isn’t an issue any longer:
This is of course the single real purpose of the function.
Only one thing can’t be done with this optimization: it can’t be used with a tail-recursive function evaluating to another function (this comes from the fact that callable returned objects are all handled as further recursive calls with no distinction). Since I usually don’t need such a feature, I am very happy with the code above. However, in order to provide a more general module, I thought a little more in order to find some workaround for this issue (see next section).
Concerning the speed of this process (which isn’t the real issue however), it happens to be quite good; tail-recursive functions are even evaluated much quicker than with the following code using simpler expressions:
I think that evaluating one expression, even complicated, is much quicker than evaluating several simple expressions, which is the case in this second version. I didn’t keep this new function in my module, and I see no circumstances where it could be used rather than the «official» one.
Continuation passing style with exceptions
Here is a more general function; it is able to handle all tail-recursive functions, including those returning other functions. Recursive calls are recognized from other return values by the use of exceptions. This solutions is slower than the previous one; a quicker code could probably be written by using some special values as «flags» being detected in the main loop, but I don’t like the idea of using special values or internal keywords. There is some funny interpretation of using exceptions: if Python doesn’t like tail-recursive calls, an exception should be raised when a tail-recursive call does occur, and the Pythonic way will be to catch the exception in order to find some clean solution, which is actually what happens here.
Now all functions can be used. In the following example, f(n) is evaluated to the identity function for any positive value of n:
Of course, it could be argued that exceptions are not intended to be used for intentionally redirecting the interpreter (as a kind of goto statement or probably rather a kind of continuation passing style), which I have to admit. But, again, I find funny the idea of using try with a single line being a return statement: we try to return something (normal behaviour) but we can’t do it because of a recursive call occurring (exception).
Initial answer (2013-08-29).
I wrote a very small plugin for handling tail recursion. You may find it with my explanations there: https://groups.google.com/forum/?hl=fr#!topic/comp.lang.python/dIsnJ2BoBKs
It can embed a lambda function written with a tail recursion style in another function which will evaluate it as a loop.
The most interesting feature in this small function, in my humble opinion, is that the function doesn’t rely on some dirty programming hack but on mere lambda calculus: the behaviour of the function is changed to another one when inserted in another lambda function which looks very like the Y combinator.
Оптимизация хвостовой рекурсии в питоне
Почему вдруг ее нет? Не могут сделать? Правильно я понимаю, что абсолютно любая функция с рекурсией большой глубины приведет к ошибке переполнения стека?
Почему вдруг ее нет? Не могут сделать?
Можно попробовать реализовать самому: заменить рекурсию на цикл с сохранением промежуточных значений в списках. И посмотреть, что получится.
Потому что питон — это крайне перегруженный различными хаками язык, из-за чего интерпретатор не может знать, вызываешь ли ты функцию, конструктор объекта, написанный на Си обработчик операции-вызова, или еще черт пойми что. По этой причине все проекты оптимизации на этапе компиляции провалились, и живы остались только JIT оптимизаторы, которые конкретный фактически маршрут выполнения пытаются сократить для повторного прохода.
Правильно я понимаю, что абсолютно любая функция с рекурсией большой глубины приведет к ошибке переполнения стека?
Всё уже сделано до нас.
А взаимную рекурсию оно умеет? Плюс, оно на каждый шаг цикла кидает эксепшон. Это просто офигенная оптимизация, я тебе скажу.
интерпретатор не может знать, вызываешь ли ты функцию, конструктор объекта, написанный на Си обработчик операции-вызова, или еще черт пойми что
А как же он работает, когда фунуцию от объекта отличить не может? Это фигня полная.
А какие практические задачи обычно решают с помощью хвостовой рекурсии?
Решают при помощи рекурсии. А речь идет об оптимизации рекурсии интепретатором питона таким образом, что можно работать с бесконечной рекурсией без переполнения стека.
А какие практические задачи обычно решают с помощью хвостовой рекурсии?
Решают при помощи рекурсии.
Использование рекурсии очень сильно упрощает программу, если речь идет об объектах, которые сами определяются рекурсивно. Например списки или фрактальтные объекты.
Это первая попавшаяся ссылка. Скорее в шутку. «Оптимизация» и «Python» в одном предложении — это всегда юмор.
Нужно пребывать в терминальной стадии ФП головного мозга, чтобы определять список посредством рекурсии.
Что касается вещей вроде фракталов, деревьев, графов, то одной только *хвостовой* рекурсии не достаточно, чтобы реализовать весь набор интересных операций с ними. И, стало быть, оптимизация хвостовой рекурсии значительной выгоды для этих задач не даст..
«Оптимизация» и «Python» в одном предложении — это всегда юмор.
Because nested structures appear in almost every problem domain and programming environment, from databases to 3D graphics to filesystems, the act of iterating through these structures is common, so common that most programmers barely notice when they’re doing it. As such, generalizing the act of recursive traversals provides immediate real-world benefits: our new generalized traversal can replace a host of type-specific traversal functions. In addition, by decoupling how a function recurses over data from what the function actually does, we reduce cognitive overhead and can focus entirely on the core behavior of our recursive functions. No matter the structures in question—lists, directory hierarchies, control flow graphs, database records—recursion schemes bring us an orderly and predictable way to traverse them.
оптимизация хвостовой рекурсии значительной выгоды для этих задач не даст..
В питоне абсолютно любая функция с рекурсией большой глубины приведет к ошибке переполнения стека. Значит питон для задач указанных выше не подходит вообще.
абсолютно любая функция с рекурсией большой глубины приведет к ошибке переполнения стека?
Кэширование функций в Python
В сегодняшней статье мы рассмотрим как оптимизировать время выполнения программы в Python c помощью операции кэширования. Мы рассмотрим данную операцию на примере рекурсивной функции в Python. Но сначала — пара слов о рекурсии. Рекурсия — это понятие в программировании, при котором функция вызывает сама себя один или несколько раз. Данные типы функций часто сталкиваются с проблемами скорости, из-за того, что функция постоянно вызывает сама себя. Операция рекурсии занимает достаточно много памяти из за постоянного повторения одних и тех же шагов. Кэшировнаие или Мемоизация (англ. memoization от англ. memory и англ. optimization) помогает этому процессу, сохраняя значения, которые уже были рассчитаны для последующего использования. Давайте сначала вспомним что такое рекурсивные функции. Давайте посмотрим несколько примеров!
Написание факториальной функции.
Факториалы — один из самых простых примеров рекурсии, и является результатом умножения всех чисел меньших на единицу чем данное:
def factorial(n):
# установите базовый случай!
if n <= 1:
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 <= 1:
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 <= 1:
return n
else:
return fib( n – 1 ) + fib( n – 2 )
Мы получим тот же результат, что и в предыдущем примере, но на этот раз с меньшим количеством строк. Таким образом, язык Python предоставляет возможность оптимизации кода библиотекой functools.
Копирование материалов разрешается только с указанием автора (Михаил Русаков) и индексируемой прямой ссылкой на сайт (http://myrusakov.ru)!
Добавляйтесь ко мне в друзья ВКонтакте: http://vk.com/myrusakov.
Если Вы хотите дать оценку мне и моей работе, то напишите её в моей группе: http://vk.com/rusakovmy.
Если Вы не хотите пропустить новые материалы на сайте,
то Вы можете подписаться на обновления: Подписаться на обновления
Если у Вас остались какие-либо вопросы, либо у Вас есть желание высказаться по поводу этой статьи, то Вы можете оставить свой комментарий внизу страницы.
Порекомендуйте эту статью друзьям:
Если Вам понравился сайт, то разместите ссылку на него (у себя на сайте, на форуме, в контакте):
Она выглядит вот так:
Комментарии ( 0 ):
Для добавления комментариев надо войти в систему.
Если Вы ещё не зарегистрированы на сайте, то сначала зарегистрируйтесь.