LINUX.ORG.RU
Новости — Java  

В Java рекурсивный вызов метода быстрее, чем итеративный


0

0
В опровержение бытующему среди программистов мнению о том, что рекурсивное "складывание" вызовов методов в стек способно "затормозить" исполнение программы, в статье описываются испытания 5 вариантов исполнения одного и того же алгоритма, 3 из которых рекурсивные. И угадайте, какой вариант оказывается быстрее? ;)

>>> Подробности

anonymous

Проверено: anonymous_incognito ()
← xinelib 1.1.4
Результаты тестирования шести ведущих фреймворков на производительность →
  1 2 →
Ответ на: комментарий от pustota1
> компайлер превращает этот

$ /opt/java6/bin/javap -c recursion/RecursionTester > test

$ /opt/java6/bin/ -c recursion/TreeNode >> test

$ vi test

:)

Bioreactor ★★★★★
()
Ответ на: комментарий от pustota1
>Хорошо бы посмотреть во что компайлер превращает этот якобы рекурсивный код.

Можно не смотреть - рекурсий не разворачивает.

А вот во что его превращает JIT вопрос отдельный.

r ★★★★★
()
Ответ на: комментарий от anonymous
>Вот только больно мне еэта формула не нравится, зачем floor вызывать, кога можно без него точную алгебраичскую формулу записать для a(n) ? Или подразумевалось, что считать будем на компутере а там корни вычисляются неточно ?

Да, floor(n+1/2) - это банальное округление. Правда, там точности не хватит. Только большие числа считаются достаточно точно. Та же единица даёт 0.7 с чем-то (утром считал, уже не помню точно).

KRoN73 ★★★★★
()
Ответ на: комментарий от anonymous
> n-ое число Фибоначчи вообще считается за O(1) как floor(phi^n/sqrt(5)+1/2), где phi = (1 + sqrt(5))/2

распространенное заблуждение. Это О(lg n) в терминах операций с вещественными числами бесконечной точности. В компьютерах таких не бывает.

dilmah ★★★★★
()
Ответ на: комментарий от KRoN73 
> Но даже в этом случае оно явно смотрится лучше, чем O(n) :)

гораздо красивее смотрится решение с возведением матрицы
 0 1
 1 1
в n-ю степень. Тоже O(lg n) но тут хоть оперировать нужно
целыми числами. Неограниченные целые проще реализовать чем
оценивать с какой погрешностью нужно вещественными числами
оперировать.
dilmah ★★★★★
()
Ответ на: комментарий от bugmaker
>Поправьте заголовок на "В Java итеративный вызов метода даже ещё медленнее, чем рекурсивный" пожалуйста.

+1 :)))
Ubnormal ★
()
Ответ на: комментарий от baka-kun
> Число ничуть не хуже pi в этом смысле.

Да нет. У пи есть физический смысл (и это трансцендентное число), а у золотого сечения (назовём его фи) - лишь алгебраический смысл (это не трансцендентное число).

Фи (1.618034) появляется из простейших алгебраический преобразований. Ну например, чтобы возвести фи в квадрат, надо просто прибавить к нему единицу. А чтобы вычислить обратное (1/n), надо просто отнять от него единицу.

Это всё из уравнения x^2 - x - 1 = 0 видно.

mihalych ★★★
()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.
  1 2 →
← xinelib 1.1.4
Java
Результаты тестирования шести ведущих фреймворков на производительность →