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

Форум программистов > Perl: Общие вопросы > Обсудим как ускорить алгоритм?

Автор: MakTpaxep 17.6.2011, 10:14

Есть таблица соответствий в файле - строка-строка. Получается хэш около 1000 элементов. Нужно заменить в исходном файле все эти строки на соответствующие (для простоты предположим что в файле просто слова). Мой код работает неприлично долго.  В каждой строке исходного файла пробегает по всем ключам и если находит заменяет их. Код foreach (@data) {    foreach my $key (keys %hash)    {       my $h=$hash{$key};       s!\b$key\b!$h!g;    } } Господа, какие есть идеи по ускорению проги? Добавлю: Файл большой, строки тоже бывают по несколько тысяч.

Автор: Suppir 17.6.2011, 10:25

Если файл не слишком большой, то, возможно, мультистрочный поиск (по всему файлу целиком) будет быстрее. Т.е. не нужно для каждой строки перебирать библиотеку замен.

Автор: Logo 17.6.2011, 10:59

Однако, судя по коду, файл полностью посещается в память?

Автор: arto 17.6.2011, 11:03

# perl -MBenchmark=timethese -e '%h = map { $_ => "aa$_" } 1024; @data = 0..10_000; $re = join "|", keys %h; timethese ($ARGV[0], { mak => sub { foreach (@data) { foreach my $k (keys %h) { my $h = $h{$k}; s#\b$k\b#$h#g } } }, arto => sub { foreach (@data) { s#\b($re)\b#$h{$1}#go } } })' 1000 Benchmark: timing 1000 iterations of arto, mak...       arto:  2 wallclock secs ( 1.82 usr +  0.01 sys =  1.83 CPU) @ 546.45/s (n=1000)        mak: 14 wallclock secs (12.78 usr +  0.00 sys = 12.78 CPU) @ 78.25/s (n=1000)

Автор: MakTpaxep 17.6.2011, 11:17

Цитата(arto @  17.6.2011,  11:03 ) # perl -MBenchmark=timethese -e '%h = map { $_ => "aa$_" } 1024; @data = 0..10_000; $re = join "|", keys %h; timethese ($ARGV[0], { mak => sub { foreach (@data) { foreach my $k (keys %h) { my $h = $h{$k}; s#\b$k\b#$h#g } } }, arto => sub { foreach (@data) { s#\b($re)\b#$h{$1}#go } } })' 1000Benchmark: timing 1000 iterations of arto, mak...      arto:  2 wallclock secs ( 1.82 usr +  0.01 sys =  1.83 CPU) @ 546.45/s (n=1000)       mak: 14 wallclock secs (12.78 usr +  0.00 sys = 12.78 CPU) @ 78.25/s (n=1000) А мысль не дурна, спасибо  Только вот если найдёт слово, которого нету в хэше, то боюсь думать что он подставит. Можно как-нибудь прямо в рег вставить проверку, если вам не трудно?  Я реги ещё не настолько изучил, чтобы код внутри писать (наверное самое время). Цитата(Logo @  17.6.2011,  10:59 ) Однако, судя по коду, файл полностью посещается в память? Конечно, а как иначе? Цитата Если файл не слишком большой, то, возможно, мультистрочный поиск (по всему файлу целиком) будет быстрее. Т.е. не нужно для каждой строки перебирать библиотеку замен.  Идею понял, можно просто поменять циклы местами. Но таки самая большая потеря скорости точно не здесь.

Автор: arto 17.6.2011, 11:26

а как его найдут?

Автор: MakTpaxep 17.6.2011, 11:38

А ну да - не найдут. Это я стормозил. А вот если вместо ($re) было бы (\w+), то было бы ещё быстрее, только тогда надо не производить замен если такого ключа нету.

Автор: arto 17.6.2011, 11:43

ну если вы уверены, что у вас там класс \w+, то s#\w+#$h{$&}||''#ge

Автор: MakTpaxep 17.6.2011, 11:45

Спасибо огромное, я посмотрю что значат эти две палочки=) Ещё вопрос по этому регу s#\b($re)\b#$h{$1}#go  Тут ведь переменные есть, какое тогда значение имеет модификатор "o"? Я токо в рунете находил, а решил на perldoc глянуть, так нету его О_о  http://perldoc.perl.org/perlre.html

Автор: arto 17.6.2011, 12:03

perldoc perlop на предмет Regexp Quote-Like Operators

Автор: MakTpaxep 17.6.2011, 12:30

Да всё проще чем я думал=)

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