что быстрее, цикл или рекурсия?
Длинная рекурсия небезопасна.
Независимо от компилятора, на вложенностях порядка 10.000 быстрее своя реализация стека и цикла по этому стеку - "мнимая рекурсия"
Независимо от компилятора, на вложенностях порядка 10.000 быстрее своя реализация стека и цикла по этому стеку - "мнимая рекурсия"
если компилятор нормальный, то ассемблерный код должен быть одинаков в обоих случаях. как следствие, скорость - тоже.
сомневаюсь, что "нормальный" в таком отношении существует - все локальные переменные на стек положут все компиляторы, имхо.
автору - 10^6 это 12, в курсе?
автору - 10^6 это 12, в курсе?
да я вообще тут рядом пробегал 
я имел ввиду, что в таком случая рекурсия будет хвостовой и поэтому ее выгоднее разворачивать, что обычно и делается (то есть один и тот же стек будет реюзаться)
ага, рекурсию про чётные числа компилятор сумеет в цикл развернуть?
при чем тут четные числа 
http://www.linux.org.ru//view-message.jsp?msgid=771586&anonymous=hide
во, нашел тот тред, где советуют рекурсию вместо циклов делать
я че думаю, у меня прога с циклами есть, как бы её убыстрить... хехехе...
во, нашел тот тред, где советуют рекурсию вместо циклов делать
я че думаю, у меня прога с циклами есть, как бы её убыстрить... хехехе...
для безинетных
типа, если рекурсивная функция вызвала себя тысячный раз - то выйти из рекурсии. как это в сях вообще делается то? я даж функций то никогда не писал...
Re: люди, как рекурсию сделать?
Сосчитать размер стека, потребляемый ф-ей при одном входе, умножить на 1000 и ограничить стек полученым числом. И оно сразу выйдет, прямо в ОС. IMHO.
DonkeyHot ** (*) (19.01.2005 16:16:37)
Ответ на: Re: люди, как рекурсию сделать? от DonkeyHot 19.01.2005 16:16:37
Re: люди, как рекурсию сделать?
> Сосчитать размер стека, потребляемый ф-ей при одном входе, умножить на 1000 и ограничить стек полученым числом. И оно сразу выйдет, прямо в ОС. IMHO.
рекурсивный вызов не обязательно увеличивает использование стэка ..
простно нужно корректно определять termination conditions ..
lg ** (*) (19.01.2005 16:53:37)
Re: люди, как рекурсию сделать?
2 KIV & Moridin:
Как бабки базарные... Что, никак нельзя без ругани обойтись?
2lg
Такой тезис:
Допустим, я нарисовал некий алгоритм с рекурсией. Все минимизировал и оптимизировал.
Утверждение: если теперь я тупо переведу рекурсию в итерации, то на рельной железяке оно (итеративное) будет не медленнее. Просто потому, что вызов функции всегда дороже перехода.
Если функции синлайнить (кстати, gcc не умеет инлайнить рекурсивные функции, по крайней мере мой gcc 3.2 то, конечно, разницы вообще не будет.
Мы же, к сожаления, работаем не с виртуальной машиной, а с реальной железякой.
Die-Hard ***** (*) (19.01.2005 19:34:52)
Re: люди, как рекурсию сделать?
Moridin (19.01.2005 19:36:36):
> Потому как больше возможностей для оптимизации.
Я же написАл, что мы все соптимизировали!
Die-Hard ***** (*) (19.01.2005 19:41:49)
Re: люди, как рекурсию сделать?
Moridin (19.01.2005 19:37:54):
> На современных процессорах довольно часто вызов функции ДЕШЕВЛЕ безусловного перехода! Артефакт предсказателя ветвлений, как правило...
Голословно.
Если уж на то пошло, всегда имеются возможности управлять конвейером явно, делать преферчинг и т.п.
Я не понимаю, что ты кипятишься. Если есть аргументы, так приведи. Ты же предпочитаешь делать голословные утверждения и обзываться.
Die-Hard ***** (*) (19.01.2005 19:50:00)
Ответ на: Re: люди, как рекурсию сделать? от Die-Hard 19.01.2005 19:34:52
Re: люди, как рекурсию сделать?
> Допустим, я нарисовал некий алгоритм с рекурсией. Все минимизировал и оптимизировал.
> Утверждение: если теперь я тупо переведу рекурсию в итерации, то на рельной железяке оно (итеративное) будет не медленнее. Просто потому, что вызов функции всегда дороже перехода.
точно! только если мы в начале двяностых .. в наше время по большому счету рекурсия оказывается чаще быстрее чем лупинг даже на таких железках как мы сейчас имеем .. кто-то даже помоему проводил тесты по этому поводу и был поражен (к сожалению не сохранил ссылку, но попробуй поищи)
> Мы же, к сожаления, работаем не с виртуальной машиной, а с реальной железякой.
В теории рекурсия всегда не медленнее лупинга, но на практике пока все еще это не так хотя приближается ...
кстати нашел вот показательную выдержку из AoA(Art of Assembly Language) [надеюсь никто не ставит под сомнение ее авторитетность?
]
...there are only a few recursive algorithms that you cannot implement in an iterative fashion. However, many recursively implemented algorithms are more efficient than their iterative counterparts and most of the time the recursive form of the algorithm is much easier to understand...
lg ** (*) (19.01.2005 22:30:51)
Ответ на: Re: люди, как рекурсию сделать? от lg 19.01.2005 22:30:51
Re: люди, как рекурсию сделать?
2lg :
А что мы понимаем под рекурсией? Можно определение?
Программа в конце концов транслруется в коды, и пара call/return -- всего лишь longjump'ы со спасением/чтением адреса возврата. Железяка по природе своей итеративна, она не знает, что такое функция. Если я формально напишу блок-схему странслированной в машинные коды программы, то я не получу ничего, кроме goto в некоторых ветвях.
Die-Hard ***** (*) (19.01.2005 23:30:51)
Ответ на: Re: люди, как рекурсию сделать? от Die-Hard 19.01.2005 23:30:51
Re: люди, как рекурсию сделать?
хорошо - рекурсия это метод создания модели используя рекурсивные функции. Рекурсивная функция это функция которая может явно или не явно использовать саму себя для вычисления результата
ну конечно итеративна а что с того .. еще раз повторю что для того чтобы добиться состояния модели после n-го шага рекурсии не обязательно применять функцию n раз .. в случае если ты можешь доказать идентичность моделей .. поэтому оптимизированная рекурсия совсем не означает что ты постоянно будешь вызывать какие то функции ..
так же при рекурсии у тебя не обязательно будет расти стек ..
просто всю это сложную работу по отимизации должен проделывать компилятор, а он не всегда с этим справляется, хотя в основном у него хорошо получается ..
lg ** (*) (20.01.2005 1:18:56)
Ответ на: Re: люди, как рекурсию сделать? от Die-Hard 19.01.2005 19:34:52
Re: люди, как рекурсию сделать?
>Как бабки базарные... Что, никак нельзя без ругани обойтись?
Прошу прощения у общественности. Но трудно общаться с Moridin.
To Die-Hard Ты сам скоро это поймешь!
KIV * (*) (20.01.2005 9:06:50)
Re: люди, как рекурсию сделать?
А вообще, longjmp/setjmp.
WFrag ** (*) (20.01.2005 12:10:13)
Ответ на: Re: люди, как рекурсию сделать? от WFrag 20.01.2005 12:10:13
Re: люди, как рекурсию сделать?
Как-то так:
[...]
jmp_buf continuation;
if(setjmp(continuation) == 0) {
superRecurrent(params, continuation);
}
/* Сюда выходим */
[...]
void superReccurent(params, jmp_buf continuation) {
...
if(someCondition) {
superRecurrent(params);
} else {
// Выходим из мега-рекурсии
longjmp(continuation, 1);
}
...
}
Но это не очень хороший вариант.
WFrag ** (*) (20.01.2005 12:15:48)
Re: люди, как рекурсию сделать?
WFrag (20.01.2005 14:59:29):
> Э-м-м-м. Не понял. Что это означает, поясни? Лямбда исчисление эквивалентно машине Тьюринга.
Современные процессоры ближе к машине Тьюринга и по своей прирове итеративны.
Moridin (20.01.2005 15:06:16):
> Спросили определенеи рекурсии - дал определение, чего ещё надыть?
Ну, вообще-то, вопрос, скорее, был риторическим.
Кстати, ты НЕ дал определние, Ты дал ссылку на топик, пройдя по которой можно найти ссылку на другой топик, в котором приводится определение рекурсивных функций. А в соседнем топике можно найти "напальцевые" рассуждения о рекурсии.
2KIV:
> В основе программы может лежать и более абстрактная субстанция нежели алгоритм.
Либо подробнее формулируй, либо вообще не пиши. Сейчас опять ругань начнется...
Die-Hard ***** (*) (20.01.2005 15:27:00)
Ответ на: Re: люди, как рекурсию сделать? от Die-Hard 20.01.2005 15:27:00
Re: люди, как рекурсию сделать?
>> В основе программы может лежать и более абстрактная субстанция нежели алгоритм.
>Либо подробнее форм
типа, если рекурсивная функция вызвала себя тысячный раз - то выйти из рекурсии. как это в сях вообще делается то? я даж функций то никогда не писал...
Re: люди, как рекурсию сделать?
Сосчитать размер стека, потребляемый ф-ей при одном входе, умножить на 1000 и ограничить стек полученым числом. И оно сразу выйдет, прямо в ОС. IMHO.
DonkeyHot ** (*) (19.01.2005 16:16:37)
Ответ на: Re: люди, как рекурсию сделать? от DonkeyHot 19.01.2005 16:16:37
Re: люди, как рекурсию сделать?
> Сосчитать размер стека, потребляемый ф-ей при одном входе, умножить на 1000 и ограничить стек полученым числом. И оно сразу выйдет, прямо в ОС. IMHO.
рекурсивный вызов не обязательно увеличивает использование стэка ..
простно нужно корректно определять termination conditions ..
lg ** (*) (19.01.2005 16:53:37)
Re: люди, как рекурсию сделать?
2 KIV & Moridin:
Как бабки базарные... Что, никак нельзя без ругани обойтись?
2lg
Такой тезис:
Допустим, я нарисовал некий алгоритм с рекурсией. Все минимизировал и оптимизировал.
Утверждение: если теперь я тупо переведу рекурсию в итерации, то на рельной железяке оно (итеративное) будет не медленнее. Просто потому, что вызов функции всегда дороже перехода.
Если функции синлайнить (кстати, gcc не умеет инлайнить рекурсивные функции, по крайней мере мой gcc 3.2 то, конечно, разницы вообще не будет.
Мы же, к сожаления, работаем не с виртуальной машиной, а с реальной железякой.
Die-Hard ***** (*) (19.01.2005 19:34:52)
Re: люди, как рекурсию сделать?
Moridin (19.01.2005 19:36:36):
> Потому как больше возможностей для оптимизации.
Я же написАл, что мы все соптимизировали!
Die-Hard ***** (*) (19.01.2005 19:41:49)
Re: люди, как рекурсию сделать?
Moridin (19.01.2005 19:37:54):
> На современных процессорах довольно часто вызов функции ДЕШЕВЛЕ безусловного перехода! Артефакт предсказателя ветвлений, как правило...
Голословно.
Если уж на то пошло, всегда имеются возможности управлять конвейером явно, делать преферчинг и т.п.
Я не понимаю, что ты кипятишься. Если есть аргументы, так приведи. Ты же предпочитаешь делать голословные утверждения и обзываться.
Die-Hard ***** (*) (19.01.2005 19:50:00)
Ответ на: Re: люди, как рекурсию сделать? от Die-Hard 19.01.2005 19:34:52
Re: люди, как рекурсию сделать?
> Допустим, я нарисовал некий алгоритм с рекурсией. Все минимизировал и оптимизировал.
> Утверждение: если теперь я тупо переведу рекурсию в итерации, то на рельной железяке оно (итеративное) будет не медленнее. Просто потому, что вызов функции всегда дороже перехода.
точно! только если мы в начале двяностых .. в наше время по большому счету рекурсия оказывается чаще быстрее чем лупинг даже на таких железках как мы сейчас имеем .. кто-то даже помоему проводил тесты по этому поводу и был поражен (к сожалению не сохранил ссылку, но попробуй поищи)
> Мы же, к сожаления, работаем не с виртуальной машиной, а с реальной железякой.
В теории рекурсия всегда не медленнее лупинга, но на практике пока все еще это не так хотя приближается ...
кстати нашел вот показательную выдержку из AoA(Art of Assembly Language) [надеюсь никто не ставит под сомнение ее авторитетность?
]...there are only a few recursive algorithms that you cannot implement in an iterative fashion. However, many recursively implemented algorithms are more efficient than their iterative counterparts and most of the time the recursive form of the algorithm is much easier to understand...
lg ** (*) (19.01.2005 22:30:51)
Ответ на: Re: люди, как рекурсию сделать? от lg 19.01.2005 22:30:51
Re: люди, как рекурсию сделать?
2lg :
А что мы понимаем под рекурсией? Можно определение?
Программа в конце концов транслруется в коды, и пара call/return -- всего лишь longjump'ы со спасением/чтением адреса возврата. Железяка по природе своей итеративна, она не знает, что такое функция. Если я формально напишу блок-схему странслированной в машинные коды программы, то я не получу ничего, кроме goto в некоторых ветвях.
Die-Hard ***** (*) (19.01.2005 23:30:51)
Ответ на: Re: люди, как рекурсию сделать? от Die-Hard 19.01.2005 23:30:51
Re: люди, как рекурсию сделать?
хорошо - рекурсия это метод создания модели используя рекурсивные функции. Рекурсивная функция это функция которая может явно или не явно использовать саму себя для вычисления результата
ну конечно итеративна а что с того .. еще раз повторю что для того чтобы добиться состояния модели после n-го шага рекурсии не обязательно применять функцию n раз .. в случае если ты можешь доказать идентичность моделей .. поэтому оптимизированная рекурсия совсем не означает что ты постоянно будешь вызывать какие то функции ..
так же при рекурсии у тебя не обязательно будет расти стек ..
просто всю это сложную работу по отимизации должен проделывать компилятор, а он не всегда с этим справляется, хотя в основном у него хорошо получается ..
lg ** (*) (20.01.2005 1:18:56)
Ответ на: Re: люди, как рекурсию сделать? от Die-Hard 19.01.2005 19:34:52
Re: люди, как рекурсию сделать?
>Как бабки базарные... Что, никак нельзя без ругани обойтись?
Прошу прощения у общественности. Но трудно общаться с Moridin.
To Die-Hard Ты сам скоро это поймешь!
KIV * (*) (20.01.2005 9:06:50)
Re: люди, как рекурсию сделать?
А вообще, longjmp/setjmp.
WFrag ** (*) (20.01.2005 12:10:13)
Ответ на: Re: люди, как рекурсию сделать? от WFrag 20.01.2005 12:10:13
Re: люди, как рекурсию сделать?
Как-то так:
[...]
jmp_buf continuation;
if(setjmp(continuation) == 0) {
superRecurrent(params, continuation);
}
/* Сюда выходим */
[...]
void superReccurent(params, jmp_buf continuation) {
...
if(someCondition) {
superRecurrent(params);
} else {
// Выходим из мега-рекурсии
longjmp(continuation, 1);
}
...
}
Но это не очень хороший вариант.
WFrag ** (*) (20.01.2005 12:15:48)
Re: люди, как рекурсию сделать?
WFrag (20.01.2005 14:59:29):
> Э-м-м-м. Не понял. Что это означает, поясни? Лямбда исчисление эквивалентно машине Тьюринга.
Современные процессоры ближе к машине Тьюринга и по своей прирове итеративны.
Moridin (20.01.2005 15:06:16):
> Спросили определенеи рекурсии - дал определение, чего ещё надыть?
Ну, вообще-то, вопрос, скорее, был риторическим.
Кстати, ты НЕ дал определние, Ты дал ссылку на топик, пройдя по которой можно найти ссылку на другой топик, в котором приводится определение рекурсивных функций. А в соседнем топике можно найти "напальцевые" рассуждения о рекурсии.
2KIV:
> В основе программы может лежать и более абстрактная субстанция нежели алгоритм.
Либо подробнее формулируй, либо вообще не пиши. Сейчас опять ругань начнется...
Die-Hard ***** (*) (20.01.2005 15:27:00)
Ответ на: Re: люди, как рекурсию сделать? от Die-Hard 20.01.2005 15:27:00
Re: люди, как рекурсию сделать?
>> В основе программы может лежать и более абстрактная субстанция нежели алгоритм.
>Либо подробнее форм
так сделай 2 варианта и сравни
походу, придется, совета хочется...
Программа в конце концов транслруется в коды, и пара call/return -- всего лишь longjump'ы со спасением/чтением адреса возврата. Железяка по природе своей итеративна, она не знает, что такое функция. Если я формально напишу блок-схему странслированной в машинные коды программы, то я не получу ничего, кроме goto в некоторых ветвях.Сынок, не читай эту хуйню. Они там мудаки. В свитерах с пузырями на локтях. Они под "железякой" понимают Машыну ПДП-11, которую они видели в институте, но к которой их не подпускали. Мне так кажется, по крайней мере.
Потому что даже я, остановившись в изучении ассемблера на х386 процессоре, точно знаю, что кроме jmp есть ещё инструкции call, ret, enter и leave (вот насчёт неё не уверен, иногда, возможно, её называют ret N а ещё дальше же пошла аппаратная поддержка эксепшенов кажется...
Сынок, не пиши эту хуйню.
Ну, допустим, ты знаешь некоторые команды ассемблера. И чо? Ты написал время их исполнения? Или что-то конкретное об предсказании дальнейшего хода программы?
Ну, допустим, ты знаешь некоторые команды ассемблера. И чо? Ты написал время их исполнения? Или что-то конкретное об предсказании дальнейшего хода программы?
Я это вообще к тому, что "железяка" на самом деле очень хорошо "знает, что такое функция".
Если тебя интересует время выполнения инструкции enter - бери мануаль и читай.
Если тебя интересует время выполнения инструкции enter - бери мануаль и читай.
гы, чувак, ты это там напиши, а я посмотрю, как там тебя аккуратетненько препарируют... а то яб тоже на перловые вопросы отвечал "дети мои, use strict;"...
p.s. и потом, людям работающим на опенсурс я более доверяю, нежели чем... А то блин, свитер ему не понравился...
p.s. и потом, людям работающим на опенсурс я более доверяю, нежели чем... А то блин, свитер ему не понравился...
гы, какая функция? вот какая железяка знает про функцию waitpid? ы? Не блин, на свитер тот чувак мож и ненакопил, за счет того, что он там на меня дурака пашет.
> В свитерах с пузырями на локтях. Они под "железякой" понимают Машыну ПДП-11, которую они видели в институте, но к которой их не подпускали. Мне так кажется, по крайней мере.
Ну-ну... Товарищ Die-Hard из процитированной ветки много и успешно копался с Итаниумами и SGI Altix.
Ну-ну... Товарищ Die-Hard из процитированной ветки много и успешно копался с Итаниумами и SGI Altix.
Просто считаем во что обходиться вызов функции не включая тело функции:
Запихтвание параметров в стек/регистры(с предварительным сохранением регистров
переход с сохранением адреса вызова функции
возврат из функции(востановление сохраненного адреса вызова функции
удаление из стека параметров/востановление регистров.
В случае рекурсии я верю, что можно сделать так, что параметры передаються через регистры и их сохранение нужно только перед первым вызовом функции, а выход из функции сделаем из последнего вызова (что я не назвал бы красивым решением).
Имеем для n вложенной рекурсии:
1 сохранение регистров
1 помещение параметров в регистры
n вызовов функции
1 возврат из функций
1 очистка стека от адресов возврата функции
1 востановление функции
в случае цикла с n итерациями имеем
1 сохранение регистров
1 задание параметров(в том числе и задание кол-ва итераций)
n вызывов loop ...(что считаем эквивалентным вызову процедуры, но может быть и не равным)
1 востановление регистров
Получаем, что если отбросить подготовительные и заключительные этапы, то эти методы выполняються примерно с одной скорость(при допуске, что что вызов функции выполняется со скоростью перехода на след. итерацию).
Но рекурсию иногда можно распаралелить, но отдельный разговор.
По поводу разворачивания рекурсии с помощью инлайн функций (если такое возможно то думаю все упрется в пропускную способность памяти, т.к. при достачно большом кол-ве итераций, кода будет значительно больше и проблема будет успевать его подавать на конвеер, при этом кеши эффективно работать не будут.
Жду критики моих рассуждений.
Запихтвание параметров в стек/регистры(с предварительным сохранением регистров
переход с сохранением адреса вызова функции
возврат из функции(востановление сохраненного адреса вызова функции
удаление из стека параметров/востановление регистров.
В случае рекурсии я верю, что можно сделать так, что параметры передаються через регистры и их сохранение нужно только перед первым вызовом функции, а выход из функции сделаем из последнего вызова (что я не назвал бы красивым решением).
Имеем для n вложенной рекурсии:
1 сохранение регистров
1 помещение параметров в регистры
n вызовов функции
1 возврат из функций
1 очистка стека от адресов возврата функции
1 востановление функции
в случае цикла с n итерациями имеем
1 сохранение регистров
1 задание параметров(в том числе и задание кол-ва итераций)
n вызывов loop ...(что считаем эквивалентным вызову процедуры, но может быть и не равным)
1 востановление регистров
Получаем, что если отбросить подготовительные и заключительные этапы, то эти методы выполняються примерно с одной скорость(при допуске, что что вызов функции выполняется со скоростью перехода на след. итерацию).
Но рекурсию иногда можно распаралелить, но отдельный разговор.
По поводу разворачивания рекурсии с помощью инлайн функций (если такое возможно то думаю все упрется в пропускную способность памяти, т.к. при достачно большом кол-ве итераций, кода будет значительно больше и проблема будет успевать его подавать на конвеер, при этом кеши эффективно работать не будут.
Жду критики моих рассуждений.
> Просто считаем во что обходиться вызов функции не включая тело функции:
> Запихтвание параметров в стек/регистры(с предварительным сохранением регистров
При правильных подходе, аргументы уже лежат в регистрах/на стеке,
результат --- тоже.
> возврат из функции(востановление сохраненного адреса вызова функции
> удаление из стека параметров/востановление регистров.
При правильном подходе, восстановление не требуется.
> а выход из функции сделаем из последнего вызова
> (что я не назвал бы красивым решением).
Scheme is _properly_ tail-recursive dialect.
Как учит нас RnRS.
> 1 помещение параметров в регистры
> n вызовов функции
_Переходов_.
> 1 возврат из функций
> 1 очистка стека от адресов возврата функции
_Одного_ адреса вовзрата. Самого первого.
> 1 востановление функции
> n вызывов loop ...(что считаем эквивалентным вызову процедуры, но может быть и не равным)
Точно такое же.
> Но рекурсию иногда можно распаралелить, но отдельный разговор.
Кроме этого есть и ещё преимущества.
В частности, лучше видно, какие регистры надо сохранять.
---
...Я работаю антинаучным аферистом...
> Запихтвание параметров в стек/регистры(с предварительным сохранением регистров
При правильных подходе, аргументы уже лежат в регистрах/на стеке,
результат --- тоже.
> возврат из функции(востановление сохраненного адреса вызова функции
> удаление из стека параметров/востановление регистров.
При правильном подходе, восстановление не требуется.
> а выход из функции сделаем из последнего вызова
> (что я не назвал бы красивым решением).
Scheme is _properly_ tail-recursive dialect.
Как учит нас RnRS.
> 1 помещение параметров в регистры
> n вызовов функции
_Переходов_.
> 1 возврат из функций
> 1 очистка стека от адресов возврата функции
_Одного_ адреса вовзрата. Самого первого.
> 1 востановление функции
> n вызывов loop ...(что считаем эквивалентным вызову процедуры, но может быть и не равным)
Точно такое же.
> Но рекурсию иногда можно распаралелить, но отдельный разговор.
Кроме этого есть и ещё преимущества.
В частности, лучше видно, какие регистры надо сохранять.
---
...Я работаю антинаучным аферистом...
Чуваки.
Вы ебан*лись?
Вы о чём вообще спорите?
Рекурсия и цикл это одно и то же.
Быстрее - код на ассемблере.
Ещё вопросы?
Вы ебан*лись?
Вы о чём вообще спорите?
Рекурсия и цикл это одно и то же.
Быстрее - код на ассемблере.
Ещё вопросы?
N> Жду критики моих рассуждений.
---
...Я работаю антинаучным аферистом...
---
...Я работаю антинаучным аферистом...
имхо, ты путаешь логическую рекурсию и физическую.
ps
если логическую рекурсию развернуть, то это уже будет цикл, а не рекурсия.
ps
если логическую рекурсию развернуть, то это уже будет цикл, а не рекурсия.
Как ты себе представляешь логически более быстрое?
---
...Я работаю антинаучным аферистом...
---
...Я работаю антинаучным аферистом...
не понял, спроси другими словами.
DG> имхо, ты путаешь логическую рекурсию и физическую
---
"Vyroba umelych lidi, slecno, je tovarni tajemstvi."
---
"Vyroba umelych lidi, slecno, je tovarni tajemstvi."
O(n) разве не логическая оценка?
Ну да.
И рекурсия и цикл (или циклы произвольной вложенности) жрут одинаковое количество памяти и времени, если их правильно написать, потому что это одно и то же. В случае рекурсии сложнее избавляться от дублирования данных, в случае цикла приходится ручками писать сохранение данных. В остальном - это ОДНО И ТО ЖЕ.
А быстрее - ассемблер.
И рекурсия и цикл (или циклы произвольной вложенности) жрут одинаковое количество памяти и времени, если их правильно написать, потому что это одно и то же. В случае рекурсии сложнее избавляться от дублирования данных, в случае цикла приходится ручками писать сохранение данных. В остальном - это ОДНО И ТО ЖЕ.
А быстрее - ассемблер.
> А быстрее - ассемблер.
Теоретик, блин
Теоретик, блин
>А быстрее - ассемблер.
Неправда. Если правильно написать компилятор, то самый оптимальный код который существует на ассемблере и выдаваемый компилятором будут одинаковы
Неправда. Если правильно написать компилятор, то самый оптимальный код который существует на ассемблере и выдаваемый компилятором будут одинаковы
Да, забыл маленький ньюанс: когда нужно выходить из рекурсии (при фиксированом кол-ве вызовов)?
т.е. нужно вести счетчик + в теле каждой функции проверять не выполни ли мы все вызовы, что не дается бесплатно, а при использование цикла это получаем бесплатно.
т.е. нужно вести счетчик + в теле каждой функции проверять не выполни ли мы все вызовы, что не дается бесплатно, а при использование цикла это получаем бесплатно.
Если я напишу "Убей Себя", это будет считаться флудом?
Вот я предлагаю сделать так: я пишу
Убей Себя
а ГПЖ или глебиус делают мне замечание только в том случае, если смогут придумать адекватный ответ.
Вот я предлагаю сделать так: я пишу
Убей Себя
а ГПЖ или глебиус делают мне замечание только в том случае, если смогут придумать адекватный ответ.
мое мнение такое: конвертить цикл в рекурсию и наоборот смысла не имеет, если алгоритм явно не требует рекурсии то и высасывать ее из пальца не надо, если алгоритм легко описывается с ее использованием то начинать чудить и разворачивать рекурсию в цикл тоже не надо.
в свое время ради спортивного, и не очень, интереса развернул рекурсию в цикл с простой имитацией стека параметров с минимумом действий ( заранее заказанный достаточной величины "стек" и пр. ) был неприятно удивлен тем фактом, что такая простая разверстка привела к потере эффективности на всех выборках. компилятор использовался VC,7 если не потерялся то могу и сам код привести. там строк 50 - 100... мерял время в тиках, рекурсия была очень глубокая.
PS чтобы писать на ассемблере эффективный код надо быть Специалистом в этой области.
в свое время ради спортивного, и не очень, интереса развернул рекурсию в цикл с простой имитацией стека параметров с минимумом действий ( заранее заказанный достаточной величины "стек" и пр. ) был неприятно удивлен тем фактом, что такая простая разверстка привела к потере эффективности на всех выборках. компилятор использовался VC,7 если не потерялся то могу и сам код привести. там строк 50 - 100... мерял время в тиках, рекурсия была очень глубокая.
PS чтобы писать на ассемблере эффективный код надо быть Специалистом в этой области.
Оставить комментарий
Barbie29
а я вот слыхал в районе linux.org.ru, что некоторые типы компиляторов быстрее цикл рекурсией делают, нежели чем просто for(i=0;i++;i<10^6){bla-bla-bla}Может, действительно сие так?