Версия для печати темы Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > Perl: Системное программирование > рекурсия

Автор: aksined 28.12.2005, 17:36

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

Автор: sergejzr 28.12.2005, 17:52

Цитата(aksined @ 28.12.2005, 16:36) А не может такого быть, что сохранять нужно не текстовую строку, а более накрученную структуру, что будет сопоставимо с рекурсией рекурсия - тот же стэк. Интерпретатор однако не знает, какие данные релевантны и поэтому сохраняет в своём стэке просто абсолютно все переменные в функции, кроме того ещё и точку выполнения, чтобы знать, откуда продолжить работу. Кроме того выполняется ещё много проверок и, возможно системных запросов. То есть при наличии сложной структуры, при рекурсии она копируется столько раз, сколько вызовов функции произошло и впамяти держаться все копии из ещё необработанных функций. Создание собственного стека - значительно упрощает ситуацию. Туда мы сохраняем только то, что действительно надо. Происходит заначительная разгрузка системы. В стек мы можем класть ссылки, а не сами обьекты, при этом обходя множество ненужных копирований, неизбежных при рекурсии. Ещё одно преимущество - управление порядком вызовов на низком уровне. То есть например заменив очередь на стек мы можем прошагать по дереву в длинну, иначе - в ширину.

Автор: sharq 28.12.2005, 17:59

Рекурсия и линейные алгоритмы? ВОт в чем вопрос! Все зависит от задачи, например, обход дерева с неизвестной степенью вложенности, однозначно следует делать через рекурсию.

Автор: sergejzr 28.12.2005, 18:06

Цитата(sharq @ 28.12.2005, 16:59) Все зависит от задачи, например, обход дерева с неизвестной степенью вложенности, однозначно следует делать через рекурсию. Не верно. Во всяком случаи подобные утверждения следует делать с доказательствами. А я пока не вижк, почему это должно быть так.

Автор: sharq 28.12.2005, 18:19

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'а, а всех ЯП, которые поддерживают рекурсию.

Автор: sergejzr 28.12.2005, 18:33

Цитата(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'а, а всех ЯП, которые поддерживают рекурсию. Угу, я вот перла не знаю, поэтому написал на псевдоязыке ))

Автор: aksined 28.12.2005, 18:35

sharq А не удобнее пользоваться File::Find разве не удобнее? Кстати, сейчас смотрю, как они там реализовали обход дерева. Не факт, что используют рекурсию.Их функция справляется с гораздо более злой вложенностью, чем ты привел. Пока правда не очень получается. Очень уж там все накручено. Слушай, а что делает Код foreach (grep {/[^\.]+/} sort readdir $dir) { ? С grep у меня самые большые нелады. Понимаю, что вызвал readdir в списковом контексте, отсортировал, а вот что делает grep - не пойму. Я бы делал через -d $qwe.

Автор: sharq 28.12.2005, 18:38

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

Автор: sergejzr 28.12.2005, 18:43

Цитата(sharq @ 28.12.2005, 17:38) sergej.z рекурсия реализована с помощью стека, сделай тоже самое без стека. Зачем? рекурсия подразумевает вызов самой функции. Мой пример - линейный алгоритм, а не рекурсивный. Это стандартное решение для перевода из рекурсивный в линейное. Смысла переделывать не вижу.

Автор: sharq 28.12.2005, 18:46

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

Автор: aksined 28.12.2005, 19:07

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;   ... Цитата рекурсия с любой! придется все-таки посмотреть модуль. Думаю, что они без рекурсии сделали

Автор: sergejzr 28.12.2005, 19:24

Цитата(aksined @ 28.12.2005, 18:07) Вместо стека можно использовать список или какую угодно структуру хранения данных. В статье, откуда растут ноги, используется массив (хотя и используется c методами push и рор). Хотя, есть подозрение, что массивы в перл - это не массивы, а списки. Ассоциативные hash - массивы. Они достаточно быстры. Его можно заставить работать и как стек, и как очередь. Цитата(sharq @ 28.12.2005, 17:46) sergej.z ради интереса, сравню оба подхода по времени выполнения. Ага, сравни, только на чём нибудь очень большом. А то если просто вызвать функцию много раз, только время на вызов и подсчитаешь...

Автор: aksined 28.12.2005, 20:09

Цитата(aksined @ 28.12.2005, 18:35) Слушай, а что делает код Perl 1: foreach (grep {/[^\.]+/} sort readdir $dir) { ? так и не ответил Как говорится в тему Цитата   *   Избегайте использования grep() (или map()) или `обратных_апострофов`         в void-контексте, то есть игнорировать возвращаемые ими значения.         Все эти функции возвращают значения, так используйте их. Иначе,         используйте цикл foreach() или функцию system() вместо них. by http://vingrad.ru/PERL-ART-001992

Автор: korob2001 28.12.2005, 21:05

Цитата 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 используется не совсем удачный шаблон, который будет проверять каждый символ, каждого элемента списка. Нужно потестировать.

Автор: sharq 29.12.2005, 00:14

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:46

Вот ради интереса сравнил рекурсию и линейный алгоритм. Код use Time::HiRes 'time'; sub simple($) {     my $scanpath = shift;     my $stack;     push @$stack, $scanpath;     while (@$stack) {         my $newpath = shift @$stack; #        print $newpath, "\n";         if (-f $newpath) {             1;         } else {             opendir my($dir), $newpath;             push @$stack, $newpath.'/'.$_ foreach grep {/[^\.]+/} readdir $dir;         };     };     1; }; sub recurcia($) {     my $scanpath = shift; #    print "$scanpath\n";     if (-f $scanpath) {         1;     } else {         opendir my($dir), $scanpath;         &recurcia($scanpath.'/'.$_) foreach grep {/[^\.]+/} readdir $dir;     };     1; }; my $start1 = time; simple('root'); my $end1 = time - $start1; my $start2 = time; recurcia('root'); my $end2 = time - $start2; print "Simple: $end1\nRecurcia: $end2\n"; Вот результат работы: Код Simple: 0.0267901420593262 Recurcia: 0.0253551006317139 При повторных запусках линейный алгоритм примерно одинаков, иногда на чуть-чуть обгонял, но это маленькое дерево. Цитата(sergej @ 28.12.2005, 20:24) Ага, сравни, только на чём нибудь очень большом. А то если просто вызвать функцию много раз, только время на вызов и подсчитаешь... При увеличение директорий рекурсия выигрывает. Вот просканировал свой диск e:\\ - всего лишь 250 метров. Код Simple: 0.890079021453857 Recurcia: 0.85121488571167 Вот диск c:\\ - 5 гигов. Код Simple: 20.6784000396729 Recurcia: 8.88276100158691 Результаты на лицо! И выглядит рекурсия при обходе дерева проще и наглядней!

Автор: korob2001 29.12.2005, 01:25

Цитата Здесь поясню, имелись в виду след. директории: "." или "..", их обрабатывать не надо, поэтому пропускаем. Хотя шаблон отбрасывает все названия, в которых есть точка. Так если нужно отбросить только катологи ./ и ../, то почему бы не изменить шаблон? Например на такой: Код /^[^\.\.?]$/ А то мы таким шаблоном будем отсеивать и все файлы с раширениями.

Автор: sharq 29.12.2005, 01:33

korob2001 писался на скорую руку, поэтому такой. Изменить конечно можно. Например на такой: Код /^\.+$/ Цитата(korob2001 @ 29.12.2005, 02:25) А то мы таким шаблоном будем отсеивать и все файлы с раширениями. Отсеиваться будут только директории, в названии которых есть точка, т.к. Код     if (-f $scanpath) { # если директория         ...     } else { # если не файл, т.е. директория         opendir my($dir), $scanpath;         foreach (grep {/[^\.]+/} readdir $dir) {           ....         }     };

Автор: aksined 29.12.2005, 09:47

А не слишкомм круто ли круто использовать это только для отсеивания . и ..? Код foreach (grep {/[^\.]+/} readdir $dir) { Дело не в регулярном выражении, а в том, что readdir возвращает нам массив. А если каталог содержит 7000 файлов, не быстрее его будет обработать поэлементно. Это я еще не в курсе - grep создаст еще один или изменит переданный ему. Если новый - получается выделена память на еще один массив. Может и не так элегантно, но но все понятно, да и работать должно быстро Код opendir IN_DIR, $in_dir; while(my $name = readdir IN_DIR) {   next if ($name eq "." || $name eq ".."); #не суть можно и так   next if ($name =~ m!^\.\.?$!);   func($name, $in_dir);   } closedir IN_DIR;

Автор: sergejzr 29.12.2005, 13:30

Цитата(sharq @ 28.12.2005, 23:46) Результаты на лицо! И выглядит рекурсия при обходе дерева проще и наглядней! Может быть перл так и склеен, что рекурсия быстрей, потому что где нибуть в длльке обрабатывается. Тут сложно сказать. Это вообще своеобразный язык. Может массив медленно работает в качестве стека (Ведь в нашем случае массив нам действительно не нужн). Но по логике вещей такого быть не должно. В коде написанный на С++ (где есть полный контроль за данными на почти самом низком уровне), рекурсия работает значительно медленнее.

Автор: korob2001 29.12.2005, 21:40

sergej.z - стек рботает очень быстро, об этом написано почти во всех книгах по Perl. Код my $start1 = time; simple('root'); my $end1 = time - $start1; ########################## my $start2 = time; recurcia('root'); my $end2 = time - $start2; Попробуй поменять местами вот эти два участка программы. И запусти тест снова, я получил противоположные значения.

Автор: sergejzr 29.12.2005, 21:56

Чтото я тоже слышал про перл и деструкцию

Автор: korob2001 29.12.2005, 23:23

Разделил их и добавил Benchmark, тест simple Код #!/usr/bin/perl -w use strict; use Time::HiRes 'time'; use Benchmark; sub simple($) {     my $scanpath = shift;     my $stack;     push @$stack, $scanpath;     while (@$stack) {         my $newpath = shift @$stack; #        print $newpath, "\n";         if (-f $newpath) {             1;         } else {             opendir my($dir), $newpath;             push @$stack, $newpath.'/'.$_ foreach grep {/[^\.]+/} readdir $dir;         };     };     1; }; my $bstart = new Benchmark; my $start1 = time; simple('D:'); my $end1 = time - $start1; my $bstop = new Benchmark; my $diff = timediff($bstop, $bstart); print "Simple: $end1\n"; print "Benchmark: " . timestr($diff) . "\n"; рекурсия Код #!/usr/bin/perl -w use strict; use Time::HiRes 'time'; use Benchmark; sub recurcia($) {     my $scanpath = shift; #    print "$scanpath\n";     if (-f $scanpath) {         1;     } else {         opendir my($dir), $scanpath;         &recurcia($scanpath.'/'.$_) foreach grep {/[^\.]+/} readdir $dir;     };     1; } my $bstart = new Benchmark; my $start2 = time; recurcia('D:'); my $end2 = time - $start2; my $bstop = new Benchmark; my $diff = timediff($bstop, $bstart); print "Recurcia: $end2\n"; print "Benchmark: " . timestr($diff) . "\n";

Автор: sergejzr 29.12.2005, 23:46

А где результы?

Автор: korob2001 30.12.2005, 01:13

Винт 120 GB, занято на нём 106 GB: Цитата Recurcia: 8.29783892631531 Benchmark:  8 wallclock secs ( 1.44 usr +  6.55 sys =  7.99 CPU) Simple: 8.26796793937683 Benchmark:  8 wallclock secs ( 1.45 usr +  6.44 sys =  7.89 CPU) ============================================= Recurcia: 9.01686096191406 Benchmark:  9 wallclock secs ( 1.70 usr +  6.77 sys =  8.47 CPU) Simple: 8.67406606674194 Benchmark:  9 wallclock secs ( 1.81 usr +  6.48 sys =  8.30 CPU)

Powered by Invision Power Board (http://www.invisionboard.com)
© Invision Power Services (http://www.invisionpower.com)