Как ускорить рекурсивный алгоритм
Я пытаюсь решить задачу Hackerrank Игра Камней, (сокращенная) постановка задачи которого скопирована ниже.
Я придумал следующее решение:
алгоритм по существу является алгоритмом минимакса, поскольку он выглядит на один шаг вперед, а затем рекурсивно вызывает ту же функцию. Проблема в том, что в Hackerrank он заканчивается из — за тайм-аут:
действительно, я заметил, что оценки which_player_wins(40) уже занимает
2 секунды. Есть идеи для более быстрого решения, которое не будет тайм-аут?
3 ответов
из описания проблемы кажется, что вы можете сохранить промежуточные и окончательные результаты каждого расчета для использования в последующих расчетах. Если это так, рекурсивный алгоритм не является оптимальным. Вместо этого используйте динамический стиль программирования.
другими словами, сохраните глобальный массив, в котором хранятся результаты предыдущих определений выигрышей и проигрышей. Когда вы определяете для нового значения n , вместо того, чтобы рекурсировать весь путь до конца, используйте предыдущий определения.
например, когда вы доберетесь до n=10 , вы видите, что первый игрок, удаляющий 3 камня, оставляет 7 камней, которые вы уже видели как выигрыш для второго игрока. Таким образом, 10 камней-это выигрыш для первого игрока.
Я считаю, что ваш рекурсивный алгоритм снова вычислит результат для n=7 вместо использования предыдущей работы.
ваше решение будет работать (хотя и очень медленно), если у вас есть бесконечные уровни рекурсии. Но поскольку вы не повторно используете уже вычисленные результаты, вы очень быстро достигаете предела рекурсии Python. Одним из хороших решений, как было предложено выше, является переписывание кода с использованием нерекурсивного алгоритма.
кроме того, вы можете сохранить код у вас есть, но получить его повторно использовать любой результат, который вы уже видели раньше. Это называется memoization, и простой способ реализуйте это, чтобы добавить декоратор memoization к части кода, которая вычисляет следующий шаг. Вот способ использовать memoization для ускорения вашего рекурсивного алгоритма, который, я думаю, вы специально просили:
преобразовать весь код после первого else в функции next_move(n) это возвращает либо «Первый», либо «второй».
добавить memoize(f) функция, которая будет принимать next_move(n) и избегайте вызова рекурсии, если результат для n уже рассчитан.
добавить линию декоратора @memoize перед next_move определение.
это чрезвычайно ускоряет вычисление, а также снижает уровни рекурсии, необходимые. На моем компьютере N=100 решается за 0.8 МС.
после Рори Долтонсовет использовать динамическое программирование, я переписал which_player_wins метод следующим образом:
Мне нужно ускорить рекурсию
Мне задали решить задачу. Я написал код, но он работает медленно. Мне нужно ускорить рекурсию. Если n будет равен даже 70 расчеты займет очень много времени. Помогите мне улучшить мой код. Максимальное n может быть 500!
дело в том, что функция a(n) вызывается многократно, а значит рекурсий больше, чем нужно
можно вычислить a(n) однократно и дальше только использовать уже вычисленные значения
a(900) работает мгновенно, так что можно считать это оптимизацией 🙂
только учтите одну важную вещь, я не знаю как у питона, но при рекурсии у того же c++ вызовы запихиваются в стек и стек может просто переполниться
Оптимизация хвостовой рекурсии в питоне
Почему вдруг ее нет? Не могут сделать? Правильно я понимаю, что абсолютно любая функция с рекурсией большой глубины приведет к ошибке переполнения стека?
Почему вдруг ее нет? Не могут сделать?
Можно попробовать реализовать самому: заменить рекурсию на цикл с сохранением промежуточных значений в списках. И посмотреть, что получится.
Потому что питон — это крайне перегруженный различными хаками язык, из-за чего интерпретатор не может знать, вызываешь ли ты функцию, конструктор объекта, написанный на Си обработчик операции-вызова, или еще черт пойми что. По этой причине все проекты оптимизации на этапе компиляции провалились, и живы остались только 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.
оптимизация хвостовой рекурсии значительной выгоды для этих задач не даст..
В питоне абсолютно любая функция с рекурсией большой глубины приведет к ошибке переполнения стека. Значит питон для задач указанных выше не подходит вообще.
абсолютно любая функция с рекурсией большой глубины приведет к ошибке переполнения стека?
А где-то это не так?
Мне от питона каждый раз рыдать хочется после нормальных языков.
Где язык умеет оптимизировать хвост. рекурсию. Хаскель, Скала, лисп.
Питон сам по себе в
10 раз тормознее си-шки. Питон не умеет в многопоточность. С такими вводными, произносить слово «оптимизация» и одновременно сохранять серьезное выражение лица — невозможно.
Или ты под словом «оптимизация» подразумеваешь переписывание откровенного говнокода?
Вообще, для работы с большими контейнерами (бд, фс, и так далее) общепринято использовать курсоры (итераторы, указатели), а не рекурсию.
В питоне абсолютно любая функция с рекурсией большой глубины приведет к ошибке переполнения стека.
Если бы хвостовая рекурсия к переполнению не приводила, качественной разницы это не сделало бы.
Значит питон для задач указанных выше не подходит вообще.
Как быть со всеми теми, кто на питоне работает со списками, бд, фс и графами, и никаких трудностей не испытывает?
Вопрос так и остался почему не сделают? При такой популярности и широком использовании питона? Есть что-то принципиальное типа «глобальной блокировки интепретатора»?
Вопрос так и остался почему не сделают?
Не ясно, ради чего это делать.
Откуда в питоне указатели? Там же автоматическое управление памятью.
Напиши в питоне рекурсивную функцию n!(123456) тогда поймешь.
Ради того, что многие алгоритмы гораздо легче записываются в рекурсивной форме чем в итеративной.
Не в защиту питона, но любой рекурсивный алгоритм можно описать в виде цикла, так что не вижу проблемы.
Ради того, что многие алгоритмы гораздо легче записываются в рекурсивной форме чем в итеративной.
Да, именно так, но в случае хвостовой рекурсией есть ограничение в виде отсутствия возможности определить логику сразу после рекурсивного вызова, с таким ограничением многие алгоритмы резко теряют в понятности и проигрывают итеративным алгоритмам.
Это можно обойти путём передачи коллбэка. Но да, без всяких плюшек со стороны языка будет выглядеть всрато.
Вопрос так и остался почему не сделают?
Не ясно, ради чего это делать.
Напиши в питоне рекурсивную функцию n!(123456) тогда поймешь.
Не ясно, ради чего писать функцию, которая отлично пишется циклом, рекурсивно.
Не ясно, ради чего писать функцию, которая отлично пишется циклом, рекурсивно.
А как же он работает, когда фунуцию от объекта отличить не может? Это фигня полная.
По месту разбирается. И так — каждую операцию.
Можно попробовать реализовать самому: заменить рекурсию на цикл с сохранением промежуточных значений в списках. И посмотреть, что получится.
Рекурсия — это повторный вызов функции. При вызове функции локальные переменные неявно сохраняются на стеке вызовов. При повторных вызовах стек вызовов соответственно растёт.
Ничто не мешает сделать явный стек (в питоне обычно используют класс list) и сохранять туда значения явно.
В питоне абсолютно любая функция с рекурсией большой глубины приведет к ошибке переполнения стека.
Жавайте уточнять, что речь идет про CPython. Не все реализации питона страдают этой проблемой.