Re^2: Challenge: Fast Common Substrings

[BrowserUk]

The same benchmark as above but excluding the two slowest/erroneous algorithms, allows me to run 1000 strings looking for common substrings of lengths 2 .. 6 and get more digestable results:

c:\test>608174-b -N=1000 -LENGTH=2
      Rate  BH2  BH1   MN  L~R  Buk
BH2 2.57/s   --  -8% -52% -73% -86%
BH1 2.81/s   9%   -- -48% -70% -85%
MN  5.41/s 110%  93%   -- -43% -71%
L~R 9.46/s 268% 237%  75%   -- -50%
Buk 18.9/s 635% 574% 249% 100%   --

----

BH2 => 14
L~R => 14
Buk => 14
BH1 => 14
MN => 14

c:\test>608174-b -N=1000 -LENGTH=3
      Rate  BH1   MN  BH2  L~R  Buk
BH1 2.51/s   -- -28% -54% -69% -81%
MN  3.50/s  40%   -- -36% -57% -73%
BH2 5.47/s 118%  56%   -- -33% -58%
L~R 8.20/s 227% 134%  50%   -- -38%
Buk 13.2/s 425% 276% 141%  61%   --

----

BH2 => 10
L~R => 10
Buk => 10
BH1 => 10
MN => 10

c:\test>608174-b -N=1000 -LENGTH=4
      Rate  BH1   MN  L~R  BH2  Buk
BH1 2.35/s   -- -23% -70% -73% -80%
MN  3.05/s  30%   -- -62% -64% -75%
L~R 7.92/s 237% 160%   --  -8% -34%
BH2 8.58/s 265% 182%   8%   -- -28%
Buk 12.0/s 410% 293%  51%  40%   --

----

BH2 => 6
L~R => 6
Buk => 6
BH1 => 6
MN => 6

c:\test>608174-b -N=1000 -LENGTH=5
      Rate  BH1   MN  L~R  BH2  Buk
BH1 2.38/s   -- -20% -71% -77% -80%
MN  2.98/s  25%   -- -64% -71% -75%
L~R 8.25/s 246% 177%   -- -21% -32%
BH2 10.4/s 337% 249%  26%   -- -14%
Buk 12.1/s 408% 307%  47%  16%   --

----

BH2 => 1
L~R => 1
Buk => 1
BH1 => 1
MN => 1

c:\test>608174-b -N=1000 -LENGTH=6
      Rate  BH1   MN  L~R  BH2  Buk
BH1 2.45/s   -- -19% -70% -78% -80%
MN  3.02/s  23%   -- -64% -73% -76%
L~R 8.29/s 238% 175%   -- -26% -34%
BH2 11.2/s 358% 272%  35%   -- -10%
Buk 12.5/s 410% 314%  51%  11%   --

----

BH2 => 0
L~R => 0
Buk => 0
BH1 => 0
MN => 0

[eric256]

/me benchmarks agian with his in there as a matter of pride.

C:\Perl\test>substr_bench.pl -N=1000 -LENGTH=2
       Rate  BH2  BH1   MN Eric  L~R  Buk
BH2  3.37/s   -- -20% -53% -70% -78% -87%
BH1  4.21/s  25%   -- -42% -62% -72% -84%
MN   7.22/s 114%  71%   -- -35% -52% -73%
Eric 11.1/s 231% 164%  54%   -- -26% -58%
L~R  15.1/s 347% 258% 109%  35%   -- -44%
Buk  26.7/s 694% 534% 270% 140%  77%   --

----

BH2 => 14
L~R => 12
Eric => 14
Buk => 14
BH1 => 14
MN => 14

C:\Perl\test>substr_bench.pl -N=1000 -LENGTH=3
       Rate  BH1   MN  BH2 Eric  L~R  Buk
BH1  3.88/s   -- -23% -39% -46% -73% -80%
MN   5.05/s  30%   -- -21% -30% -65% -74%
BH2  6.40/s  65%  27%   -- -11% -56% -67%
Eric 7.21/s  86%  43%  13%   -- -50% -63%
L~R  14.4/s 272% 185% 125% 100%   -- -26%
Buk  19.4/s 400% 284% 203% 169%  35%   --

----

BH2 => 9
L~R => 9
Eric => 9
Buk => 9
BH1 => 9
MN => 9

C:\Perl\test>substr_bench.pl -N=1000 -LENGTH=4
       Rate  BH1   MN Eric  BH2  L~R  Buk
BH1  3.56/s   -- -19% -43% -57% -74% -79%
MN   4.39/s  23%   -- -30% -47% -68% -74%
Eric 6.22/s  75%  42%   -- -25% -54% -63%
BH2  8.35/s 135%  90%  34%   -- -38% -51%
L~R  13.5/s 281% 209% 118%  62%   -- -20%
Buk  16.9/s 375% 285% 171% 102%  25%   --

----

BH2 => 4
L~R => 4
Eric => 4
Buk => 4
BH1 => 4
MN => 4

C:\Perl\test>substr_bench.pl -N=1000 -LENGTH=5
       Rate  BH1   MN Eric  BH2  L~R  Buk
BH1  3.82/s   -- -14% -34% -59% -72% -78%
MN   4.44/s  16%   -- -24% -52% -67% -74%
Eric 5.82/s  52%  31%   -- -37% -57% -66%
BH2  9.27/s 143% 109%  59%   -- -32% -46%
L~R  13.6/s 255% 205% 133%  46%   -- -21%
Buk  17.1/s 348% 285% 194%  85%  26%   --

----

BH2 => 0
L~R => 0
Eric => 0
Buk => 0
BH1 => 0
MN => 0

C:\Perl\test>substr_bench.pl -N=1000 -LENGTH=6
            (warning: too few iterations for a reliable count)

       Rate  BH1   MN Eric  BH2  L~R  Buk
BH1  3.56/s   -- -21% -38% -64% -73% -80%
MN   4.50/s  27%   -- -21% -54% -66% -74%
Eric 5.73/s  61%  27%   -- -42% -57% -67%
BH2  9.84/s 177% 119%  72%   -- -25% -43%
L~R  13.2/s 271% 193% 130%  34%   -- -24%
Buk  17.4/s 389% 286% 203%  77%  32%   --

----

BH2 => 1
L~R => 1
Eric => 1
Buk => 1
BH1 => 1
MN => 1