Текущий архив: 2007.12.09;
Скачать: CL | DM;
Вниз
Отрицательные стороны рекурсии. Найти похожие ветки
← →
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]
> А если ты с самого начала не можешь сказать узкие места
> по производительности, то наверное лучше не браться за написание
> высокопроизводительного кода
да не... потом можно всегда заказчика запарить: "у вас винт тормозит или сетка" )
← →
Romkin © (2007-11-08 13:01) [41]Mystic © (08.11.07 12:48) [39] Это не оптимизация. Это плохое проектирование :)
← →
ferr (2007-11-08 13:05) [42]В функциональных языках рекурсия это всё.
Например по списку можно проходить используя рекурсию..
← →
Сусл © (2007-11-08 15:01) [43]
> 42] ferr (08.11.07 13:05)
> В функциональных языках рекурсия это всё.
> Например по списку можно проходить используя рекурсию..
зато они и тормозят неподецки :) надеюсь, что пока. насколько я знаю перспективы ускорения есть.
зато красота, конечно нереальная - одной-двумя строками написать быструю сортировку. я на дельфи пытался повторить - красиво выглядит надо сказать, только медленно :)
← →
Anatoly Podgoretsky © (2007-11-08 16:24) [44]> TUser (08.11.2007 12:11:34) [34]
Для Дельфимастеров очень актуально!
← →
Mystic © (2007-11-08 16:27) [45]> Это не оптимизация. Это плохое проектирование :)
Ну... Проектирования без учета требования скорости выполнения кода. Хотя даже в этом случае можно использовать, например, метод 0x88. Вообще это связные вещи, так что в данном случае я бы сказал, что при проектировании не учитывалось требование оптимальности (оставлено на потом). Что и привело к такому результату (код в мусорку)
> зато красота, конечно нереальная - одной-двумя строками
> написать быструю сортировку
Все-таки немного разные алгоритмы. Обычно из списке берется средний элемент, чтобы эффективно сортировались уже отсортированные списке. А в примерах на ФЯ часто выбирается первый элемент. С другой стороны, дайте мне хорошую библиотеку для работы со списками, я и на Delphi Напишу сортировку в две строки
function Sort(L: TIntList): TIntList;
begin
Element := L.GetMiddle();
Result := Concat([L.GetLess(Element), L.GetEqual(Element), L.GetMore(Element)]);
end;
← →
Mystic © (2007-11-08 16:30) [46]> TUser © (08.11.07 12:11) [34]
> Могу сказать, что рекурсивные алгоритмы на порядок сложнее
> в отладке.
Это не бесспорно. Зачастую рекурсивный алгоритм и отлаживать не надо, а на обычном надо городить стек, операции с ним и т. д.
← →
Mystic © (2007-11-08 16:33) [47]function Sort(L: TIntList): TIntList;
begin
if L.Size = 1 then Result := L else
begin
Element := L.GetMiddle();
Result := Concat([Sort(L.GetLess(Element)), L.GetEqual(Element), Sort(L.GetMore(Element))]);
end;
end;
← →
NX (2007-11-08 17:46) [48]
> Riply © (08.11.07 03:29)
Бесконечный цикл -> Переполнение памяти -> Смерть винды -> Рестарт
← →
KilkennyCat © (2007-11-08 18:09) [49]
> NX (08.11.07 17:46) [48]
бесконечный цикл не только рекурсия
переполнение памяти при бесконечном цикле не обязательно
смерть винды ваще маловероятно, если не говорить о 9х
а причем здесь рестарт?
← →
Сусл © (2007-11-08 18:44) [50]
> [47] Mystic © (08.11.07 16:33)
ну да, быстрая сортировка :)
← →
iZEN © (2007-11-08 22:40) [51]
> Romkin © (08.11.07 10:06) [33]
>
> Отказываются от рекурсии из-за желания оптимизировать.
> Я все время пользуюсь (пытаюсь) двумя правилами:
> 1. Не делайте оптимизацию.
> 2. Только для экспертов: не делайте оптимизацию раньше времени.
>
> (с) не помню кто.
> Но желание "ускорить", похоже, неистребимо :)
>
1. Программирование есть процесс автоматизации труда. Без компьютеров задача решалась бы вручную долго и непроизводительно. Так что сам процесс программирования является оптимизацией ручного труда.
2. Что касается не делать оптимизацию раньше времени, то да, нужно посмотреть, а стоит ли вообще программировать получение решения потенциально спорной задачи.
:))
← →
Mystic © (2007-11-09 11:11) [52]> ну да, быстрая сортировка :)
От нее осталось одно название :) На самом деле это тормознутая сортировка. Посчитай, какой количество временных объектов создастся? Плюс нужен хотя бы счетчик ссылок для того, чтобы умирали бесчисленные временные объекты ;)
← →
TUser © (2007-11-09 12:00) [53]Представим себе, что TIntList из [47] - потомок обычного TList, для которого определены всякие там GetMiddle и прочее. Я передаю в Sort экземпляр этого класса. GetLess, GetEqual и GetMore создают три новых экземпляра. Concat возвращает еще один экземпляр. А как иначе? И так на каждой итерации. А кто будет уничтожать созданный зверинец? Счетчика ссылок-то в Delphi не предусмотрено.
Страницы: 1 2 вся ветка
Текущий архив: 2007.12.09;
Скачать: CL | DM;
Память: 0.61 MB
Время: 0.041 c
