Рекурсивные алгоритмы и замена их линейными

И все-таки. Хотя пишу и уже понимаю, что накладные расходы на ведение массива и сохранение в стеке данных несколько раззличаются. А не может такого быть, что сохранять нужно не текстовую строку, а более накрученную структуру, что будет сопоставимо с рекурсией

Цитата(aksined @ 28.12.2005, 16:36)

А не может такого быть, что сохранять нужно не текстовую строку, а более накрученную структуру, что будет сопоставимо с рекурсией

рекурсия - тот же стэк. Интерпретатор однако не знает, какие данные релевантны и поэтому сохраняет в своём стэке просто абсолютно все переменные в функции, кроме того ещё и точку выполнения, чтобы знать, откуда продолжить работу. Кроме того выполняется ещё много проверок и, возможно системных запросов.
То есть при наличии сложной структуры, при рекурсии она копируется столько раз, сколько вызовов функции произошло и впамяти держаться все копии из ещё необработанных функций.

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

Ещё одно преимущество - управление порядком вызовов на низком уровне. То есть например заменив очередь на стек мы можем прошагать по дереву в длинну, иначе - в ширину.

Рекурсия и линейные алгоритмы? ВОт в чем вопрос!

Все зависит от задачи, например, обход дерева с неизвестной степенью вложенности, однозначно следует делать через рекурсию.

Цитата(sharq @ 28.12.2005, 16:59)

Все зависит от задачи, например, обход дерева с неизвестной степенью вложенности, однозначно следует делать через рекурсию.

Не верно. Во всяком случаи подобные утверждения следует делать с доказательствами. А я пока не вижк, почему это должно быть так.

sergej.z как ты с помощью циклов сделаешь обход большого дерева, у которого ветки совершенно разные и разная степень вложенности?
Проще всего и лучше всего это сделать через рекурсию.

ВОт пример:

Код

-root/ --1/ ---1.1/ -----index.html ---1.2/ ----1.2.1/ ----1.2.2/ ----index.html --2/ ---2.1/ ----2.1.1/ -----index.html ---2.2/ ---index.html --3/

А вот и обход:

Код

sub scan($) {     my $scanpath = shift;     print "$scanpath\n";     if (-f $scanpath) {         1;     } else {         opendir my($dir), $scanpath;         foreach (grep {/[^\.]+/} sort readdir $dir) {             &scan($scanpath.'/'.$_);         };         close $dir;     };     1; }; scan('root');

Также есть задачи, для решения которых рекурсия не приминима.

Вопрос: рекурсия или линейность - это вопрос не одного perl'а, а всех ЯП, которые поддерживают рекурсию.




Это сообщение отредактировал(а) sharq - 28.12.2005, 18:22

Цитата(sharq @ 28.12.2005, 17:19)

sergej.z как ты с помощью циклов сделаешь обход большого дерева, у которого ветки совершенно разные и разная степень вложенности?

Код

stack.push(root);  while (!stack.empty)   {      Node = stack.pop;     //Здесь обработка узла     //..      foreach(Node.children as child)       {          stack.push(child);       } }

Цитата(sharq @ 28.12.2005, 17:19)

рекурсия или линейность - это вопрос не одного perl'а, а всех ЯП, которые поддерживают рекурсию.

Угу, я вот перла не знаю, поэтому написал на псевдоязыке ))

sharq
А не удобнее пользоваться File::Find разве не удобнее?
Кстати, сейчас смотрю, как они там реализовали обход дерева. Не факт, что используют рекурсию.Их функция справляется с гораздо более злой вложенностью, чем ты привел.
Пока правда не очень получается. Очень уж там все накручено.
Слушай, а что делает

Код

foreach (grep {/[^\.]+/} sort readdir $dir) {

?
С grep у меня самые большые нелады.
Понимаю, что вызвал readdir в списковом контексте, отсортировал, а вот что делает grep - не пойму. Я бы делал через -d $qwe.

Это сообщение отредактировал(а) aksined - 28.12.2005, 18:38

sergej.z рекурсия реализована с помощью стека, сделай тоже самое без стека.

Цитата(sharq @ 28.12.2005, 17:38)

sergej.z рекурсия реализована с помощью стека, сделай тоже самое без стека.

Зачем? рекурсия подразумевает вызов самой функции. Мой пример - линейный алгоритм, а не рекурсивный. Это стандартное решение для перевода из рекурсивный в линейное.
Смысла переделывать не вижу.

aksined

Цитата(aksined @ 28.12.2005, 19:35)

Очень уж там все накручено.

именно поэтому я написал сам.

Цитата(aksined @ 28.12.2005, 19:35)

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

рекурсия с любой!




Добавлено @ 18:51
sergej.z ради интереса, сравню оба подхода по времени выполнения.

sharq
рекурсия и стек - не одно и то же.
Вместо стека можно использовать список или какую угодно структуру хранения данных. В статье, откуда растут ноги, используется массив (хотя и используется c методами push и рор). Хотя, есть подозрение, что массивы в перл - это не массивы, а списки.

Цитата(sharq @ 28.12.2005, 18:46)

aksined Цитата (aksined @ 28.12.2005, 19:35) Очень уж там все накручено. именно поэтому я написал сам. Цитата (aksined @ 28.12.2005, 19:35) Их функция справляется с гораздо более злой вложенностью, чем ты привел. рекурсия с любой!

Накручено в реализации, а в использовании все просто:

Код

use File::Find; ... find(\&func, $in_dir); ... #============================================================ sub func{   my $fullname = $File::Find::name;   return if -d $fullname;   ...

Цитата

рекурсия с любой!

придется все-таки посмотреть модуль. Думаю, что они без рекурсии сделали

Цитата(aksined @ 28.12.2005, 18:07)

Вместо стека можно использовать список или какую угодно структуру хранения данных. В статье, откуда растут ноги, используется массив (хотя и используется c методами push и рор). Хотя, есть подозрение, что массивы в перл - это не массивы, а списки.

Ассоциативные hash - массивы. Они достаточно быстры. Его можно заставить работать и как стек, и как очередь.

Цитата(sharq @ 28.12.2005, 17:46)

sergej.z ради интереса, сравню оба подхода по времени выполнения.

Ага, сравни, только на чём нибудь очень большом. А то если просто вызвать функцию много раз, только время на вызов и подсчитаешь...

Цитата(aksined @ 28.12.2005, 18:35)

Слушай, а что делает код Perl 1: foreach (grep {/[^\.]+/} sort readdir $dir) { ?

так и не ответил

Как говорится в тему

Цитата

*   Избегайте использования grep() (или map()) или `обратных_апострофов`         в void-контексте, то есть игнорировать возвращаемые ими значения.         Все эти функции возвращают значения, так используйте их. Иначе,         используйте цикл foreach() или функцию system() вместо них.

by Стиль написания кода на Perl


Это сообщение отредактировал(а) aksined - 28.12.2005, 20:10

Цитата

foreach (grep {/[^\.]+/} sort readdir $dir) { };

Создаёт цикл, по отсортированному списку, который состоит из всех файлов и каталогов, которые расположены в каталоге $dir и которые не содержат точки в своём имени.

Цитата

Как говорится в тему

В перл ещё есть такое понятие, как побочный эффект. Это когда ты вызываешь какую либо функцию не для того, что бы получить то, что она возвращает, а для того, что бы получить то, что она делает. Потому вовсе не обязательно, создавать foreach когда у тебя в теле всего одно или 2 действия и тебе их нужно выполнить на каждой итерации по списку, в данном случае map работает быстрее.
Хотя данное утверждение не относится к коду выше, потому как это не void конетекст. foreach не явно создаёт список элементов в памяти, а grep его возвращает. Потому, получается примерно следующее.

1. readdir $dir - возвращает список файлов и каталогов из каталога $dir.

2. Затем список передаётся в sort, что не есть гуд. Получается мы сортируем список до того, как часть его будет отброшена grep, на следующем шаге. Но над этим ещё нужно подумать.

3. sort передаёт отсортированный список в grep, который отбрасывает файлы или каталоги, содержащие в своих именах точки.

4. foreach получает список и создаёт его не явно в памяти и выполняет проход по этому списку.

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

Это сообщение отредактировал(а) korob2001 - 28.12.2005, 21:18

aksined

Цитата(aksined @ 28.12.2005, 20:07)

рекурсия и стек - не одно и то же.

Рекурсия использует стек. А то, что это одно и тоже я не говорил!

Цитата(aksined @ 28.12.2005, 20:07)

Вместо стека можно использовать список или какую угодно структуру хранения данных

Стек - это всего лишь название способа доступа к данным (LIFO), а как ты будешь его реализовывать, это твое дело.

Цитата(aksined @ 28.12.2005, 20:07)

Хотя, есть подозрение, что массивы в перл - это не массивы, а списки.

Читаем документацию по perl, раздел массивы.

Цитата(aksined @ 28.12.2005, 20:07)

Накручено в реализации, а в использовании все просто:

Использовать все просто, вызвал функцию и все,
то, что работает, не значит, что работает так, как надо для данной задачи.

Цитата(aksined @ 28.12.2005, 21:09)

Как говорится в тему

К сожалению, не в ту тему. Здесь греп возвращает новый список, по которому и идет цикл foreach.
Здесь нет явного присвоения, для того чтобы избежать создание избыточных переменных. Можно было написать так, но это работает дольше и код увеличивается на одну строку:

Код

my @new =grep {/[^\.]+/} sort readdir $dir; foreach (@new) {  ... }

И никакого побочного эффекта здесь нет! О чем и сказал korob2001.

Цитата(korob2001 @ 28.12.2005, 22:05)

foreach (grep {/[^\.]+/} sort readdir $dir) { }; Создаёт цикл, по отсортированному списку, который состоит из всех файлов и каталогов, которые расположены в каталоге $dir и которые не содержат точки в своём имени.

Здесь поясню, имелись в виду след. директории: "." или "..", их обрабатывать не надо, поэтому пропускаем. Хотя шаблон отбрасывает все названия, в которых есть точка.



Это сообщение отредактировал(а) sharq - 29.12.2005, 00:17