Re^2: Possessive sub-pattern with non-greedy content + recursion: WHY does this work??

[Anonymous Monk]

Thanks, choroba, your module, blog post and linked paper look interesting. What follows isn't really on topic.

I lamented here recently about Rosetta Perl snippets quality; here it is again. Sort of consolation for me (after dear ikegami was kind enough to enlighten me about near total lack of understanding about regexes), that there are people even sloppier. It's a bit surprising you bothered to benchmark against that code (give each and every advantage to your opponent, no?). To wit:

(1) This sub uses package vars, the array grows an each call during benchmarking, kind of unfair position you put that contestant to, no? (2) It's a shock to see that all the innermost loop does is string reversing. (3) The condition in "if" is never true (4) the 2nd "for" gives the same result about half of the time because there's string overshoot beyond its length (5) I'd filter out duplicates as they appear instead of grepping later. Then:

sub rosetta_code_new {
    my ( $str ) = @_;
    
    my ( @pal, %seen );
    for my $n ( 0 .. length( $str ) - 1 ) {
        for my $m ( 1 .. length( $str ) - $n ) {
            my $strpal = substr $str, $n, $m;
            push @pal, $strpal
                if $strpal eq reverse $strpal and 
                   not $seen{ $strpal } ++
        }
    }
    
    return @pal
}

And:

         Rate rosetta eertree
eertree 1159/s      --    -27%
rosetta 1584/s     37%      --

Not exactly the result as published, methinks. To be fair, your solution outpaces the above naive one if e.g. "10" is increased to "20", but still, not by orders of magnitude:

         Rate rosetta eertree
rosetta 387/s      --    -31%
eertree 565/s     46%      --

I won't publish/compare with "my" recursive regex solution, it's slower. Not "orders of magnitude" neither, but, yeah, slow.

[choroba]

Interesting. You are right that the original Rosetta code could have been simplified and made more efficient. The Eertree algorithm still scales better, but you need to stretch the string a bit more. Fore example, for lengths 55 and 110:

          Rate rosetta_old rosetta_new     eertree
rosetta_old  145/s          --        -92%        -93%
rosetta_new 1925/s       1226%          --        -13%
eertree     2214/s       1424%         15%          --

              Rate rosetta_old rosetta_new     eertree
rosetta_old 20.0/s          --        -96%        -98%
rosetta_new  464/s       2218%          --        -60%
eertree     1166/s       5729%        151%          --

As you can see, the new Rosetta code is 4 times slower, but Eertree is only 2 times slower.

Here's the code for those interested:

Read more... (2 kB)

[Anonymous Monk]

Scaling better outcome isn't disputed, immediate results very much are. You missed - $n (see "overshoot" above). Perhaps you are tired I'm just irritating the hell out of people with non-issues, sorry

[choroba]

Oh thank you. The difference moved to 110 versus 220:

              Rate rosetta_old rosetta_new     eertree
rosetta_old 20.0/s          --        -98%        -98%
rosetta_new  864/s       4222%          --        -27%
eertree     1177/s       5784%         36%          --

              Rate rosetta_old rosetta_new     eertree
rosetta_old 2.63/s          --        -99%       -100%
rosetta_new  215/s       8058%          --        -67%
eertree      654/s      24749%        205%          --
1..2

I missed the - $n because I was trying to get all the palindromes from the Rosetta code instead of just the unique ones. It seemed the new code worked correctly, but the old one didn't, so I started experimenting with replicating its incorrect output...

[Anonymous Monk]

is never true is always true