comment on

(now it's not related to the PWC task), w.r.t. "horrible amount of backtracking", I think these 2 patterns

/(.(?1)(*F))/
/(.*)(*F)/
[download]

should backtrack about the same amount. Yet one is 4 orders of magnitude slower (with sample sizes and hardware I'm using) and clearly exponential. The other stays linear. Sorry I didn't re-run it with more "REPEATS" and am leaving it untidy, it's just "mad science" for laughs of course i.e. I now see recursive pattern wasn't a good idea to use for the task.

  1.4 +-------------------------------------------------+
      |      +      +      +       +      +      +      |
      |                                                A|
      |                                                 |
      |                                                 |
      |                                                A|
      |                                               A |
      |                                                 |
      |                                              A  |
      |                                                 |
      |                                             A   |
  1.2 |-+                                             +-|
      |                                             A   |
      |                                            A    |
      |                                                 |
      |                                           A     |
      |                                                 |
      |                                           A     |
      |                                          A      |
      |                                                 |
      |                                         A       |
      |                                                 |
    1 |-+                                      A      +-|
      |                                        A        |
      |                                                 |
      |                                       A         |
      |                                      A          |
      |                                                 |
      |                                      A          |
      |                                     A           |
      |                                                 |
      |                                    A            |
      |                                   A             |
  0.8 |-+                                             +-|
      |                                   A             |
      |                                  A              |
      |                                                 |
      |                                 A               |
      |                                 A               |
      |                                                 |
      |                               AA                |
      |                                                 |
      |                              A                  |
  0.6 |-+                            A                +-|
      |                                                 |
      |                            AA                   |
      |                                                 |
      |                            A                    |
      |                           A                     |
      |                          A                      |
      |                                                 |
      |                         A                       |
      |                        A                        |
      |                                                 |
  0.4 |-+                     A                       +-|
      |                       A                         |
      |                      A                          |
      |                    AA                           |
      |                                                 |
      |                   AA                            |
      |                  A                              |
      |                                                 |
      |                AAA                              |
      |               A                                 |
      |               A                                 |
  0.2 |-+            A                                +-|
      |             A                                   |
      |             A                                   |
      |          AAA                                    |
      |         AA                                      |
      |        A                                        |
      |       AA                                        |
      |     AA                                          |
      |   AAA                                           |
      | AAA                                             |
      |A     +      +      +       +      +      +      |
    0 +-------------------------------------------------+
     1000   2000   3000   4000    5000   6000   7000   8000

  1.2 +-------------------------------------------------+
      |      +      +      +       +      +      +      |
      |                                                 |
      |                                                 |
      |                                                 |
      |                                                A|
      |                                                A|
      |                                               A |
      |                                              A  |
      |                                             A   |
      |                                             A   |
      |                                            A    |
      |                                           A     |
    1 |-+                                        AA   +-|
      |                                         A       |
      |                                        A        |
      |                                        A        |
      |                                       A         |
      |                                      A          |
      |                                     AA          |
      |                                                 |
      |                                   AA            |
      |                                   A             |
      |                                  A              |
      |                                 A               |
  0.8 |-+                               A             +-|
      |                                A                |
      |                              AA                 |
      |                                                 |
      |                              A                  |
      |                            AA                   |
      |                            A                    |
      |                           A                     |
      |                         AA                      |
      |                         A                       |
      |                        A                        |
      |                       A                         |
      |                       A                         |
  0.6 |-+                    A                        +-|
      |                     A                           |
      |                    A                            |
      |                    A                            |
      |                   A                             |
      |                  A                              |
      |                  A                              |
      |                AA                               |
      |               A                                 |
      |               A                                 |
      |              A                                  |
      |             A                                   |
      |             A                                   |
  0.4 |-+          A                                  +-|
      |           A                                     |
      |          A                                      |
      |         A                                       |
      |        A                                        |
      |        A                                        |
      |       A                                         |
      |      A                                          |
      |     A                                           |
      |     A                                           |
      |   AA                                            |
      |                                                 |
  0.2 |-+ A                                           +-|
      |  A                                              |
      | A                                               |
      |A                                                |
      |                                                 |
      |                                                 |
      |                                                 |
      |                                                 |
      |                                                 |
      |                                                 |
      |                                                 |
      |                                                 |
      |      +      +      +       +      +      +      |
    0 +-------------------------------------------------+
    1e+07  2e+07  3e+07  4e+07   5e+07  6e+07  7e+07  8e+07
[download]

####

use strict;
use warnings;

use Benchmark qw/ timeit :hireswallclock /;
use Chart::Gnuplot;
use File::Spec::Functions 'catfile';
use File::Basename 'dirname';

my $GP = catfile dirname( $^X ), '../../c/bin/gnuplot.exe';
die unless -x $GP;              # assume Strawberry Perl

use constant REPEATS => 1;

STDOUT-> autoflush( 1 );

{
    my ( @x, @y, @datasets );
    for my $x ( map 1e6 * $_, 10 .. 80 ) {
        print "$x ";
        my $s = 'a' x $x;
        my $t = timeit REPEATS, sub { $s =~ /(.*)(*F)/ };
        my $y = $t-> [ 1 ] / $t-> [ -1 ];
        push @x, $x;
        push @y, $y;
    }
    print "\n\n";
    push @datasets, Chart::Gnuplot::DataSet-> new(
        xdata => \@x,
        ydata => \@y,
        style => 'points',
    );
    my $chart = Chart::Gnuplot-> new( 
        gnuplot  => $GP,
        terminal => 'dumb size 60, 80',
    );
    $chart-> plot2d( @datasets );
}
{
    my ( @x, @y, @datasets );
    for my $x ( map 1e2 * $_, 10 .. 80 ) {
        print "$x ";
        my $s = 'a' x $x;
        my $t = timeit REPEATS, sub { $s =~ /(.(?1)(*F))/ };
        my $y = $t-> [ 1 ] / $t-> [ -1 ];
        push @x, $x;
        push @y, $y;
    }
    print "\n\n";
    push @datasets, Chart::Gnuplot::DataSet-> new(
        xdata => \@x,
        ydata => \@y,
        style => 'points',
    );
    my $chart = Chart::Gnuplot-> new( 
        gnuplot  => $GP,
        terminal => 'dumb size 60, 80',
    );
    $chart-> plot2d( @datasets );
}
[download]

In reply to Re: Recursive sub-pattern spectacularly slow, what's wrong? (me, or just this use case, or a bug?) by Anonymous Monk
in thread Recursive sub-pattern spectacularly slow, what's wrong? (me, or just this use case, or a bug?) by Anonymous Monk

Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!

Titles consisting of a single word are discouraged, and in most cases are disallowed outright.

Read Where should I post X? if you're not absolutely sure you're posting in the right place.

Please read these before you post! —

Posts may use any of the Perl Monks Approved HTML tags:

a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, details, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, summary, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr

You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)

	For:		Use:
	&		`&`
	<		`<`
	>		`>`
	[		`[`
	]		`]`

Link using PerlMonks shortcuts! What shortcuts can I use for linking?

See Writeup Formatting Tips and other pages linked from there for more info.