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

Нам не нужны дешёвые сенсации! :)

Хм.Как-то парадоксально звучит?

А память? Или в Java экономить память не принято?

Только ваша рекурсия стек засирает.

> А память? Или в Java экономить память не принято?

Garbage Collector, пулы объектов. Да не в этом дело. То, что там рекурсия быстрее - тыщщу лет как известно. Просто когда делали VM, понимали, что ООЯ. А значит - огромное количество вызовов методов, и очень большая глубина рекурсии. И соптимизировали сразу. Вот и всё.

Так что не удивительно это.

> А значит - огромное количество вызовов методов, и очень большая глубина рекурсии. И соптимизировали сразу. Вот и всё.

Дело абсолютно не в этом. Дело примерно в том, что выделение памяти в куче примерно на два порядка медленнее, чем на стеке. Поэтому положив все на стек мы естественно выигрываем в скорости.

На C++ результаты были бы довольно похожие, вероятно.

>Garbage Collector

А какое отношение он имеет к рекурсии? IIRC, сборщик мусора удаляет только то, на что не ссылается ни одна ссылка (пардон за каламбур). С рекурсией все сложнее.

А чего тут гадать-то.. Ясное дело.. ;-)

всё фигня, одни товарищи смогли доказать что на кластерах ява быстрее на порядок всего остального работает.

Майн Гат! Свершилось чудо! "Аппаратный" стек обогнал стек самодельный.

Гм, т.е. в яве итеративный метод сделан так хреново, что даже рекурсия его рвёт? :)

Бесстыжее вранье!

Никогда рекурсивный алгоритм вычисления чисел Фибоначи не обгонит итеративный!

всё в этой Java через j работает :-)

>Только ваша рекурсия стек засирает.

А как еще связанное дерево то построить?=)

Капец. Ну и нафиг такой бред постить? Сравнили стек вызовов JVM и стек, реализованный на куче.

>Дело абсолютно не в этом. Дело примерно в том, что выделение памяти в куче примерно на два порядка медленнее, чем на стеке.

Почему это? Необязательно. Наскаолько я помню, в .NET куча по принципу стека работает, т.е память выделяется только с хвоста. А при сборке мусора дырки в куче устраняются.

Причина думаю в стековой природе байт кода Java.

> Капец. Ну и нафиг такой бред постить? Сравнили стек вызовов JVM и стек, реализованный на куче.

+1 КГ/АМ, автор явно не знаком с алгоритмами. http://en.wikipedia.org/wiki/Dynamic_Programming

Поправьте заголовок на "В Java итеративный вызов метода даже ещё медленнее, чем рекурсивный" пожалуйста.

>Никогда рекурсивный алгоритм вычисления чисел Фибоначи не обгонит итеративный!

А ты трёхпараметрическую функцию Аккермана рискни в итеративный вариант развернуть. Даже на Си в несколько раз тормознее рекуррентного варианта выходит :D

А кто-то может объяснить гаивному человеку, зачем буржуи в тест итеративных методов добавляли весь этот мусор - Stack, ArrayList, массивы?
Посмотрите на рекурсивный исходник - там ТОЛЬКО вычисление суммы. А теперь на итеративный - там кроме вычисления суммы бред всякий с хранилищами выполняется. Бред это. Абсолютно неекономно. Или я чего не понял?

По ссылке не ходил (я же на ЛОРе? :D), но по самому принципу - редко
где требуется простой подсчёт суммы, как в случае Фибоначи. Обычно
при сопоставлении рекуррентных/итеративных алгоритмов в реале
требуется масса промежуточных и накопительных занчений. Вот, видимо,
в этом тесте что-то такое и подразумевалось.

Ежу понятно, что итеративный Фибоначи будет всегда и всюду быстрее.
Но такие простые случаи встречаются нечасто.

Попробуйте, например, на итерациях без накопления реализовать функцию
Аккермана:

              + X+1,                 если N=0
              | X,                   если N=1,  Y=0,
              | 0,                   если N=2,  Y=0,
    A(N,X,Y)= | 1,                   если N=3,  Y=0,
              | 2,                   если N=>4, Y=0,
              + A(N-1,A(N,X,Y-1),X), если N#0,  Y#0;

     где N,X,Y - целые неотрицательные числа.

>Бесстыжее вранье!

>Никогда рекурсивный алгоритм вычисления чисел Фибоначи не обгонит итеративный!

n-ое число Фибоначчи вообще считается за O(1) как floor(phi^n/sqrt(5)+1/2), где phi = (1 + sqrt(5))/2

Ёперный театр, как красиво. А, ведь, работает! Не знал... И тут, блин, золотое сечение :)

[:||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||:]

> Попробуйте, например, на итерациях без накопления реализовать функцию Аккермана:

Я не уверен, что можно вообще что-то реализовать без накопления

Фигня какая-то, а не тесты. Прочитав русское название новости, я было подумал, что там есть что-то интересное. На деле же оказались очевидные вещи... Оригинальное же название "Quantifying Recursion on the Java Platform" не такое тенденциозное, и оно гораздо более точное. Так что, анонимному автору новости - зачОт за умение сделать из мухи слона :)

Кстати, четвертый алгоритм "Hardcore Iterative" (надо же было так назвать) содержит ошибку, но которая себя не проявляет на тестированной выборке. Если окажется, что глубина дерева превышает 100, то тогда может наступить кердык...

накопление можно включать после определенного n. посмотри на код от dj bernstain по поиску простых чисел - там помимо прочих математических оптимизаций есть и накопление результатов, но оно включается не сразу.

> И тут, блин, золотое сечение :)

Все еще прикольнее, отношение двух последовательных чисел Фибоначчи в пределе стремится к золотому сечению :)

>Поправьте заголовок на "В Java итеративный вызов метода даже ещё медленнее, чем рекурсивный" пожалуйста.

+1.

Прочитал название - сразу же такая же мысль в голову пришла.

А это из формулы видно. Особенно, если округление убрать :) Я про это и говорю, что красиво.

Хотя, если вспомнить формулу золотого сечения, как 1/(1+1/(1+1/(1+1/(1+...)))), то, наверное, общность с Фибоначи откуда-то оттуда вылезает.

Интересное, блин, число :) Ладно, скажем, то же "пи" - оно из физики мира вылезает. Или "е" - оно в окружающем мире непосредственно не фигурирует, вроде бы (навскидку не могу вспомнить). Но "золотое сечение" - с одной стороны, абстракция, с другой - куча процессов и явлений реального мира, повязанных на него. Откуда, интересно?

Автор получил такие результаты лишь потому, что его итеративная реализация и рекурсивная отличаются. В итеративной реализации в стек записывается намного больше информации, чем нужно.

Григор

>> Ёперный театр, как красиво. А, ведь, работает! Не знал... И тут, блин, золотое сечение :)

Да там в этих числах че токо не зарыто :) Даже на треугольнике Паскаял они вылязят. Вот только больно мне еэта формула не нравится, зачем floor вызывать, кога можно без него точную алгебраичскую формулу записать для a(n) ? Или подразумевалось, что считать будем на компутере а там корни вычисляются неточно ? Рассморенная последовательность частный случай так назыаемых возвратных последоваелностей

Гармония. Например, если хочешь, чтобы прямоугольник выглядел красиво, то нужно, чтобы его стороны соотносились друг к другу как отношение чисел Фибоначчи. Это правило очень широко используется в архитектуре. Еще египтяне использовали золотое сечение при строительстве пирамид.

А вообще, эти формулы вылазят из функционального уравнения, записанного для трех последовательных чисел.

"Автор получил такие результаты лишь потому, что его итеративная реализация и рекурсивная отличаются. В итеративной реализации в стек записывается намного больше информации, чем нужно."

Вот и я о том - будь там одинаковый смысл и наполнение во всех пяти тестах, уже можно было бы о какой то объективности говорить.

Вот, еще одно красивое математическое тождество: e^(pi*i)=-1, где i - мнимая единица :)

>>А вообще, эти формулы вылазят из функционального уравнения, записанного для трех последовательных чисел.

"Функциональное", как Вы выразились, урванение выглядит так: q^2-q-1=0 и является простым алгебраическим уравнением второго порядка, их в отличии от функциональных уравнений, изучают в школе. Общая формула для последовательности Ф: a(n)=C1*q_1^n+C2*q_2^n, где константы C1, C2 определяются по начальным членам a(1), a(2) ( задайте их любыми), а указанные формулы получаются при a(1)=a(2)=1, не более того. q_1,2 - корни уравнения Просто повезло что уравнение получилось как при золотом сечении.

>>Гармония. Например, если хочешь, чтобы прямоугольник выглядел красиво, то нужно, чтобы его стороны соотносились друг к другу как отношение чисел Фибоначчи...

Блестеть эрудицией идите в Что?Где?Когда? Человек спросил почему некое число, именуемое золотым сечением, много где себя проявляет. Он вовсе не спрашивал, где оно себя проявляет. Лучше бы рассказали, как греки заметили, что именно при таком отношении сторон картинка очнь гармонично смотрится. Я уверен, что это всго лишь приближение а не точное выражение для прямоугольника, "идеального" с точки зрения чловеческого глаза ;)

Кажись у золотого сечения нет никакого физического смысла (как и у числа e), это всего лишь положительный корень часто встречаемого квадратного уравнения.

> Хотя, если вспомнить формулу золотого сечения, как 1/(1+1/(1+1/(1+1/(1+...)))), то, наверное, общность с Фибоначи откуда-то оттуда вылезает.

Посмотри внимательно дроби внимательно: 1, 2, 3/2, 5/3, 8/5, 13/8,...

хехе :) a[n]/a[n-1]

> Кажись у золотого сечения нет...

А как диагонали равностороннего пятиугольника относятся к его сторонам? Ага. Число ничуть не хуже pi в этом смысле.

> хехе :) a[n]/a[n-1]

Я бы сказал F(n). То есть phi (золотое сечение) = lim(F(n+1)/F(n))

Интересно... Java 5 vs. Java 6 :

$ /opt/jdk5/bin/javac -Xlint:unchecked recursion/RecursionTester.java
...

$ /opt/jdk5/bin/java recursion/RecursionTester
Recursion Tester v1.0
Java(TM) 2 Runtime Environment, Standard Edition
1.5.0_07-b03
creating tree with branch factor 5...100001 nodes created in 331718417ns.
summing with recursion 1...average time=3343212, average memory=0
summing with recursion 2...average time=11699565, average memory=901270
summing with stack 1...average time=18003372, average memory=30784
summing with stack 2...average time=23909295, average memory=901196
summing with stack 3...average time=4313067, average memory=30792

$ /opt/jdk6/bin/java recursion/RecursionTester
Recursion Tester v1.0
Java(TM) SE Runtime Environment
1.6.0-b105
creating tree with branch factor 5...100001 nodes created in 212115507ns.
summing with recursion 1...average time=2605448, average memory=0
summing with recursion 2...average time=10188652, average memory=1107961
summing with stack 1...average time=15453126, average memory=26771
summing with stack 2...average time=25040601, average memory=1107880
summing with stack 3...average time=3836996, average memory=26792

$ /opt/jdk6/bin/javac -Xlint:unchecked recursion/RecursionTester.java
...

$ /opt/jdk6/bin/java  recursion/RecursionTester
Recursion Tester v1.0
Java(TM) SE Runtime Environment
1.6.0-b105
creating tree with branch factor 5...100001 nodes created in 193648355ns.
summing with recursion 1...average time=2604850, average memory=0
summing with recursion 2...average time=10172209, average memory=1107961
summing with stack 1...average time=15475609, average memory=26771
summing with stack 2...average time=24635427, average memory=1107880
summing with stack 3...average time=3814792, average memory=26792

Ты всегда такой добрый по вторникам, или сегодня решил сделать исключение? Просто человек испытывает восхищение от этой штуки. Я испытываю не меньший. Короче, не мешай делиться радостью с человеком! ;)

P.S. Не понимаю, чем тебя не устроило исходное уравнение F_{n+1} = F_n + F_{n-1}, где F_0 = F_1 = 1?

> "Функциональное", как Вы выразились, урванение выглядит так: q^2-q-1=0 и является простым алгебраическим уравнением второго порядка, их в отличии от функциональных уравнений, изучают в школе. Общая формула для последовательности Ф: a(n)=C1*q_1^n+C2*q_2^n, где константы C1, C2 определяются по начальным членам a(1), a(2) ( задайте их любыми), а указанные формулы получаются при a(1)=a(2)=1, не более того. q_1,2 - корни уравнения Просто повезло что уравнение получилось как при золотом сечении.

Кстати, никогда не стоит быть таким самоуверенным! ;)

--------------------

F_{n+1} = F_n + F_{n-1} ==>

F_{n+1}/F_n = 1 + F_{n-1}/F_n = 1 + 1 / (F_n/F_{n-1}) ==>

полагаем q_n = F_n / F_{n-1} ==>

q_{n+1} = 1 + 1 / q_n ==>

только если существует предел lim q_n = q ==>

q = lim q_n = lim q_{n+1} = 1 + 1 / lim q_n = 1 + 1 / q ==>

очевидно (q != 0) ==>

q^2 - q - 1 = 0

Fecit :)

Что касается общего решения, то, кажется, оно находится из того же разностного уравнения, которое я привел выше. Метод решения совершенно аналогичен методу решения похожего дифф. уравнения, но с небольшой поправкой. Приведенная общая формула очень напоминает тот самый метод решения. Пишу "кажется", потому что последний раз я занимался этим делом без малого 15 лет назад. Поэтому некоторые детали могу уже не так хорошо помнить. А лезть в гугл и проверять ради этого мне как-то в лом :)

>Дело примерно в том, что выделение памяти в куче примерно на два порядка медленнее, чем на стеке.

Нету в Java никакого стека в этом смысле.

>Дело абсолютно не в этом. Дело примерно в том, что выделение памяти в куче примерно на два порядка медленнее, чем на стеке.

несомненно. однако в жаба, выделение памяти в куче на 0.00001% медленнее чем на стеке - ибо отличается только (одним?) сравнением (контроль выхода за границу свободной зоны в юнг дженерейшн). так шта мимо кассы.

>На C++ результаты были бы довольно похожие, вероятно.

вероятно нет. например самый дурацкий способ посчитать фибоначчи в лоб выигрывает на жаба даже если в варианте на С++ (с помощью шаблонов) сделать ручной луп анроллинг, хотя байт-код (жаба) и асм (С++) практически один в один и аллокации на хипе нет. очевидно, что жвм за кадром как то оптимизирует рекурсию.

>Если окажется, что глубина дерева превышает 100, то тогда может наступить кердык...

Даже раньше. Просто количество необработанных чайлдов в момент времени.

>вероятно нет. например самый дурацкий способ посчитать фибоначчи в лоб выигрывает на жаба даже если в варианте на С++ (с помощью шаблонов) сделать ручной луп анроллинг, хотя байт-код (жаба) и асм (С++) практически один в один и аллокации на хипе нет. очевидно, что жвм за кадром как то оптимизирует рекурсию.

да, забыл добавить, что в итерактивной реализации код на С++ рвет жабу и без всякого анроллинга.

Тема производительности не раскрыта. Хорошо бы посмотреть во что компайлер превращает этот якобы рекурсивный код.