VPF::рекурсия - Форум программистов

sharq

Дата 29.12.2005, 00:46 (ссылка)

(нет голосов)

Загрузка ...

Perl Liker

Профиль
Группа: Участник
Сообщений: 841
Регистрация: 13.12.2004
Где: Ростов-на-Дону

Репутация: 3
Всего: 28

Вот ради интереса сравнил рекурсию и линейный алгоритм.

Код


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

Результаты на лицо!

И выглядит рекурсия при обходе дерева проще и наглядней!

smile

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

--------------------

[color=gray]There's More Than One Way To Do It[/color]

korob2001

Дата 29.12.2005, 01:25 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Комодератор
Сообщений: 2871
Регистрация: 29.12.2002

Репутация: 6
Всего: 61

Цитата

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

Так если нужно отбросить только катологи ./ и ../, то почему бы не изменить шаблон?
Например на такой:

Код


/^[^\.\.?]$/

А то мы таким шаблоном будем отсеивать и все файлы с раширениями. smile

--------------------

"Время проходит", - привыкли говорить вы по неверному пониманию.
"Время стоит - проходите вы".

sharq

Дата 29.12.2005, 01:33 (ссылка)

(нет голосов)

Загрузка ...

Perl Liker

Профиль
Группа: Участник
Сообщений: 841
Регистрация: 13.12.2004
Где: Ростов-на-Дону

Репутация: 3
Всего: 28

korob2001 писался на скорую руку, поэтому такой. smile

Изменить конечно можно.
Например на такой:

Код


/^\.+$/

Цитата(korob2001 @ 29.12.2005, 02:25)

А то мы таким шаблоном будем отсеивать и все файлы с раширениями.

Отсеиваться будут только директории, в названии которых есть точка, т.к.

Код


    if (-f $scanpath) { # если директория
        ...
    } else { # если не файл, т.е. директория
        opendir my($dir), $scanpath;
        foreach (grep {/[^\.]+/} readdir $dir) {
          ....
        }
    };

--------------------

[color=gray]There's More Than One Way To Do It[/color]

aksined

Дата 29.12.2005, 09:47 (ссылка)

(нет голосов)

Загрузка ...

Шустрый

Профиль
Группа: Участник
Сообщений: 58
Регистрация: 26.12.2005

Репутация: 1
Всего: 1

А не слишкомм круто ли круто использовать это только для отсеивания . и ..?

Код


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;

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

sergejzr

Дата 29.12.2005, 13:30 (ссылка)

(нет голосов)

Загрузка ...

Un salsero
Group Icon

Профиль
Группа: Админ
Сообщений: 13285
Регистрация: 10.2.2004
Где: Германия г .Ганновер

Репутация: 1
Всего: 360

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

Результаты на лицо!

И выглядит рекурсия при обходе дерева проще и наглядней!

Может быть перл так и склеен, что рекурсия быстрей, потому что где нибуть в длльке обрабатывается. Тут сложно сказать. Это вообще своеобразный язык. Может массив медленно работает в качестве стека (Ведь в нашем случае массив нам действительно не нужн). Но по логике вещей такого быть не должно. В коде написанный на С++ (где есть полный контроль за данными на почти самом низком уровне), рекурсия работает значительно медленнее.

--------------------

Me.
FB.
LinkedIn.
ORCID.
YT.

korob2001

Дата 29.12.2005, 21:40 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Комодератор
Сообщений: 2871
Регистрация: 29.12.2002

Репутация: 6
Всего: 61

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 (ссылка)

(нет голосов)

Загрузка ...

Un salsero
Group Icon

Профиль
Группа: Админ
Сообщений: 13285
Регистрация: 10.2.2004
Где: Германия г .Ганновер

Репутация: 1
Всего: 360

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

--------------------

Me.
FB.
LinkedIn.
ORCID.
YT.

korob2001

Дата 29.12.2005, 23:23 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Комодератор
Сообщений: 2871
Регистрация: 29.12.2002

Репутация: 6
Всего: 61

Разделил их и добавил 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 (ссылка)

(нет голосов)

Загрузка ...

Un salsero
Group Icon

Профиль
Группа: Админ
Сообщений: 13285
Регистрация: 10.2.2004
Где: Германия г .Ганновер

Репутация: 1
Всего: 360

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

--------------------

Me.
FB.
LinkedIn.
ORCID.
YT.

korob2001

Дата 30.12.2005, 01:13 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Комодератор
Сообщений: 2871
Регистрация: 29.12.2002

Репутация: 6
Всего: 61

Винт 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)

Это сообщение отредактировал(а) korob2001 - 30.12.2005, 01:28

--------------------

"Время проходит", - привыкли говорить вы по неверному пониманию.
"Время стоит - проходите вы".

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| Perl: Системное программирование \| Следующая тема »