Рекурсия потребляет больше памяти
Обновлено: 05.07.2024
У меня ОЗУ 2 Гб. У нас есть приложение, которое выполняет операции экспорта / импорта. У нас есть рекурсивная функция, которая имеет одну локальную переменную типа Set, которая продолжает заполняться на каждой итерации. Этот набор продолжает расти, и в какой-то момент у нас заканчивается память.
Есть ли альтернативная структура данных, которая может оптимально использовать память?
Вот примерный код
Альтернативная структура не очень поможет. Допустим, вы перешли на класс, который использует половину памяти. Тем не менее, вы только откладываете гибель.
Размер структуры 2 ГБ обычно означает, что вам нужно переключиться на дисковую структуру, базу данных или хэш-таблицу с отображением в память.
Рассматривайте фрагменты данных по частям, а не все сразу.
Если только вы не находитесь в очень конкретном случае, когда вам нужны все данные для возможности экспорта (что маловероятно)
На мгновение сравните вызов исходного метода:
К вашему последующему рекурсивному вызову:
Если между ними не происходит чего-то волшебного, вы просто повторно вызываете метод с его собственным набором аргументов. Я подозреваю, что вы хотели вставить здесь «exportLocal» вместо «exportSets», потому что иначе, в чем был смысл exportLocal.setShared.begin ()? Вы просто продолжаете воссоздавать новый exportLocal, сообщая ему о начале, повторении и т. Д.
Короче говоря, я думаю, что проблема в ошибке кодирования, а не в рекурсии.
В качестве примечания - можете ли вы придумать способ сделать это циклом, а не рекурсией? Циклы почти всегда быстрее, проще, легче понять и быстро отлаживать.
Если ваша рекурсия потребляет 2 ГБ памяти, у вас, вероятно, возникнут проблемы с любым типом структуры данных в памяти. Можете ли вы опубликовать часть своего кода, чтобы мы могли лучше понять, что вы делаете?
Одна из идей может заключаться в использовании таблицы базы данных для хранения набора по мере его создания. Вы можете вставить новую запись для каждой рекурсии, и эта запись может иметь ссылку FK на родительскую запись в таблице. Таким образом, вы можете перемещаться вверх и вниз по рекурсии, следуя родительским ссылкам в записях.
Я не думаю, что рекурсия имеет какое-то отношение к вашей проблеме. Проблема просто в том, что данные, которые вы создаете, велики. Переход к итеративному решению здесь не поможет. Как уже указывалось, записывайте вывод по мере прохождения, а не сохраняйте его в структуре в памяти.
Однако вы можете свести к минимуму то, что находится в стеке, передав указатели в ваших рекурсивных вызовах, а не целые структуры.
Как распределяется память при вызове рекурсивных функций?
Функция имеет собственную выделенную память. Когда он вызывается, параметры (не переданные по ссылке) и переменные получают память. Итак, когда функция вызывается снова из своего тела, как память выделяется для переменных и параметров второго вызова?
Решение
Каждый рекурсивный вызов таким образом добавляет новый кадр стека, а затем возвращает его, когда возвращается. Если рекурсия не достигает базового случая, стек будет быстро исчерпан, что приведет к одноименной аварии переполнения стека.
Другие решения
Вызов функции рекурсивно выполняется так же, как и любая другая функция. Таким образом, память будет распределена так же, как если бы вы вызывали любую обычную функцию.
Это так же, как вызов любой другой функции. Переменные (не переданные по ссылке) размещаются в стеке. Когда функции начинают возвращаться (т.е. достигается базовый случай), стек извлекается в том порядке, в котором он был помещен в стек при каждом вложенном рекурсивном вызове.
Когда функция (позвоните, если func1 ) вызывает другую функцию func2 ), данные, необходимые для выполнения func2 помещается в стек. Это не меняется для рекурсивных функций (когда func2 такой же как func1 ).
Если вызывается рекурсивная функция 10 раз рекурсивно, там будет 10 стековые кадры, каждый из которых соответствует одному вызову функции.
Когда вызывается функция, необходимые параметры помещаются в стек. Когда функция завершает свою задачу, параметры выскакивают и счетчик программ восстанавливается.
Не существует исключения для рекурсивных функций.
Память для автоматических переменных выделяется на стек . Когда вы вызываете другую функцию (рекурсивно собственную или какую-либо другую), стековые кадры до сих пор остаются в их состоянии, и мы выделяем больше памяти (скажем так) в стеке для размещения локальных переменных этой новой функции. Когда функция заканчивается, новый кадр стека отбрасывается, и мы возвращаемся к предыдущему (calee) кадру стека.
Вы можете играть с любым отладчиком по вашему выбору, чтобы понять вещи еще лучше. Если вы что-то не понимаете, пожалуйста, спросите.
Рекурсия использует память стека для выполнения
Просмотрите приведенный ниже пример.
Давайте посмотрим в сегменте стека для рекурсии.
Позволять NODE1 -> NODE2->NULL Где NODE1 и NODE2 являются объектами структуры.
Что ваша функция делает:
Надеюсь, что это поможет вам.
Написанные вами функции (строки кода) хранятся в текстовом сегменте, и при его вызове он выделяется в памяти стека, а память для переменных (кроме статических) также выделяется в стеке в данном кадре.
Рекурсивные функции ничем не отличаются от своих обычных функций, которые вызываются n раз. поэтому его память (фрейм) также выделяется в стеке n раз.
Рекурсивные методы всегда лучше, чем итеративные методы в Java?
Кроме того, они всегда могут использоваться вместо итерации и наоборот?
Рекурсивные методы всегда лучше, чем итеративные методы в java?
Нет
Кроме того, они всегда могут использоваться вместо итерации и наоборот?
Вы можете всегда сделать рекурсивную функцию итеративной. (если память справится с этим, см. интересную ссылку здесь)
В некоторых случаях лучше использовать рекурсию (например, при работе с деревьями.. путешествие по двоичному дереву и т.д.). Для меня, если использование циклов не сложнее и гораздо сложнее, чем рекурсия, я предпочитаю использовать циклы.
Рекурсия более дорогостоящая в памяти, но иногда она более понятная и понятная.
Использование циклов увеличивает производительность, но рекурсия иногда может быть лучше для программиста (и его производительности).
Пример
Рассмотрим эти две реализации для факториала:
Итерационный:
рекурсии:
Какой способ более читабельный?
Очевидно, что он рекурсивный, он прямолинейный и может быть написан и успешно запущен с первой попытки. Это просто перевод математического определения в Java !
Какой метод более эффективен?
Возьмем, например, num = 40 , здесь сравнение времени:
2993 для рекурсивного
2138 для итеративного
конечно, разница будет больше, если число больше.
Рекурсия хороша для программистов, чтобы понять программу, но во многих случаях они вызывают stackoverflow, поэтому всегда предпочитают итерацию над ними.
Должен ли я использовать рекурсию или итерацию?
Как выбрать: зависит от вашего языка и удобства написания рекурсивного решения.
Существует три типа рекурсии, основанных на том, как напрямую они могут быть преобразованы в итерацию:
Трудно дать вам решающий ответ на какой тип алгоритма использовать, потому что он зависит от конкретного случая. Например, общий рекурсивный случай учебника последовательности Фибоначчи невероятно неэффективен с использованием рекурсии, поэтому лучше использовать итерацию в этом случае. И наоборот, перемещение дерева может быть реализовано более эффективно с использованием рекурсии.
Чтобы ответить на ваш второй вопрос, да, любой итерационный алгоритм может быть реализован с использованием рекурсии и наоборот.
Обычно рекурсивные методы требуют нескольких строк кода, но глубоко задуманы о вашем алгоритме. Если вы допустили логическую ошибку, вы, вероятно, получите StackOverflowError .
Здесь следует 2 примера программирования для факториала:
Iteractive:
Рекурсивный:
Всегда полезно отражать разные идеи для каждого предложения, всегда рассматривая строки кода, сложность, ясность, сплоченность и т.д.
Строго говоря, рекурсия и итерация одинаково сильны. Любое рекурсивное решение может быть реализовано как итеративное решение со стеком. Обратное преобразование может быть более сложным, но наиболее тривиальным является просто передача состояния вниз по цепочке вызовов.
В Java существует одна ситуация, когда рекурсивное решение лучше, чем (наивное) итеративное, и одна ситуация, когда они в основном эквивалентны. В большинстве других случаев итеративное решение будет превосходным, поскольку служебные служебные вызовы функций избегают.
Если функция использует стежок неявно, тогда рекурсивное решение будет обычно превосходить. Рассмотрим поиск по глубине:
по сравнению с эквивалентным итерационным решением
В итеративном случае вам придется заплатить за любой мусор, созданный объектом Stack<> . В рекурсивном случае вы будете использовать стек процесса, который не будет создавать мусор или выделять какую-либо память. Рекурсивное решение уязвимо для, но в противном случае будет работать быстрее.
В большинстве других ситуаций итеративное решение будет превосходить. Например, если вы хотите выполнить поиск по ширине, тогда вы можете использовать Queue вместо Stack в итеративном решении и заставить его работать мгновенно, а преобразование его в рекурсивное решение требует, чтобы вы платили как для неявного стека в стеке вызовов, так и для оплаты очереди.
что ты имеешь в виду лучше? каждая рекурсия также может быть реализована с итерациями и наоборот. иногда рекурсия легче понять. однако, поскольку рекурсия раздувает стек, многие вложенные вызовы могут вызвать исключение из памяти. В этом случае рекурсия явно не является вашим лучшим выбором.
Всегда ли в Java рекурсивные методы лучше итеративных?
Также могут ли они всегда использоваться вместо итерации и наоборот?
- 10 Они не лучше и могут легко вызвать StackOverflow, если набор данных слишком велик.
- Какой у вас источник? Приведите несколько примеров / контрпримеров, чтобы подкрепить свое утверждение.
- @Hoon Надеюсь, на ваш вопрос ответили. Отметьте его как принятый. Базовая этика stackoverflow :)
- возможный дубликат рекурсии или итерации?
- Вопрос может быть закрыт как дублирующий, но не как неконструктивный
Всегда ли рекурсивные методы лучше, чем итерационные методы в java?
Нет
Также могут ли они всегда использоваться вместо итерации и наоборот?
В некоторых случаях лучше использовать рекурсию (например, при работе с деревьями . перемещением по двоичному дереву . и т. Д.). Для меня, если использование циклов не сложнее и не намного сложнее, чем рекурсия, я предпочитаю использовать циклы.
Рекурсия использует больше памяти, но иногда она более четкая и читаемая. Использование циклов увеличивает производительность, но иногда рекурсия может быть лучше для программиста (и его производительности).
Итак, в заключение, решение, что использовать - рекурсию или итерацию, зависит от того, что вы хотите реализовать, и что для вас более важно (читаемость, производительность . ) и спрашивая рекурсия или итерация это как просить элегантность или производительность.
пример
Рассмотрим эти две реализации для факториал:
Итеративный:
Рекурсия:
Какой метод более читабельный?
Очевидно, рекурсивный, он прост и может быть написан и успешно запущен с первой попытки - он просто переводит математическое определение в Java !
Какой метод более эффективным?
Взять к примеру num = 40 , вот сравнение времени:
2993 для рекурсивного
2138 для итеративного
конечно разница будет больше, чем больше num ..
- 2 Я не согласен с предпосылкой этого ответа. Читаемость рекурсии и итерации - вопрос субъективный. Методика, которую один программист считает наиболее удобочитаемой, может отличаться для другого imo.
- Оператор if в примере итерации не нужен, и я считаю, что в любом случае он приведет к одинаковому количеству циклов. Интересно, что если я реализую это в Rust (просто потому, что я это вроде как знаю) и просматриваю сборку, ложное условие цикла while переходит в ветвь if вместо дублирования кода возврата. Если я удалю оператор if, он помещает код возврата сразу после условия while, которое выглядит более эффективным при факториале (n> 1) и столь же эффективным при n
Существует три типа рекурсии в зависимости от того, как напрямую они могут быть преобразованы в итерацию:
- Оптимизируемый хвостовой вызов, в котором самая последняя операция в методе есть рекурсивный вызов. Их можно преобразовать прямо в цикл.
- Рекурсия, которую нельзя оптимизировать по хвостовому вызову, поскольку она требует сохранения информации между вызовами, но не требует стека. Факториал, выраженный как fact(N) - классический пример: в рекурсивной формулировке последняя операция - это не рекурсивный вызов, а умножение. Эти типы рекурсивных вызовов можно легко преобразовать в оптимизируемую форму хвостового вызова, а затем в итеративную форму (чтобы преобразовать факториал в оптимизируемую форму хвостового вызова, вы должны использовать версию с двумя аргументами fact(n, acc) , где acc - накопленный результат).
- Рекурсия, которая требует сохранения состояния при каждом вызове. Классический пример - это предварительный обход дерева: при каждом вызове вы должны помнить родительский узел. Невозможно преобразовать это напрямую в итерацию. Вместо этого вы должны создать свой собственный стек для хранения состояния каждого вызова.
- 1 @downvoter - объяснишь? У вас есть итеративная реализация Quicksort, которая не управлять собственным стеком?
- Да, вам может понадобиться явная структура стека
Рекурсия хороша для программистов, чтобы понять программу, но часто они вызывают переполнение стека, поэтому всегда предпочитают итерацию над ними..
Дело в том, что рекурсия редко бывает наиболее эффективным подходом к решению проблемы, а итерация почти всегда более эффективна. Это связано с тем, что выполнение рекурсивных вызовов обычно связано с большими накладными расходами из-за того, что стек вызовов так интенсивно используется во время рекурсии.
Это означает, что многие языки компьютерного программирования будут тратить больше времени на поддержку стека вызовов, чем они фактически будут выполнять необходимые вычисления.
Рекурсия использует больше памяти, чем итерация? В общем, да. Это связано с широким использованием стека вызовов.
Что делать: рекурсию или итерацию?
Рекурсия обычно используется из-за того, что ее проще реализовать, и она обычно более элегантна, чем итерационные решения. Помните, что все, что делается в рекурсии, также может выполняться итеративно, но с рекурсией обычно возникает недостаток производительности. Но, в зависимости от проблемы, которую вы пытаетесь решить, этот недостаток производительности может быть очень незначительным , и в этом случае имеет смысл использовать рекурсию. С рекурсией вы также получаете дополнительное преимущество, заключающееся в том, что другим программистам будет легче понять ваш код , что всегда полезно.
что значит лучше? каждая рекурсия также может быть реализована с итерациями, и наоборот. иногда рекурсию легче понять. однако, поскольку рекурсия увеличивает стек, многие вложенные вызовы могут вызвать исключение нехватки памяти. В этом случае рекурсия явно не лучший выбор.
Трудно дать вам однозначный ответ о том, какой тип алгоритма использовать, потому что это зависит от конкретного случая. Например, распространенный в учебниках случай рекурсии последовательности Фибоначчи невероятно неэффективен при использовании рекурсии, поэтому в этом случае лучше использовать итерацию. И наоборот, обход дерева может быть реализован более эффективно с помощью рекурсии.
Чтобы ответить на ваш второй вопрос, да, любой итеративный алгоритм может быть реализован с использованием рекурсии и наоборот.
Строго говоря, рекурсия и итерация одинаково эффективны. Любое рекурсивное решение может быть реализовано как итеративное решение со стеком. Обратное преобразование может быть более сложным, но наиболее тривиальным является просто передача состояния по цепочке вызовов.
В Java есть одна ситуация, когда рекурсивное решение лучше, чем (наивное) итеративное, и одна ситуация, когда они в основном эквивалентны. В большинстве других случаев итеративное решение будет лучше, так как исключены накладные расходы на вызов функции.
Если функция использует стек неявно, рекурсивное решение обычно лучше. Рассмотрим поиск в глубину:
по сравнению с эквивалентным итерационным решением
В итеративном случае вам придется платить за любой мусор, созданный Stack<> объект. В рекурсивном случае вы будете использовать стек процесса, который не будет создавать мусор или выделять память. Рекурсивное решение уязвимо для переполнения стека, но в противном случае будет работать быстрее.
Если функция использует хвостовую рекурсию, то два решения будут эквивалентными, поскольку JIT преобразует рекурсивное решение в итеративное. Хвостовая рекурсия - это когда последнее, что делает функция, это рекурсивно вызывает себя, позволяя компилятору игнорировать любое накопленное состояние. Например, обход списка
Поскольку "walkList" - это последнее, что делается в функции, JIT по существу преобразует его в "n = n.getNext (); goto start", что сделает его эквивалентным итеративному решению.
В большинстве других ситуаций итеративное решение будет лучше. Например, если вы хотите выполнить поиск в ширину, вы можете использовать Queue вместо Stack в итеративном решении, и оно будет работать мгновенно, в то время как преобразование его в рекурсивное решение требует, чтобы вы платили как за неявный стек в стеке вызовов, так и за очередь.
Обычно рекурсивные методы требуют нескольких строк кода, но глубокого размышления над вашим алгоритмом. Если вы сделаете логическую ошибку, вы, вероятно, получите StackOverflowError .
Вот два примера программирования для факториала:
Итеративный:
Рекурсивный:
Всегда полезно размышлять над разными идеями для каждого предложения, всегда учитывая строки кода, сложность, ясность, сплоченность и т. д.
Читайте также: