#!/usr/bin/perl
use strict;
use warnings;

sub compare;

my @l;
for (10, 100, 1000)
{
    @l = map { "a$_" } 1..$_;
    compare "Pre-sorted";
    
    @l = reverse @l;
    compare "Reverse-sorted";
    
    use List::Util qw(shuffle);
    @l = shuffle @l;
    compare "Shuffled";
}

my %regexes;
sub brute_force
{
    my $c = 0;
    my @s = sort {
        $c += 2;
        ($a =~ /(\d+)/)[0] <=> ($b =~ /(\d+)/)[0]
    } @l;
    push @{$regexes{force}}, $c;
}

sub ST
{
    my $c = 0;
    my @s = map { $_->[1] } sort { $a->[0] <=> $b->[0] } map {
        $c += 1;
        /(\d+)/;
        [ $1, $_ ]
    } @l;
    push @{$regexes{ST}}, $c;
}

sub compare
{
    use Benchmark qw(cmpthese);

    my $title = shift;
    my $len   = @l;
    $title = "$title ($len).";
    print $title, "\n";
    print '-' x length $title, "\n";
    %regexes = ();

    cmpthese(-1,
             {
                 force => \&brute_force,
                 ST    => \&ST,
             }
            );
    for (qw(force ST))
    {
        use List::Util qw(sum);
        my $avg = sum(@{$regexes{$_}}) / @{$regexes{$_}};
        printf "%10s %d regexes\n", $_, $avg;
    }
    print "\n";
}