Re^2: A better implementation of LCSS? (Memoize)

[toolic]

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

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

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); },
});

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

[BrowserUk]

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.

[toolic]

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?

[BrowserUk]

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.