Самый быстрый выход из рекурсии в Java
Есть ли способ чисто и быстро уйти от рекурсии в Java? Есть способ вырваться из for loop с помощью оператора break; . Есть ли эквивалентный шаблон или метод выхода из рекурсии?
Я могу думать о создании отдельного потока, и как только значение вычислено, просто убить поток, а не поднимать стек рекурсии. Есть ли способ лучше?
Уже есть вопрос, в котором обсуждается, как вы можете выйти из рекурсии: здесь .
Я ищу более быстрый способ достичь этого, возможно, без возврата к стеку. Что-то вроде заявления goto или break .
Здесь рассматриваются следующие критерии:
- Простота рефакторинга для использования этого выхода
- Чистая производительность (чем быстрее, тем лучше)
- Длина на практике (чем быстрее написать / добавить, тем лучше)
Ответ, который я ищу, объяснит как производительность, так и простоту решения — этот вопрос задается в контексте алгоритмической конкуренции, поэтому предпочтительны решения, требующие меньшего количества рефакторинга.
Зачем мне это использовать?
Иногда при кодировании для некоторой алгоритмической конкуренции вам нужно вернуть значение изнутри рекурсии, и мне интересно, можете ли вы сделать это быстрее, используя такого рода перерыв. Подумайте об алгоритме, который выглядит так:
Ответы (7)
Ответ на ваш вопрос довольно прост:
Просто сделайте это обычным способом, т.е. самостоятельно раскрутите стек с помощью return s. Почему? Потому что это не так медленно, как вы думаете. Если вычисление в вашей рекурсии не является очень тривиальным, а глубина стека очень и очень высока, возврат никогда не окажет заметного влияния на время выполнения вашего алгоритма.
В основном у вас есть следующие возможности:
- Если возможно, трансформируйте свой алгоритм в итеративный.
- Преобразуйте свой алгоритм, чтобы он был конечным рекурсивным, и надейтесь, что виртуальная машина будет повторно использовать кадр стека. Тогда возвращение из рекурсии фактически равно одному простому возврату.
- Выбросить исключение. Однако это будет даже медленнее, чем возврат, потому что должна быть построена трассировка стека, которая в конечном итоге также проходит по стеку. Также необходимо размотать стек, чтобы проверить catch es. Вы ничего не выиграете.
Первые два варианта жизнеспособны, но не всегда возможны. Но, честно говоря, не думайте об этом. Возврат из глубокого стека — не то, что замедляет ваш алгоритм. Если у вас есть алгоритм с очень глубокой рекурсией, тогда у вас все равно есть проблема (переполнение стека, стоимость рекурсивных вызовов), и вам следует подумать о том, чтобы переписать свой алгоритм. Если глубина стека мала, это в любом случае не проблема.
Вот простая тестовая программа Java, чтобы показать вам, что я имею в виду:
Он вычисляет рекурсивную функцию, которая будет иметь глубину стека, равную входному параметру. Функция вычисляет квадратный корень в каждом кадре стека e для моделирования некоторых нетривиальных вычислений. Он также вычисляет ту же функцию итеративным способом. Чтобы разогреть JIT, программа сначала выполняется 9 раз без вывода результата; печатается только десятый результат. Вот мои результаты (мне пришлось увеличить размер стека до 1 гигабайта с помощью -Xss1g . Вот результаты на моей машине:
Как видите, для возврата из стека глубиной в один миллион требуется 3 миллисекунды. Большие размеры стека приводят к увеличению времени, возможно, из-за того, что стек больше не помещается в кэш L3. Однако, если вам нужны такие большие стеки, у вас все равно возникнет проблема, как описано выше. Запуск Java с максимальным размером стека 1 гигабайт — не лучшая идея. Любой размер стека ниже 131072 невозможно даже измерить в миллисекундах. В разумном алгоритме стек должен быть намного меньше этого, поэтому у вас всегда должно быть все в порядке.
Как видите, самым быстрым решением является итеративное решение, поэтому, если очень глубокая рекурсия оказывается слишком медленной, полностью избегайте ее, вместо того, чтобы пропускать только возврат.
Заключение
Если рекурсия для вас слишком медленная, полностью избавьтесь от нее. Если просто пропустить возврат, особого значения не будет.
Выход из рекурсии в Java
Рекурсия — это своего рода стиль «разделяй и побеждай», он разбивается, становясь все меньше (структура данных дерева), и я хочу, чтобы он полностью сломался, если обнаружено нарушение, что означает разрыв всех рекурсивных путей и возврат правда. Возможно ли это?
11 ответов
Вы можете вернуть код ошибки или изменить некоторую глобальную переменную, чтобы каждый рекурсивный экземпляр знал, чтобы «убить себя».
Что-то в этом роде.
Независимо от того, что вы делаете, вам придется раскрутить стек. Это оставляет два варианта:
- Магическое возвращаемое значение (как описано одним из Toms)
- Выбросьте исключение (как упомянуто thaggie)
Если случай, когда вы хотите, чтобы что-то умереть, редки, это может быть одна из тех ситуаций, когда бросание исключения может быть жизнеспособным выбором. И прежде, чем все скачут мне горло, помните, что одним из важнейших правил программирования является знание, когда это необходимо для нарушения правила.
Как оказалось, сегодня я провел оценку библиотеки zxing из кода google. На самом деле они используют исключения для множества управляющих структур. Мое первое впечатление, когда я это увидел, было ужасом. Они буквально вызывали методы десятки тысяч раз с разными параметрами, пока метод не генерирует исключение.
Это, безусловно, выглядело как проблема с производительностью, поэтому я внесла некоторые изменения, чтобы изменить ситуацию до использования возвращаемого значения magic. И знаешь, что? При работе в отладчике код был на 40% быстрее. Но когда я переключился на не-отладки, код был менее чем на 1% быстрее.
Я все еще не сумасшедший о решении использовать исключения для управления потоком в этом случае (я имею в виду, что исключения все время бросаются). Но это, конечно, не стоит моего времени для повторного внедрения, учитывая почти неизмеримую разницу в производительности.
Если ваше условие, которое вызывает смерть итерации, не является фундаментальной частью алгоритма, использование исключения может сделать ваш код намного более чистым. Для меня точка, в которой я принимаю это решение, — это то, что всю рекурсию нужно разматывать, тогда я бы использовал исключение. Если только часть рекурсии должна быть размотана, используйте магическое возвращаемое значение.
Выход из рекурсии в Java
Эта рекурсия является своего рода стилем «разделяй и властвуй», она разделяется при уменьшении (древовидная структура данных), и я хочу, чтобы она полностью разорвалась при обнаружении нарушения, то есть сломала все рекурсивные пути и вернула true. Это возможно?
11 ответов
Вы можете вернуть код ошибки или изменить некоторую глобальную переменную так, чтобы каждый рекурсивный экземпляр знал, что нужно «убить себя».
Что-то в этом роде.
Неважно, что вы делаете, вам придется раскручивать стек. Это оставляет два варианта:
- Волшебное возвращаемое значение (как описано одним из Томов)
- Брось исключение (как упомянуто тагги)
Если случай, когда вы хотите, чтобы вещи умирали, встречается редко, это может быть одна из тех ситуаций, когда выбрасывание исключения может быть жизнеспособным выбором. И прежде чем все начнут мне в этом горло, помните, что одно из самых важных правил программирования — знать, когда уместно нарушать это правило.
Как оказалось, сегодня я потратил на оценку библиотеки zxing из кода Google. Они на самом деле используют исключения для многих управляющих структур. Мое первое впечатление, когда я увидел это был ужас. Они буквально вызывали методы десятки тысяч раз с разными параметрами, пока метод не выдает исключение.
Это, безусловно, выглядело как проблема с производительностью, поэтому я внес некоторые коррективы, чтобы изменить магическое возвращаемое значение. И знаешь, что? Код был на 40% быстрее при запуске в отладчике. Но когда я переключился на отсутствие отладки, код был менее чем на 1% быстрее.
Я до сих пор не в восторге от решения использовать исключения для управления потоком в этом случае (я имею в виду, исключения генерируются постоянно). Но, безусловно, не стоит тратить время на его повторную реализацию, учитывая почти неизмеримую разницу в производительности.
Если ваше условие, приводящее к смерти итерации, не является фундаментальной частью алгоритма, использование исключения может сделать ваш код намного чище. Для меня, точка, в которой я бы принял это решение: если вся рекурсия должна быть размотана, я бы использовал исключение. Если нужно размотать только часть рекурсии, используйте магическое возвращаемое значение.
Условия выхода из рекурсии. StackOverflowError
Давайте еще раз посмотрим на рекурсивную задачу. В качестве примера можно рассмотреть поиск чисел Фибоначчи. Кто не помнит, последовательность Фибоначчи – элементы числовой последовательности, в которой первые два числа равны 0 и 1, а каждое последующее число равно сумме двух предыдущих чисел.
Напишем код для поиска и вывода таких чисел:
Перед первым вызовом рекурсивного метода printFibonacci , выведем первые два числа последовательности – ноль и единицу. Это нужно, потому что в рекурсивном методе мы выводим только сумму полученных параметров, а не сами параметры.
Выглядит ОК: получаем два числа, считаем их сумму, выводим ее в консоль, и снова вызываем рекурсивный метод printFibonacci . В качестве параметров передаем предыдущее (previous) и текущее число (current).
На самом деле в этом коде есть 2 ошибки. Их можно заметить, если запустить код.
Первая ошибка заключается в переполнении типа long . Уже 104-е число в нашей последовательности вывелось отрицательным, а это значит, что произошло переполнение типа long .
Вторая ошибка имеет другой характер. После найденного 12 тысяч с копейками числа, на экран выводится:
Здесь уместно вспомнить, что такое стек вызова методов в Java. Java-машина ведет запись всех вызовов функций. У нее есть для этого специальная коллекция – стек (Stack). Когда одна функция вызывает другую, Java-машина помещает в этот стек новый элемент StackTraceElement. Когда функция завершается, этот элемент удаляется из стека. Таким образом в этом стеке всегда хранится актуальная информация о текущем состоянии «стека вызовов функций». Дословный перевод ошибки StackOverflowError – «стек переполнен». В Javadoc-е написано: «Бросается, когда стек вызова слишком глубокий». В запущенной JVM есть специальная область памяти для хранения стека вызова методов. Размер этой области памяти зависит от ОС и настроек JVM. Кроме самого стека вызовов методов в этой области памяти хранятся примитивные переменные (конкретные значения параметров вызова метода) и адреса ссылочных переменных (в HEAP области памяти). Модель доступа к стеку – LIFO.
Исправленный пример с условием выхода
Исправления нашего кода начнем со второй проблемы.
Попробуем проблему решить в лоб: если маленький размер стека, то давайте его увеличим. Для этого нужно запустить JVM со специальным флагом «-Xss» и указать сколько выделить памяти под стек. Давай попробуем выделить 5 мегабайт. Выглядеть это в IDEA будет так:
Да, длина вывода увеличилась и сейчас составляет не 12+ тысяч найденных чисел последовательности, а 49+ тысяч. Но после какого-то числа все равно получаем StackOverflowError .
Можно пробовать еще увеличивать стек-область памяти, но принципиально ничего не изменится. Значит, будем искать проблему в логике. У рекурсии должна быть точка остановки. То есть должно быть какое-то условие, после которого рекурсивный метод не вызовется, и стек вызова будет возвращаться. Для того, чтобы определить такое условие, давайте конкретизируем задачу – выводить числовой ряд Фибоначчи до тех пор, пока они меньше, чем Integer.MAX_VALUE .
Напишем новый метод printFibonacciWithCondition , в котором учтем это условие. И в методе main вызовем именно новый исправленный метод.
После запуска кода действительно видим, что вывод завершился числом 1836311903. Перед этим числом было 1134903170. Их сумма 2_971_215_073, что действительно больше Integer.MAX_VALUE (2_147_483_647) .
Вместе с этим исправлением у нас автоматически исправилась ошибка с переполнением типа long . Если нужен более длинный числовой ряд, нужно использовать другие типы данных, например BigInteger .
Метод рекурсивного спуска и возврата
Давайте попробуем поэтапно проанализировать как выполняется наш код. Для это добавим метод echo и будем его вызывать перед и после рекурсивного вызова метода printFibonacciWithCondition .
В результате работы программы получим вывод:
Давайте графически проиллюстрируем, как это происходит.
Проговорим еще раз: вызывается метод printFibonacciWithCondition . В нем вычисляется текущее число. Если оно подходит нам, то выводим его и снова вызываем метод printFibonacciWithCondition с новыми параметрами.
Пока идет вызов рекурсивного метода – это называется «Рекурсивный спуск». Когда идет возврат по стеку вызова – «Рекурсивный возврат».