RE: RE: Generating a Pattern

[eak]

I first have to say that I really enjoyed this problem. It took me a little while to come up with a working algorithm, unfortunately it wasn't at elegant as yours. I thought I would play with your version to see if I could improve upon it a bit. The only thing I could do was add the use of references which reduces the memcopy time on larger lists. Below is a script that benchmarked the old 'non_ref' vs. the new 'ref'. Not necessarily staggering, but an improvement. I compacted the for loop for flipping it around and putting the for statement at the end of the conditional line.

#!/usr/bin/perl
use Benchmark;
my $count = 100;
 
my $end = 30;
sub ref {
  my $a = [1];
 
  for(1..$end){
#    print "@$a\n";
 
    my @na;
    ($na[-1] == $_ ? $na[-2]++ : push @na, (1, $_)) for @$a;
    $a = \@na;
  }
}
 
sub no_ref {
  my @a = (1);
 
  my @na;
  for (1..$end){
#    print "@a\n";
 
    @na = ();
    ($na[-1] == $_ ? $na[-2]++ : push @na, (1, $_)) for @a;
 
    @a = @na;
  }
}
timethese($count, { 'no_ref' => \&no_ref , 'ref' => \&ref} );

Benchmark: timing 100 iterations of no_ref, ref...
    no_ref: 11 wallclock secs (11.12 usr +  0.04 sys = 11.16 CPU)
       ref:  9 wallclock secs ( 8.34 usr +  0.06 sys =  8.40 CPU)