[Moscow.pm] Ускорение регэкспа

[Denis Evdokimov]

А вот тако


12 июля 2013 г., 17:12 пользователь Konstantin S. Uvarin
<khedin на gmail.com>написал:

> Приветствую!
>
> > >   { 15_символов_подряд => [ вхождение, вхождение2, ... ] }
> > >
> > Думаю, что стоит ограничиться
> > ++$substr{15_символов_подряд};
> > Вот если найдётся подстрока 5+, тогда и заморачиваться.
> > Должно быть сильно дешевле по памяти и быстрее.
> >
> > Не зная данных, сложно предлагать что-то оптимальное, но скорее
> всего можно
> > делать
> > ++$substr{N_символов_подряд};
> > Где N достаточно большое, для отбрасывания большинства лишних
> совпадений,
> > но сильно меньше 15;
>
> С меньше_15_символов нет особого смысла заморачиваться, похоже -
> длина ключей заметна, но погоды не делает:
> -bash$ perl -MDevel::Size=total_size -wle '$hash{ $_ } = 1 for 1..10000;
> print
> total_size(\%hash); $hash2{ ("x" x 15) . $_ } = 1 for 1..10000; print
> total_size(\%hash2);'
> 604466
> 754466
>
> Вот массив в хеш пихать - ужас ужас:
> -bash$ perl -MDevel::Size=total_size -wle '$hash{ $_ } = 1 for 1..10000;
> print
> total_size(\%hash); $hash2{ $_ } = [1] for 1..10000; print
> total_size(\%hash2);'
> 604466
> 1164466
>
> Но нам массив и не нужен на самом деле, достаточно ведь последнего
> вхождения.
>
> my %position; # последнее вхождение
> my %count; # счетчик
>
> # ... в цикле
> if ( $position{$substr} + $length < $current_position ) {
>   $count{$substr}++; # тут же ... and return $substr
>   $position{$substr} = $current_position;
> }
>
> Получается вдвое больше памяти, чем просто счётчик, зато в один проход
> и не надо вообще больше ничего делать.
>
> --
> WBR,
> Konstantin S. Uvarin
> --
> Moscow.pm mailing list
> moscow-pm на pm.org | http://moscow.pm.org
>
----------- следущая часть -----------
Вложение в формате HTML было извлечено…
URL: <http://mail.pm.org/pipermail/moscow-pm/attachments/20130712/cd33eccc/attachment-0001.html>