Beefy Boxes and Bandwidth Generously Provided by pair Networks
Perl Monk, Perl Meditation
 
PerlMonks  

Re^4: how to count the number of repeats in a string (really!)

by blazar (Canon)
on Nov 14, 2007 at 22:08 UTC ( #650860=note: print w/replies, xml ) Need Help??


in reply to Re^3: how to count the number of repeats in a string (really!)
in thread how to count the number of repeats in a string (really!)

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...

#!/usr/bin/perl use strict; use warnings; use Data::Dumper; use constant MIN => 2; use Benchmark qw/:all :hireswallclock/; my $str='aabcdabcabcecdecd'; sub blazar { 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; } sub oha { my $s=shift; my %saw; while($s =~ /(..+)(?=.*?\1)/g) { for my $x (0..length $1) { @saw{ map {substr $1, $x, $_} $x+2..length $1 } = (); } } $saw{$_} =()= $s =~ /\Q$_/g for keys %saw; \%saw; } { my %count; sub count1 { my( $string) = @_; my $length = length( $string ); if ($length < MIN) { $count{$_} == 1 and delete $count{$_} for keys %count; return \%count; } for my $l (MIN..$length) { my $s = substr( $string, 0, $l ); $count{ $s } += 1; } count1( substr( $string, 1 ) ); } sub kramba { count1 shift; for (keys %count) { delete $count{$_} unless $count{$_} >= 2 and length($_) >= MIN; } \%count; } } sub ikegami { my $str = shift; local our %counts; $str =~ / (.{2,}) # or (.+) (?(?{ !$counts{$1} })(?=.*\1)) (?{ ++$counts{$1} }) (?!) /x; \%counts; } cmpthese 10_000 => { blazar => sub { blazar $str }, oha => sub { oha $str }, kramba => sub { kramba $str }, ikegami => sub { ikegami $str }, }; __END__

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:

sub lodin { my $str = shift; local our %count; $str =~ / (.{2,}) (?(?{ $count{$1} }) (?!) ) .* \1 (?{ ($count{$1} ||= 1)++ }) (?!) /x; \%count; }

I also corrected the kramba subroutine as per lodin's remark:

sub kramba { my %count; my $count; $count = sub { my( $string) = @_; my $length = length( $string ); if ($length < MIN) { $count{$_} == 1 and delete $count{$_} for keys %count; return \%count; } for my $l (MIN..$length) { my $s = substr( $string, 0, $l ); $count{ $s } += 1; } $count->( substr( $string, 1 ) ); }; $count->(shift); for (keys %count) { delete $count{$_} unless $count{$_} >= 2 and length($_) >= MIN; } \%count; }

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.

Replies are listed 'Best First'.
Re^5: how to count the number of repeats in a string (really!)
by lodin (Hermit) on Nov 14, 2007 at 23:41 UTC

    To include mine, just change .+ to .{N,} where N is the minimum length.

    lodin

Re^5: how to count the number of repeats in a string (really!)
by lodin (Hermit) on Nov 15, 2007 at 00:00 UTC

    The kramba subroutine suffers from an accumulating %count. It can be fixed by doing %count = () and returning { %count } (a copy of %count); making %count global and localizing it; or my favourite: write the recursive subroutine as an anonymous closure in kramba.

    lodin

Re^5: how to count the number of repeats in a string (really!)
by oha (Friar) on Nov 15, 2007 at 11:22 UTC
    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% --
Re^5: how to count the number of repeats in a string (really!)
by Krambambuli (Curate) on Nov 15, 2007 at 18:35 UTC
    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...


    Krambambuli
    ---
    enjoying Mark Jason Dominus' Higher-Order Perl

      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.

      One simple solution is to go back to my (unposted) original solution and check MIN_REPEATS outside.

      use constant MIN_REPEATS => 2; # Must have at least this many repeats my $str = 'aabcdabcabcecdecd'; local our %counts; $str =~ /(.{2,})(?{ ++$counts{$1} })(?!)/s; delete @counts{ grep $counts{$_}<MIN_REPEATS, keys %counts }; use Data::Dumper; print Dumper \%counts;

      That way, there's nothing complicated left in the regex. The only part that's modifiable is /.{2,}/, which is easier to understand and modify than hand-rolled parsing code.

      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

      Not so! The above regex never has to look beind or ahead and touches every possible substring exactly 1 time.

      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.

      I've updated my original reply to include minimum substring length and minimum matched patterns. It would be interesting to see our and the other subroutines benchmarked against each other with this addition.

      lodin

      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.

      I personally believe that those steps were not all that unnecessary. To be definite, I chose to compare subs that accept a string and return a hashref of the counts. Yours doesn't, so some extra step is required. According to the last update to Re^4: how to count the number of repeats in a string (really!), I'm posting a new benchmark here, with your sub as a thin layer around the recursive sub. I hope that is fine...

      So, instead of the benchmark, for the moment I'm posting the script with the tests:

      15 tests out 18 fail.

      Update: I'm an idiot! All tests run smoothly once I use the correct reference. The lesson in this is: don't post when you're too tired. I'm going to sleep and I will update the node with the actual benchmark tomorrow morning... Sorry for the noise!

      Update: Ok, I woke up and I'm not that tired anymore. Here's the complete script:

      And here's the output:

      Krambambuli seems to win in the long string case. Anyway, analysis? Refinements, comments, additions?

      Update: well done, lodin++.

        Anyway, analysis? Refinements, comments, additions?

        These routines are still not equivalent. They all give different results for e.g. 'aaaaa'. You're not using ikegami's version from Re^6: how to count the number of repeats in a string (really!). With that version, ikegami's and krambambuli's versions are equivalent. A simple modification to the regex in your routine makes that equivalent too. I also removed the tail recursion from kramba, which improves the performance with about 50 %.

        The return value from these routines should be interpreted as the answer to "how many unique substrings are there in the string, and what's their frequency". This is a different problem from "how many times is a substring sequentially repeated (possibly with other substrings inbetween) in the string", which is the problem most of us solved initially.

        Here's the code and the output:

        use strict; use warnings; use Test::More 'no_plan'; use Benchmark qw/:all :hireswallclock/; my $str = 'aabcdabcabcecdecdaaaa'; sub blazar { my ($str, $min_len, $min_rep)=@_; my $l=length($str); my %count; for my $off (0..$l-1) { for my $len ($min_len .. $l-$off) { my $s = quotemeta substr $str, $off, $len; $count{ $s } ||= () = $str =~ /(?=$s)./gs; } $count{$_} < $min_rep and delete $count{$_} for keys %count; } \%count; } sub kramba { my ($str, $min_len, $min_rep)=@_; my %count; for my $c (0 .. length($str) - $min_len) { my $string = substr($str, $c); for my $l ($min_len .. length $string) { $count{substr($string, 0, $l)}++; } } for (keys %count) { delete $count{$_} if $count{$_} < $min_rep; } return \%count; } sub ikegami { my ($str, $min_len, $min_rep)=@_; local our %counts; use re 'eval'; $str =~ / (.{$min_len,}) (?{ ++$counts{$1} }) (?!) /x; for (keys %counts) { delete $counts{$_} if $counts{$_} < $min_rep; } \%counts; } my %subs = ( ikegami => \&ikegami, blazar => \&blazar, kramba => \&kramba, ); for my $len (1..3) { for my $rep (2..3) { my $tag="len=$len, rep=$rep"; my $ref = ikegami($str, $len, $rep); for my $name (keys %subs) { my $code = $subs{$name}; is_deeply($code->($str, $len, $rep), $ref, "$name - $tag") +; } } } print "\n"; for my $s ( map {$str x $_} 1,3,42) { for my $len (1..2) { for my $rep (2..3) { printf "length=%d, min_len=%d, min_rep=%d\n", length $s, $len, $rep ; cmpthese(-60, { map { my $c = $subs{$_}; $_ => sub { $c->($s, $len, $rep) } } keys %subs }); print "\n"; } } } __END__ ok 1 - blazar - len=1, rep=2 ok 2 - ikegami - len=1, rep=2 ok 3 - kramba - len=1, rep=2 ok 4 - blazar - len=1, rep=3 ok 5 - ikegami - len=1, rep=3 ok 6 - kramba - len=1, rep=3 ok 7 - blazar - len=2, rep=2 ok 8 - ikegami - len=2, rep=2 ok 9 - kramba - len=2, rep=2 ok 10 - blazar - len=2, rep=3 ok 11 - ikegami - len=2, rep=3 ok 12 - kramba - len=2, rep=3 ok 13 - blazar - len=3, rep=2 ok 14 - ikegami - len=3, rep=2 ok 15 - kramba - len=3, rep=2 ok 16 - blazar - len=3, rep=3 ok 17 - ikegami - len=3, rep=3 ok 18 - kramba - len=3, rep=3 length=21, min_len=1, min_rep=2 Rate blazar ikegami kramba blazar 364/s -- -84% -86% ikegami 2329/s 539% -- -13% kramba 2674/s 634% 15% -- length=21, min_len=1, min_rep=3 Rate blazar ikegami kramba blazar 355/s -- -85% -87% ikegami 2316/s 553% -- -16% kramba 2744/s 674% 18% -- length=21, min_len=2, min_rep=2 Rate blazar ikegami kramba blazar 381/s -- -85% -87% ikegami 2462/s 546% -- -13% kramba 2826/s 642% 15% -- length=21, min_len=2, min_rep=3 Rate blazar ikegami kramba blazar 381/s -- -84% -86% ikegami 2424/s 537% -- -13% kramba 2802/s 636% 16% -- length=63, min_len=1, min_rep=2 Rate blazar ikegami kramba blazar 28.8/s -- -91% -94% ikegami 328/s 1039% -- -26% kramba 444/s 1441% 35% -- length=63, min_len=1, min_rep=3 Rate blazar ikegami kramba blazar 35.1/s -- -90% -92% ikegami 340/s 870% -- -21% kramba 432/s 1130% 27% -- length=63, min_len=2, min_rep=2 Rate blazar ikegami kramba blazar 32.0/s -- -91% -93% ikegami 355/s 1009% -- -21% kramba 452/s 1312% 27% -- length=63, min_len=2, min_rep=3 Rate blazar ikegami kramba blazar 35.0/s -- -90% -92% ikegami 335/s 855% -- -21% kramba 423/s 1106% 26% -- length=882, min_len=1, min_rep=2 Rate blazar ikegami kramba blazar 6.46e-002/s -- -95% -95% ikegami 1.20/s 1754% -- -16% kramba 1.42/s 2104% 19% -- length=882, min_len=1, min_rep=3 Rate blazar ikegami kramba blazar 6.16e-002/s -- -95% -96% ikegami 1.17/s 1804% -- -17% kramba 1.41/s 2189% 20% -- length=882, min_len=2, min_rep=2 Rate blazar ikegami kramba blazar 6.14e-002/s -- -95% -96% ikegami 1.18/s 1829% -- -17% kramba 1.42/s 2213% 20% -- length=882, min_len=2, min_rep=3 Rate blazar ikegami kramba blazar 6.27e-002/s -- -95% -96% ikegami 1.18/s 1779% -- -18% kramba 1.44/s 2197% 22% -- 1..18

        lodin

Log In?
Username:
Password:

What's my password?
Create A New User
Domain Nodelet?
Node Status?
node history
Node Type: note [id://650860]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others exploiting the Monastery: (4)
As of 2022-05-23 19:49 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?
    Do you prefer to work remotely?



    Results (82 votes). Check out past polls.

    Notices?