<div dir="ltr">А вот тако<br><div><div><div class="gmail_extra"><br><br><div class="gmail_quote">12 июля 2013 г., 17:12 пользователь Konstantin S. Uvarin <span dir="ltr"><<a href="mailto:khedin@gmail.com" target="_blank">khedin@gmail.com</a>></span> написал:<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">Приветствую!<br>
<div><div class="h5"><br>
> >   { 15_символов_подряд => [ вхождение, вхождение2, ... ] }<br>
> ><br>
> Думаю, что стоит ограничиться<br>
> ++$substr{15_символов_подряд};<br>
> Вот если найдётся подстрока 5+, тогда и заморачиваться.<br>
> Должно быть сильно дешевле по памяти и быстрее.<br>
><br>
> Не зная данных, сложно предлагать что-то оптимальное, но скорее<br>
всего можно<br>
> делать<br>
> ++$substr{N_символов_подряд};<br>
> Где N достаточно большое, для отбрасывания большинства лишних<br>
совпадений,<br>
> но сильно меньше 15;<br>
<br>
</div></div>С меньше_15_символов нет особого смысла заморачиваться, похоже -<br>
длина ключей заметна, но погоды не делает:<br>
-bash$ perl -MDevel::Size=total_size -wle '$hash{ $_ } = 1 for 1..10000; print<br>
total_size(\%hash); $hash2{ ("x" x 15) . $_ } = 1 for 1..10000; print<br>
total_size(\%hash2);'<br>
604466<br>
754466<br>
<br>
Вот массив в хеш пихать - ужас ужас:<br>
-bash$ perl -MDevel::Size=total_size -wle '$hash{ $_ } = 1 for 1..10000; print<br>
total_size(\%hash); $hash2{ $_ } = [1] for 1..10000; print<br>
total_size(\%hash2);'<br>
604466<br>
1164466<br>
<br>
Но нам массив и не нужен на самом деле, достаточно ведь последнего<br>
вхождения.<br>
<br>
my %position; # последнее вхождение<br>
my %count; # счетчик<br>
<br>
# ... в цикле<br>
if ( $position{$substr} + $length < $current_position ) {<br>
  $count{$substr}++; # тут же ... and return $substr<br>
  $position{$substr} = $current_position;<br>
}<br>
<br>
Получается вдвое больше памяти, чем просто счётчик, зато в один проход<br>
и не надо вообще больше ничего делать.<br>
<div class="HOEnZb"><div class="h5"><br>
--<br>
WBR,<br>
Konstantin S. Uvarin<br>
--<br>
Moscow.pm mailing list<br>
<a href="mailto:moscow-pm@pm.org">moscow-pm@pm.org</a> | <a href="http://moscow.pm.org" target="_blank">http://moscow.pm.org</a><br>
</div></div></blockquote></div><br></div></div></div></div>