об эффективности рекурсивных алгоритмов в форте

garbler

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, например.

true-grue

garbler писал(а):

ну дались же тебе эти стеки..... вот смотри, в фортране есть подпрограммы,
в фортране есть параметры и локальные переменные, а стека нет. совсем.
вся память в фортране аллоцируется статически. более того, были люди, которые
чрезвычайно резко высказывались ПРОТИВ использования стека (и, например,
системы прерываний). стек необходим только тогда, когда появляется необходимость
в одновременной активации нескольких копий подпрограммы. без слова recurse
стек в форте не нужен и _можно_ обойтись без него (стека).

А мне захотелось этот момент проиллюстировать кодом.
Вот, милости прошу экспериментировать(spf):

Цитата:

: f-: ( "name" -- here ) : HERE 0 , ;
: f-; ( here )
[COMPILE] ; HERE SWAP ! -1 ALLOT
0xE9 C, ( jmp #) 0 , ; IMMEDIATE
: f-call ( "name" )
' DUP @ 0xBB C, ( mov ebx, #) ,
0xC7 C, 0x03 C, ( mov [ebx], #) HERE 9 + OVER @ 4 + - ,
0xE9 C, HERE - , ; IMMEDIATE

f-: foo ... f-;
: test-foo ... f-call foo ... ;

mOleg

garbler писал(а):

mOleg писал(а):И, может, стоит поговорить не столько об эффективности рекурсивных алгоритмов по сравнению с их нерекурсивными вариантами, сколько о самой рекурсии, так как тема при всей своей простоте имеет некие подводные камни.
ох-хо...... http://www.mccme.ru/free-books/
Н.К. Верещагин, А.Шень. Лекции по математической логике и теории алгоритмов.
Часть 3. Вычислимые функции.
вот тут о самой рекурсии, о примитивно-рекурсивных функциях и т.п.

интересно, но ссылочка не работает 8(

garbler писал(а):

ну дались же тебе эти стеки...

они не дались - они есть

это объективная реальность.

garbler писал(а):

вот смотри, в фортране есть подпрограммы,
в фортране есть параметры и локальные переменные, а стека нет. совсем.

интересно. Не знал. Но тогда не представляю, что из себя представляют подпрограммы и как передается управление?

garbler писал(а):

без слова recurse стек в форте не нужен и _можно_ обойтись без него (стека).

Гм, очень интересно. Тут можно поподробнее?

garbler писал(а):

в случае, если обращение к ассоциативной памяти быстрее, чем повторное вычисление подвыражения, такой вариант вычислений окажется эффективнее.

только, если данный метод используется не повсеместно, а в нужных местах. Потому как чаще вычислить значение будет быстрее поиска в ассоциатиивной памяти.

garbler писал(а):

попробую привести аналогию, смотри: mark, heapalloc-(x раз), release может быть гораздо быстрее heapalloc-(x раз), heapfree-(х раз). разница в данном случае в том, что решение могут принимать "в динамике" и для целого ряда алгоритмов такой код может оказаться быстрее явных alloc/free.

тут не соглашусь. Наиболее затратным является выделение памяти, а не освобождение ее.
То есть, если heapalloc(x-раз) в обоих случаях, то время работы будет примерно одинаковым. HeapFree() более быстро выполняется.
Хотя тут много зависит от метода организации динамической памяти (при использовании страничной адресации выделение памяти будет быстрее).

garbler писал(а):

mOleg писал(а):Память можно выделять из линейной области, по типу того, как с памятью работает фортовый механизм HERE ALLOT - однозначно быстрее.

именно поэтому так редко встречаются многосегментные форт-реализации?

нет, причина, мне кажется другая. Современные ОС используют плоскую модель памяти (что виндовс, что линукс) и, соответственно все писаные на них форты используют тоже плоскую модель. То, что осталось в Win32Forth от работы с сегментами является наследием досевого предка. Кстати, почти все досевые форты были многосегментными. На многосегментную память очень хорошо ложится косвенный шитый код

garbler писал(а):

собственно, насколько я заметил, в форт-реализациях вообще туго с глобальной обработкой кода........ даже фиксапы никто не почешется сделать в turnkey образах, обходятся ABS>REL/REL>ABS

в форт реализациях по-возможности используют наиболее простые методики.

garbler писал(а):

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

а тут плохой или хороший код не причем. В форте стек данных (и частично возвратов) является естественной средой для передачи данных между словами. И, хотя, в Ява-ВМ тоже стек используется для передачи данных, на "описательном" уровне это не так выражается, как в форте.

mOleg

profiT писал(а):

mOleg писал(а):Нормальные люди - они разные.

Иногда очень важно не просто быстро написать, а чтоб всегда работало, чтоб меньше памяти кушало, и вообще много чего бывает важнее, чем просто быстро написать.
Чтобы написать первый вариант ("полностью" "рекурсивный") и считать себя нормальным, нужно быть прописанным в палате номер 9.
А "чтобы всегда работало" и "быстро написать" -- это как раз одно и то же, так как быстрое написание имеет в виду больше времени на отладку/отеложивание/доработку.

Гм. Есть языки, в которых доступны только рекурсивные алгоритмы. Тот же пролог, например. Хотя опять же речь о форте.
Просто я хотел сравнить возможные варианты. Сначала полностью рекурсивный и полностью нерекурсивный. Но первым получился гибрид.

Что же до отладки, то не согласен. Например, можно быстро написать простое, но медленное решение практически без отладки, либо писать быстрое, но сложное, и потом долго его отлаживать. Опять же, если ты пишешь что-то для микроконтроллера, то может статься так, что есть ограниченное пространство для реализации алгоритма, за которое ну никак нельзя выйти, и решение должно быть ко всему прочему шустрым.

profiT писал(а):

mOleg писал(а):понимаю но другой вариант не получился, чтоб было полностью рекурсивным определение (можешь попробовать сам ради интереса).

Опять это буквосочетание: "полностью рекурсивное". Неужели "чиста в натуре рекурсивность" отвергает другое буквосочетание: "цикличность"?..

нет, не отвергает. Но тема называется "об эффективности рекурсивных алгоритмов в форте" и я привел сравнение рекурсивного решения, которое тебе не понравилось и нерекурсивного, которое(??).

garbler

mOleg писал(а):

...skip...

garbler писал(а):

http://www.mccme.ru/free-books/

интересно, но ссылочка не работает 8(

всё там работает, я просто линк на страницу привёл (а не на конкретный том книги),
вообще, книжек там _очень_ много, может выберешь себе ещё что по душе.....

mOleg писал(а):

garbler писал(а):

ну дались же тебе эти стеки...

они не дались - они есть

это объективная реальность.

garbler писал(а):

вот смотри, в фортране есть подпрограммы,
в фортране есть параметры и локальные переменные, а стека нет. совсем.

интересно. Не знал. Но тогда не представляю, что из себя представляют подпрограммы и как передается управление?

true-grue на один пост выше всё прекрасно проиллюстрировал. приведу пример
на псевдокоде:

Код:

.code
sub1:
    .........
    ret_from_sub2 = ret_to_sub1a
    jmp sub2
ret_to_sub1a:
    .........
    ret_from_sub2 = ret_to_sub1b
    jmp sub2
ret_to_sub1b:
    .........
    .........
    jmp [ret_from_sub1]

sub2:
    .........
    jmp [ret_from_sub2]

.data
ret_from_sub1:
    .addr(?)
ret_from_sub2:
    .addr(?)

со всем остальным аналогично. между прочим! в своё время считали косвенную адресацию
весьма накладной! ( думаю, своих холиваров хватало о том, каким должен быть набор команд
ассемблера :-)

) так вот, ret_from_sub1 вполне может находиться прямо поверх команды
jmp [ret_from_sub1] после чего адресация станет непосредственной.

теперь - уточнение - зачем это было нужно? например, чтобы гарантированно определить
затраты программы на память, ещё до загрузки программы!!! чтобы гарантированно
_доказать_ поведение программы! (раньше это считалось более важным, чем получить
stack fault в непредсказуемый момент времени).

mOleg писал(а):

garbler писал(а):

без слова recurse стек в форте не нужен и _можно_ обойтись без него (стека).

Гм, очень интересно. Тут можно поподробнее?

на абзац выше всё сказано + пример от true-grue. кстати, туда-же, закрывая тему:
в ассемблере PDP нет команды перехода на подпрограмму с использованием стека,
там есть JSR REG, TARGET (когда счётчик команд заносят в регистр и переходят на адрес)
после чего возврат из подпрограммы выглядит как переход по содержимому регистра.
заодно по адресу, на который указывает регистр, хранят и передаваемые параметры.
другое дело, что богатое множество режимов адресации позволяет эмулировать
команду CALL - это да (стек предполагалось использовать для прерываний в основном).

mOleg писал(а):

...skip...
тут не соглашусь. Наиболее затратным является выделение памяти, а не освобождение ее.

зависит от алгоритмов организации динамической памяти и профиля её использования.
в mark-sweep-copy затратным является как раз освобождение :-)

mOleg писал(а):

...skip...
И, хотя, в Ява-ВМ тоже стек используется для передачи данных, на "описательном" уровне это не так выражается, как в форте.

ну, давай тогда следующее поколение этих языков возьмём - .NET семейство.
там кодогенератор из модуля Reflection уже даже у Петцольда описывается
(т.е. - читай - для домохозяек, решивших стать программистами).

p.s.

mOleg писал(а):

Гм. Есть языки, в которых доступны только рекурсивные алгоритмы. Тот же пролог, например

не факт..... т.е. ты можешь конечно использовать процедурную интерпретацию
программы, но это не поощряется. программа на прологе определяет совокупность
отношений предметной области, но ничего не говорится о методе достижения
результата. кроме классического последовательного алгоритма резолюции
есть масса других моделей вычисления пролог-программы, в том числе и
параллельные!!! например: andorra kernel language, and-prolog и т.п.

(в языки программирования "в ограничениях" мы сейчас погружаться не будем, там
ещё более хитро дела обстоят).

и ещё, в прологе можно определить "процедурные компоненты", после чего программировать
так, как будто у тебя есть циклы и т.п. вещи. самый тривиальный пример: repeat:-!,repeat.
после чего у тебя появляется "оператор бесконечного цикла". впрочем, самое интересное
закопано в метапредикатах: op, eval, apply, findall и т.п. вот в этом реализации и разнятся
между собой, от скучного turbo-prolog до "навёрнутых" swi-prolog или ciao-prolog.
так что, отступая от темы, пролог прологу рознь.

mOleg

garbler писал(а):

mOleg писал(а):

Гм. Есть языки, в которых доступны только рекурсивные алгоритмы. Тот же пролог, например

не факт..... т.е. ты можешь конечно использовать процедурную интерпретацию программы, но это не поощряется. программа на прологе определяет совокупность отношений предметной области, но ничего не говорится о методе достижения результата. кроме классического последовательного алгоритма резолюции есть масса других моделей вычисления пролог-программы, в том числе и параллельные!!! например: andorra kernel language, and-prolog и т.п. и ещё, в прологе можно определить "процедурные компоненты", после чего программировать так, как будто у тебя есть циклы и т.п. вещи. самый тривиальный пример: repeat:-!,repeat. после чего у тебя появляется "оператор бесконечного цикла". впрочем, самое интересное закопано в метапредикатах: op, eval, apply, findall и т.п. вот в этом реализации и разнятся между собой, от скучного turbo-prolog до "навёрнутых" swi-prolog или ciao-prolog.
так что, отступая от темы, пролог прологу рознь.

Имел дело только с TurboProlog и осталось от него очень отрицательное впечатление. К тому же на лекциях нам "толкали тему" что "можно обходиться рекурсией и это круто. И вообще кроме рекурсии ничего нет и быть не может"

может с тех пор у меня к рекурсии есть некое нехорошее отношение, как и к прологу.

WhitEAngell

Объясняю. Есть разработанный алгоритм функционирования системы. Начало, начальные значения, ветвления, циклы и т.д. Этих алгоритмов много. Надо создать документацию на систему статьюотчёт, где нарисовать этот алгоритм алгоритмы. Поскольку алгоритмы получаются достаточно развесистые, хочется автоматизировать процесс рисования этих документов, на таскание блоков мышкой много времени уходит. Наиболее оптимальный вариант пакетной обработки: даю текстовый файл описания, по нему генерируется изображение алгоритма, которое потом вставляется в отчёт.

вопрос

mOleg писал(а):

Имел дело только с TurboProlog и осталось от него очень отрицательное впечатление. К тому же на лекциях нам "толкали тему" что "можно обходиться рекурсией и это круто. И вообще кроме рекурсии ничего нет и быть не может"

может с тех пор у меня к рекурсии есть некое нехорошее отношение, как и к прологу.

преподаватель сам видел всё это, возможно, только на бумаге...

garbler

WhitEAngell писал(а):

...skip... Надо создать документацию на систему статьюотчёт, где нарисовать этот алгоритм ...skip... Наиболее оптимальный вариант пакетной обработки: даю текстовый файл описания, по нему генерируется изображение алгоритма, которое потом вставляется в отчёт.

как-то бессвязно к предыдущему обсуждению задан вопрос. Если ты не спамбот, то попробуй aiSEE - у него очень гибкий входной язык описаний структур. ещё как вариант можно graphviz попробовать, он бесплатный, но не без подводных камней (не всегда удаётся управлять алгоритмом размещения блоков).

об эффективности рекурсивных алгоритмов в форте

Кто сейчас на конференции