|
in reply to Re: how to count the number of repeats in a string (really!)
in thread how to count the number of repeats in a string (really!)
Your regex /(.{2,}).*\1/g will always try to capture the largest thing it can in $1. In your example string, every "b" character is followed by a "c". So every position where the string could match /b.*b/, it could also match /bc.*bc/. Since the "bc" version is longer, that's the one that will be tried first by the regex engine, and will return with success. It will never return success with $1 eq "b", even though a "b" character repeats itself in the string.
I personally believe that this obvious... now that you point it out... Anyway I now wonder if at this point the best thing could be to generate all substrings e.g. with two nested maps and a uniq-like technique and possibly filter out those that have a count of 1 if one is not interested in them. My approach at a filtering in the generation phase by means of a regex may be fixable somehow but I can't see an easy way...
Update: it's also worth noting that m//g does not mean "try to match every possible way this match could succeed". Instead it means, "try to find one match starting at each position in the string" .. So in the above, when it matches on "bc", it will not continue backtracking to pick up the match with "b". Instead, it will be satisfied that it found a match starting at that position, increment pos, and move on.
But in fact this is the reason why I explicitly set pos. Perl 6 provides an adverb to do so in the first place instead -matching with superimpositions-, which is very good.
Update: the following, for example, finally works really correctly.
#!/usr/bin/perl
use strict;
use warnings;
use Data::Dumper;
use constant MIN => 2;
my $str='aabcdabcabcecdecd';
sub count {
local $_=shift;
my $l=length;
my %count;
for my $off (0..$l-1) {
for my $len (MIN .. $l-$off) {
my $s=substr $_, $off, $len;
$count{ $s } ||= ()= /$s/g;
}
$count{$_} == 1 and
delete $count{$_} for keys %count;
}
\%count;
}
print Dumper count $str;
__END__
|
Re^3: how to count the number of repeats in a string (really!)
by Krambambuli (Curate) on Nov 14, 2007 at 17:56 UTC
|
I've tried to smoothen the differences between your non-recursive but using regexp solution and mine, which is recursive but doesn't use any RX.
After benchmarking, you're the clear winner:
Benchmark: timing 2000 iterations of Krambambuli, blazar...
Krambambuli: 4 wallclock secs ( 3.28 usr + 0.01 sys = 3.29 CPU) @ 6
+07.90/s (n=2000)
blazar: 1 wallclock secs ( 0.80 usr + 0.00 sys = 0.80 CPU) @ 25
+00.00/s (n=2000)
Congrats! :)
Here's the code I've used for the benchmarking.
Update: Actually, it's in fact the other way round, my code is faster - I've just named the benchmarked subs wrongly. Duh! Sorry.
| [reply]
[d/l]
[select] |
|
|
After benchmarking, you're the clear winner:
I personally believe that I'm not! ;)
Anyway, I extended the benchmark to include oha's solution (in my version) and ikegami's. For definiteness I made sure to compare subs that do exactly the same thing: accept a string and return a hashref of the counts, and that the counts are those of strings of length 2 or more repeated 2 or more times. I could not include lodin's solution because I haven't the slightest idea of how to modify it so that only strings of length 2 or more are taken into account. (Short of deleting thos of length 1.) Admittedly, it would be interesting to see how the benchmark goes with different data sets...
Results:
Rate blazar kramba ikegami oha
blazar 405/s -- -77% -89% -89%
kramba 1788/s 341% -- -52% -52%
ikegami 3743/s 823% 109% -- -0%
oha 3743/s 823% 109% 0% --
Update: I included lodin's solution as per his direction as follows:
I also corrected the kramba subroutine as per lodin's remark:
The new results are:
Rate blazar kramba oha ikegami lodin
blazar 577/s -- -72% -90% -91% -91%
kramba 2045/s 254% -- -66% -67% -69%
oha 6039/s 946% 195% -- -2% -9%
ikegami 6154/s 966% 201% 2% -- -8%
lodin 6667/s 1055% 226% 10% 8% --
Update: lodin draws my attention by /msg on the fact that the closure leaks and he directs me to his own Sub::Recursive both for an explanation and a fix. He also notices that he didn't include the manual fix in the docs. Anyway, one can use local our $count; in this particular instance. I'm doing a new benchmark which will be posted in a separate node taking also this into account, although I don't think it will make that much of a difference. | [reply]
[d/l]
[select] |
|
|
| [reply]
[d/l]
[select] |
|
|
| [reply]
[d/l]
[select] |
|
|
Admittedly, it would be interesting to see how the benchmark goes with different data sets...
I used the following text, not big but should be enough
my $s = 'Lorem ipsum dolor sit amet, consectetuer adipiscing elit,
sed diam nonummy nibh euismod tincidunt ut laoreet dolore magna
aliquam erat volutpat. Ut wisi enim ad minim veniam, quis nostrud
exerci tation ullamcorper suscipit lobortis nisl ut aliquip ex ea
commodo consequat. Duis autem vel eum iriure dolor in hendrerit in
vulputate velit esse molestie consequat, vel illum dolore eu feugiat
nulla facilisis at vero eros et accumsan et iusto odio dignissim qui
blandit praesent luptatum zzril delenit augue duis dolore te feugait
nulla facilisi.';
$s = s/[\r\n]//g;
After reading the code of ikegami and lodin, "I personally believe"d they were faster but i was wrong:
s/iter ikegami lodin oha
ikegami 1.43 -- -1% -48%
lodin 1.42 1% -- -48%
oha 0.740 93% 92% --
I suspect the regex engine is so much smarter in finding fixed char repetition to gain more then the gain of doing lots regex call...
Oha
PS: i didn't passed the string to the subs and didn't returned the results.
Update: removed the \n from the string, updated results
Update: my code is broken: it must reset pos to the previous pos+1 (if not some subpatterns aren't matched). updated results are as "i personally believe"d:
s/iter oha lodin ikegami
oha 1.66 -- -12% -14%
lodin 1.46 14% -- -2%
ikegami 1.43 16% 2% --
| [reply]
[d/l]
[select] |
|
|
I've made just a few changes (mostly to my sub, so that it comes closer to my original design - your modifications added a few unnecessary steps) and run the benchmarks again.
The results seem to support my original suspicion that - at least for this particular problem - a regexp based solution would have to loose the fight against an approach that never has to look behind or ahead, but just touches every possible substring exactly 1 time:
Results for string:
"aabcdabcabcecdecd "
Rate blazar kramba ikegami lodin oha
blazar 464/s -- -77% -89% -90% -90%
kramba 2062/s 344% -- -52% -54% -58%
ikegami 4255/s 817% 106% -- -4% -13%
lodin 4444/s 858% 116% 4% -- -9%
oha 4878/s 951% 137% 15% 10% --
Results for string:
"aabcdabcabcecdecd aabcdabcabcecdecd "
Rate blazar oha kramba ikegami lodin
blazar 92.4/s -- -85% -86% -86% -87%
oha 610/s 560% -- -7% -9% -14%
kramba 658/s 612% 8% -- -1% -7%
ikegami 667/s 621% 9% 1% -- -6%
lodin 709/s 667% 16% 8% 6% --
Results for string:
"aabcdabcabcecdecd aabcdabcabcecdecd aabcdabcabcecdecd aabcdabcabcecde
+cd "
Rate blazar lodin ikegami oha kramba
blazar 21.4/s -- -85% -86% -86% -90%
lodin 144/s 574% -- -3% -5% -35%
ikegami 148/s 594% 3% -- -2% -33%
oha 151/s 607% 5% 2% -- -31%
kramba 220/s 930% 53% 48% 46% --
Here's the full code I've used for benchmarking.
Another mention I'd make is that if some changes would be needed to the subs - like for example considering at least MIN_REPEATS repetitions of a string to be counted - I'm afraid it might be rather challenging in modifying the RX-ish solutions.
Speaking for me, I wouldn't know how to make it in the code above, even if I think of me as not being a novice any more when dealing with regular expressions.
Update Ahmm... there are some things broken, and I'll have to find out which one. Checking results for simple cases looked ok, so I thought things are ok. But then trying to run the benchmark for the longer text that Oha proposed, I noticed some problems and so tried to just output the _count_ of strings retained by each sub for a string like
'aabcdabcabcecdecd aabcdabcabcecdecd aabcdabcabcecdecd aabcdabcabcecdecd '
Much to my surprize, that came out as
467,337,791,467,467
for respectively blazar, oha, kramba, ikegami, lodin. Ooops...
How was that: who has a clock, knows what the time is, who has 2 clocks, has a problem... :)
Update 2 With Oha's longer latin text, the counts are - in the same order as above - 419,244,371,371,371 and my little recursive beauty complains about 'Deep recursion on subroutine "main::kramba" at ./test.pl line 95'. Well, understandable...
| [reply]
[d/l]
[select] |
|
|
|
|
|
|
|
|
|
|
