in reply to Re: A better implementation of LCSS?
in thread A better implementation of LCSS?

UPDATE: ahh, nevermind. BrowserUk just debunked this...
Somewhat related...

For what it's worth, I used Memoize on the String::LCSS::lcss sub, and the increase in performance is huge. In fact, String::LCSS is faster than String::LCSS_XS.

The String::LCSS_XS POD shows these Benchmark results (which I was able to reproduce): 

                   Rate    String::LCSS String::LCSS_XS
String::LCSS     60.9/s              --           -100%
String::LCSS_XS 84746/s         138966%              --

[download]

Here are the results with Memoize: 

String::LCSS    version = 0.12
String::LCSS_XS version = 1.2
>>>the quick brown fox <<<
>>>the quick brown fox <<<

            Rate LCSS_XS    LCSS
LCSS_XS 195695/s      --    -27%
LCSS    268817/s     37%      --

[download]

Here is the code to run it: 

use strict;
use warnings;
use Benchmark       qw(cmpthese);
use String::LCSS    qw();
use String::LCSS_XS qw();
use Memoize         qw(memoize);

memoize('String::LCSS::lcss');

printf "String::LCSS    version = %s\n", $String::LCSS::VERSION;
printf "String::LCSS_XS version = %s\n", $String::LCSS_XS::VERSION;

my $s = 'i pushed the lazy dog into a creek, the quick brown fox told 
+me to';
my $t = 'the quick brown fox jumps over the lazy dog';
 
printf ">>>%s<<<\n", String::LCSS::lcss   ($s, $t);
printf ">>>%s<<<\n", String::LCSS_XS::lcss($s, $t);
print "\n";

#cmpthese(100_000, { # w/out memoize
cmpthese(1_000_000, { # w/ memoize
    LCSS    => sub { my $lcss = String::LCSS::lcss   ($s, $t); },
    LCSS_XS => sub { my $lcss = String::LCSS_XS::lcss($s, $t); },
});

[download]

Keep in mind that String::LCSS has critical bugs.

Replies are listed 'Best First'.
Re^3: A better implementation of LCSS? (Memoize)
by BrowserUk (Patriarch) on Nov 18, 2015 at 21:33 UTC
    For what it's worth, I used Memoize on the String::LCSS::lcss sub, and the increase in performance is huge. In fact, String::LCSS is faster than String::LCSS_XS.

    Sorry, but that is a useless test. You are always testing the same two strings, which means that you are simply getting back the same result each time after the first, without having to re-perform the algorithm.

    With the rise and rise of 'Social' network sites: 'Computers are making people easier to use everyday'
    Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
    "Science is about questioning the status quo. Questioning authority". I knew I was on the right track :)
    In the absence of evidence, opinion is indistinguishable from prejudice.
[reply]
      OK, I guess I'm clueless in the ways of benchmarking. Do you think the results in the String::LCSS_XS POD are bogus, too? Unfortunately, I don't have the code for that benchmark. Can someone point me to a way to generate a meaningful test?
[reply]

        Memoize() is only of benefit if you call the memoised function multiple times with the same arguments -- ie. when it can return the previously returned value instead of recalculating it.

        Repeating the same test for a benchmark of a lcss() function makes for a totally artificial test.

        Of course, you could also apply the memoisation to the XS version and you'd restore the differential.

        With the rise and rise of 'Social' network sites: 'Computers are making people easier to use everyday'
        Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
        "Science is about questioning the status quo. Questioning authority". I knew I was on the right track :)
        In the absence of evidence, opinion is indistinguishable from prejudice.
[reply]

In Section Seekers of Perl Wisdom