Форум: "Прочее";
Текущий архив: 2007.12.09;
Скачать: [xml.tar.bz2];
Вниз
Отрицательные стороны рекурсии. Найти похожие ветки
← →
Riply © (2007-11-08 03:29) [0]Здравствуйте !
Который раз вижу такую ситуацию:
Там где задача решается рекурсией буквально в две строчки,
люди идут на страшные ухищрения и "километры кода", лишь бы ее избежать.
Из каких соображений так поступают ?
P.S.
Полагаем, что глубина рекурсии не большая.
← →
KilkennyCat © (2007-11-08 03:40) [1]Это вопрос для начинающих? Или совет им использовать рекурсию?
← →
KilkennyCat © (2007-11-08 03:49) [2]http://www.intuit.ru/department/pl/plprolog/4/2.html
← →
Riply © (2007-11-08 03:54) [3]> [1] KilkennyCat © (08.11.07 03:40)
> Это вопрос для начинающих? Или совет им использовать рекурсию?
Нет. Это вопрос начинающего, просто страждущего узнать все плохие стороны рекурсии :)
Вот даже уснуть не могу: не дает она мне покоя :)
← →
Riply © (2007-11-08 03:58) [4]> [2] KilkennyCat © (08.11.07 03:49)
> http://www.intuit.ru/department/pl/plprolog/4/2.html
Спасибо. Но я же оговорилась: "Полагаем, что глубина рекурсии не большая".
← →
KilkennyCat © (2007-11-08 04:03) [5]Если рассматривать теорию, при верном алгоритме, плохих сторон нет.
Если практику, при "небольших глубинах" плохих сторон нет.
Подобное размазывание кода мне встречалось с целью ускорения работы графики. Это был полный идиотизм, ибо математический просчет там
занимал намного меньше времени, чем процесс отображения.
З.ы.
Мое мнение может не совпадать с моим мнением и ответственности не несу.
← →
KilkennyCat © (2007-11-08 04:04) [6]Еще вариант: изначально рекурсия не вырисовывалась, писалось наспех, типа, потом соптимизируем. ну а потом не наступило "потом".
← →
Riply © (2007-11-08 04:07) [7]Удалено модератором
Примечание: флуд
← →
Джо © (2007-11-08 04:10) [8]Удалено модератором
Примечание: флуд
← →
Riply © (2007-11-08 04:13) [9]Удалено модератором
Примечание: флуд
← →
Джо © (2007-11-08 04:30) [10]Удалено модератором
Примечание: флуд
← →
KilkennyCat © (2007-11-08 04:43) [11]Удалено модератором
Примечание: флуд
← →
Джо © (2007-11-08 04:54) [12]Удалено модератором
Примечание: флуд
← →
Riply © (2007-11-08 05:13) [13]Удалено модератором
Примечание: флуд
← →
Джо © (2007-11-08 05:28) [14]Удалено модератором
Примечание: флуд
← →
Джо © (2007-11-08 05:30) [15]Удалено модератором
Примечание: флуд
← →
Riply © (2007-11-08 05:30) [16]Удалено модератором
Примечание: флуд
← →
Джо © (2007-11-08 05:35) [17]Удалено модератором
Примечание: флуд
← →
Riply © (2007-11-08 05:42) [18]Удалено модератором
Примечание: флуд
← →
KilkennyCat © (2007-11-08 06:01) [19]Вот такая вот рекурсия.
← →
Джо © (2007-11-08 06:03) [20]> [19] KilkennyCat © (08.11.07 06:01)
> Вот такая вот рекурсия.
Рекурсия будет, если ее из Потрепаловки начнут опять закидывать в Начиниающим, а там создадут тему, в которой дадут ссылку на эту тему в Потрепаловке.
Или что-то в роде того.
← →
KilkennyCat © (2007-11-08 06:08) [21]а реинкарнация - это рекурсия? Начинается на одну и ту же букву. в каждом слове по две буквы "р", по одной "е", "к", "я", и их очередность совпадает. Кроме того, первая и последние пары букв также совпадают.
← →
Джо © (2007-11-08 06:14) [22]> [21] KilkennyCat © (08.11.07 06:08)
> а реинкарнация - это рекурсия? Начинается на одну и ту же
> букву. в каждом слове по две буквы "р", по одной "е", "к",
> "я", и их очередность совпадает. Кроме того, первая и последние
> пары букв также совпадают.
Я, конечно, не KilkennyCat, но мои фамилия/имя, если записать их русскими буквами, будут КС. Значит ли это что? Или не значит это что?
Зафлудили тему, это поразительно даже для Мастаков :)
← →
KilkennyCat © (2007-11-08 06:18) [23]
> Джо © (08.11.07 06:14) [22]
Это очень много значит! Это значит, что мы оба на этом форуме, причем в одной ветке.
← →
Мазут Береговой (2007-11-08 07:05) [24]Интересно как провода сходятся и расходятся... ишь ты!...
← →
homm © (2007-11-08 08:40) [25]Я один раз избавился от рекурсии, потому что это позволило ускорить алгоритм в 2 раза. С тех пор я заню, что вызов функции обходится очень дорого :)
← →
Рамиль © (2007-11-08 09:09) [26]ИМХО, по аналогии с указателями - есть люди у которых часть мозга, ответственная за понимание рекурсии, не работает:)
← →
Ega23 © (2007-11-08 09:11) [27]
> Это вопрос начинающего, просто страждущего узнать все плохие
> стороны рекурсии :)
Чтобы понять рекурсию, нужно понять рекурсию.
Только и всего.
← →
Sha © (2007-11-08 09:13) [28]Компиляторы хорошо оптимизируют небольшие рекурсивные алгоритмы.
В таких случаях отказ от рекурсии обычно не дает выигрыша в скорости.
← →
wendy parkinson (2007-11-08 09:18) [29]Sha © (08.11.07 09:13) [28]
Очевидно, здесь речь идет о хвостовой рекурсии.
Но как компилятор может оптимизировать, например, рекурсивный обход дерева, отказавшись от рекурсии?
← →
Steep (2007-11-08 09:21) [30]Есть задачи которыми не решить рекурсией - например поиск файлов с возможностью остановки и возобновления
← →
Sha © (2007-11-08 09:36) [31]> wendy parkinson (08.11.07 09:18) [29]
> Но как компилятор может оптимизировать, например, рекурсивный обход
> дерева, отказавшись от рекурсии?
Конечно компилятор не отказывается от рекуриии.
Имелось ввиду "отказ программиста от рекурсии путем разработки нерекурсивного алгоритма". Во.
Компиляторы обычно оптимизируют хвостовую рекурсию.
Кроме того, небольшое количество переменных в рекурсивном алгоритме
дает больший простор для оптимизации, например, все переменные могут
лежать в регистрах процессора.
← →
Sha © (2007-11-08 09:41) [32]Хорошей иллюстрацией служат, например, алгоритмы сортировки.
Часто рекурсивная версия алгоритма оказывается более быстрой.
← →
Romkin © (2007-11-08 10:06) [33]Отказываются от рекурсии из-за желания оптимизировать.
Я все время пользуюсь (пытаюсь) двумя правилами:
1. Не делайте оптимизацию.
2. Только для экспертов: не делайте оптимизацию раньше времени.
(с) не помню кто.
Но желание "ускорить", похоже, неистребимо :)
← →
TUser © (2007-11-08 12:11) [34]Во-первых многие помнят времена маленького стека. Сегодня это не очень актуально. По крайней мере у меня есть несколько рекурсивных программ, ничего работают. Могу сказать, что рекурсивные алгоритмы на порядок сложнее в отладке.
← →
Ega23 © (2007-11-08 12:11) [35]А в TSQL глубина рекурсии не должна превышать 32.
← →
Virgo_Style © (2007-11-08 12:14) [36]> Steep (08.11.07 09:21) [30]
> Есть задачи которыми не решить рекурсией - например поиск
> файлов с возможностью остановки и возобновления
Я, помнится, решал в те времена, когда питал к рекурсии почти необъяснимую неприязнь. Остановку-возобновление, правда, не делал, но проблемы не вижу. Правда, приходилось хранить все, что нашел, даже если впоследствии этот список не был нужен. Итог - отъедалась куча памяти под список каталогов (еще раз - если задача состоит именно в составлении списка, то это не есть недостаток), зато стек не забивался. Реализация сложнее, смысл неясен - но можно.
← →
Сусл © (2007-11-08 12:15) [37]Я в последнее время пишу как пишется не думаю о скорости. Зачастую оказывается, что оптимизировать потом существенно эффектевний, т.к. если оптимизируешь потом, то находишь действительно узкие места и оптимизируешь их, а не все подряд.
Если по теме, то я не вижу ничего плохого в рекурсии.
← →
Romkin © (2007-11-08 12:39) [38]Ega23 © (08.11.07 12:11) [35] А у Sybase вроде вообще 16 :)
У IB/FB - 255, хватает на все. Это же данные.
А в алгоритмах ничего прохого в рекурсии нет, иногда она позволяет очень симпатично сократить программу. А по мне чем короче программа - тем она лучше ;)
← →
Mystic © (2007-11-08 12:48) [39]> Зачастую оказывается, что оптимизировать потом существенно
> эффектевний, т.к. если оптимизируешь потом, то находишь
> действительно узкие места и оптимизируешь их, а не все подряд.
Достигается упражнениями и в общем случае, вообще говоря, это не так. Взять, например, шахматную программу. Допустим, что ты вначале решил не оптимизировать и в качестве представления доски взял array[0..63] of ShortInt. Отлично, движок реализован, осталось его оптимизировать. И тут ты выясняешь, что лучшее представление доски в виде битовых масок:TPosition = record
WPawns: UInt64;
WQuenns: UInt64;
...
BPawns: UInt64;
...
end;
Честно говоря, тут более простой путь оптимизации, выкинуть весь старый код и переписать все по новому :)
Скорость выполнения кода это такое же требования, как и другие. И решать его тоже надо наравне с другими требованиями. А если ты с самого начала не можешь сказать узкие места по производительности, то наверное лучше не браться за написание высокопроизводительного кода :)
← →
clickmaker © (2007-11-08 12:54) [40]
> А если ты с самого начала не можешь сказать узкие места
> по производительности, то наверное лучше не браться за написание
> высокопроизводительного кода
да не... потом можно всегда заказчика запарить: "у вас винт тормозит или сетка" )
Страницы: 1 2 вся ветка
Форум: "Прочее";
Текущий архив: 2007.12.09;
Скачать: [xml.tar.bz2];
Память: 0.54 MB
Время: 0.041 c
