Mark Aufflick comment on Recursive Regular Expressions

Privacy Controls Software from ParetoLogic

Style distinguishes excellence from accomplishment.

James Coplien

I am doing a startup!

Cross-browser testing from your browser

I have written my first book!

Awk one-liners explained

You're viewing a comment by Mark Aufflick and its responses.

Mark Aufflick Permalink

December 15, 2009, 03:05

This approach is really interesting. It is worth pointing out that you can achieve the same match non-recursively with two regexes. With my versions of perl (5.10 on Windows and 5.8 Linux) this approach turns out to be much faster even though it appears to have more steps.

                  Rate     recursive non_recursive
recursive      41580/s            --          -93%
non_recursive 606061/s         1358%            --

use Benchmark qw(cmpthese);

use strict;
use warnings;

use vars qw($recursive_regex);

my $str = "0"x50 . "1"x50;
$recursive_regex = qr/0(??{$recursive_regex})*1/;

sub recursive {
  if ($str =~ /^$recursive_regex$/) {
    # do nothing - printing to stdout would
    # be the most expensive operation here
  }
}

sub non_recursive {
  $str =~ /^(0*)/;
  my $num_zeroes = length $1;
  if ($str =~ /^0{$num_zeroes}1{$num_zeroes}$/) {
    # do nothing
  }
}

cmpthese(400000,
     {
     recursive => \&recursive,
     non_recursive => \&non_recursive,
     });

Reply to this comment