mOleg писал(а):
И, может, стоит поговорить не столько об эффективности рекурсивных алгоритмов по сравнению с их нерекурсивными вариантами, сколько о самой рекурсии, так как тема при всей своей простоте имеет некие подводные камни.
ох-хо......
http://www.mccme.ru/free-books/Н.К. Верещагин, А.Шень. Лекции по математической логике и теории алгоритмов.
Часть 3. Вычислимые функции.
вот тут о самой рекурсии, о примитивно-рекурсивных функциях и т.п.
mOleg писал(а):
......[skip]........ в том числе из за наличия стека данных. Происходит это потому, что необходимые данные, если, конечно, они лежат на стеке данных, необходимо принудительно копировать! Чего в других языках нет.
ну дались же тебе эти стеки..... вот смотри, в фортране есть подпрограммы,
в фортране есть параметры и локальные переменные, а стека нет. совсем.
вся память в фортране аллоцируется статически. более того, были люди, которые
чрезвычайно резко высказывались ПРОТИВ использования стека (и, например,
системы прерываний). стек необходим только тогда, когда появляется необходимость
в одновременной активации нескольких копий подпрограммы. без слова recurse
стек в форте не нужен и _можно_ обойтись без него (стека).
mOleg писал(а):
И никто ничего не запрещает. Любое решение стоит взвешивать.
золотые слова!
mOleg писал(а):
garbler писал(а):
кто тебе запрещает делать мемоизацию? (на каждый вызов функции цепляется обработчик,
если параметры функции уже передавались, то данные берутся из кэша, иначе производится
вызов функции).
и это будет быстрее и эффективнее? Ведь надо проверять каждый параметр
вот видишь, ты сам ответил на свой вопрос. в случае, если обращение к ассоциативной
памяти быстрее, чем повторное вычисление подвыражения, такой вариант вычислений
окажется эффективнее. всё просто.
mOleg писал(а):
garbler писал(а):
вообще-то, с моей стороны это был сарказм
насчет сарказма не понял 8(
не обижайся, значит, это моя вина, раз не смог донести значение высказанного
mOleg писал(а):
пародоксально, так как конкретный алгоритм (при нормальной реализации) всегда будет быстрее общего. Сборшик мусора - это общее решение.
сборщик мусора - действительно общее решение.
попробую привести аналогию, смотри: mark, heapalloc-(x раз), release
может быть гораздо быстрее heapalloc-(x раз), heapfree-(х раз).
разница в данном случае в том, что решение могут принимать "в динамике"
и для целого ряда алгоритмов такой код может оказаться быстрее явных alloc/free.
Ты можешь возразить, что ты тоже можешь так поступать, делать alloc и потом переустановку
указателя here, но, ты это сделаешь статически по коду программы. вот в этом будет
и разница. повторюсь ещё раз: во многих случаях работа сборщика мусора может оказаться
быстрее явных alloc/free на каждый вызов.
приведу ещё аналогию: бессистемное использование модификатора
register в си (и/или ассемблерных вставок и/или указателей) вполне в состоянии
затормозить выполнение программы, т.к. собьют напрочь попытки глобальной
оптимизации кода.
в общем, человек должен думать, компилятор работать. если что-то можно абстрагировать
из программного кода, то это так и должно быть сделано.
в конце концов, посмотри на историю: статическое отведение памяти (фортран), затем
стек, затем хип..... кстати, вот ответь, какие преимущества мы получаем, если активационные
записи процедур (функций, слов, неважно) будут храниться в хипе, а не стеке?
ответ - нити, сопрограммы, "замыкания" в которых можно реализовать вычисления
"с откатами" и т.п. Кстати, есть масса промежуточных способов организации
этих структур....... в паскале, например, решили обойтись только стеком, ввели
"дисплеи" для вложенных процедур (что автоматически ограничивает область жизни
указателей на процедуры и процедурных параметров вершинами дерева вызова).
mOleg писал(а):
Память можно выделять из линейной области, по типу того, как с памятью работает фортовый механизм HERE ALLOT
- однозначно быстрее.
именно поэтому так редко встречаются многосегментные форт-реализации?
сегмент кода, сегмент данных, сегмент изменяемых данных, сегмент словаря,
сегмент констант, стеки: вызовов, параметров, переменных....... ? динамическое
изменение размеров сегмента....... собственно, насколько я заметил, в форт-реализациях
вообще туго с глобальной обработкой кода........ даже фиксапы никто не почешется
сделать в turnkey образах, обходятся ABS>REL/REL>ABS
mOleg писал(а):
Еще раз, стек в яве не является естественной структурой, которой все везде пользуются.
ну, все.... везде.... мы же не обсуждаем плохой код? мы ведь говорим о хорошем коде,
а зачем мне плохие программы плохих программистов? мне не нужны все, и мне не надо
везде, мне достаточно друзей и интересных задач. вот кому нравится писать "бухгалтерию"
на коболе 21-го века, вот те пускай её и пишут. берут готовые конструкторы (библиотеки),
созданные системщиками, и пишут.........
я бы ориентировался на Алгол-68, например.