Beefy Boxes and Bandwidth Generously Provided by pair Networks
Perl-Sensitive Sunglasses
 
PerlMonks  

Generating a Pattern

by japhy (Canon)
on Jul 24, 2000 at 22:32 UTC ( #24145=CUFP: print w/ replies, xml ) Need Help??

There's an interesting number pattern:
1 1 1 2 1 1 2 1 1 1 1 1 2 2 1 3 1 2 2 1 1
For those of you that don't know this pattern, each line is a description of the previous line. For instance, the line "1 1 1 2 2 1" describes the line "1 2 1 1", because it says "one 1, one 2, two 1's". And so on.

On PerlGuru.com, there was recently a quiz to come up with a good (fast? short?) way to create these lines in Perl. I came up with a very short solution, as well as a very fast solution. These are in the form:
@a = (1); for (1..10) { print "@a\n"; # real juicy stuff here }
I'd like to see possible solutions from people. My fastest code executed the 1..10 loop 500 times in 2.40 seconds, and a 1..35 loop 10 times in 43.51 seconds. My shortest one is a bit slower, because it uses a regex, at 3.76 seconds and 57.35 seconds.

Comment on Generating a Pattern
Select or Download Code
RE: Generating a Pattern
by fundflow (Chaplain) on Jul 25, 2000 at 01:29 UTC
    Here's my version:
    @a = (1); for (1..10) { print "@a\n"; @na=(); for (@a) { $na[-1] == $_ ? $na[-2]++ : push @na, (1, $_) } @a=@na; }
    It does not move elements around (assuming push/pop are doing the natural thing) and has only one temporary copy.

    Update: Use [-1] instead of [$#na]. Cool, learned a new thing!
    Update: use ?: instead of if/then
      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)  
      
RE: Generating a Pattern
by lhoward (Vicar) on Jul 25, 2000 at 03:28 UTC
    My fastest did 500 iterations of 1..10 in 0.23 seconds and 10 iterations of 1..35 in 3.72 seconds.

    Why don't you post your code so we can benchmark against it in a meaningful comparison. Raw time numbers (like I posted above) mean nothing cause I could have written really bad code, but benchmarked it on a Cray....

RE: Generating a Pattern
by turnstep (Parson) on Jul 25, 2000 at 05:04 UTC

    Here's how I did it. Have no idea how this does on time.

    #!perl $total=10; ## Set to 1000 and watch your memory drain away! :) @a=qw(1); for (1..$total) { print "@a\n"; my @all; $count=1; $x=0; { if ($a[$x] != $a[$x+1]) { push(@all, $count); push(@all, $a[$x]); $count=0; } last unless ++$count and $a[$x++]; redo; } *a=\@all; }
RE: Generating a Pattern
by japhy (Canon) on Jul 25, 2000 at 07:39 UTC
    Here's my code:
    # fastest my @a = (1); for (1..10) { my $s = @a; while ($s-- and my $e = shift @a) { push @a, 1, $e; $a[-2]++, $s--, shift @a while $a[0] == $e and $s; } } # shortest my @a = (1); for (1..10) { my $i; @a = map $i++ % 2 : length : $_, join("", @a) =~ /((\d)\2*)/g; }


    $_="goto+F.print+chop;\n=yhpaj";F1:eval
RE: Generating a Pattern
by hawson (Monk) on Jul 27, 2000 at 00:47 UTC
    Here's mine:
    #!/usr/local/bin/perl @a=split(//,"1"); #easier to make test strings this way. :) for (1..10) { print "@a\n"; @b=(); $a=join("",@a); while ( $a =~ /((.)\2*/cg ) { push (@b, (length $1, $2)); } @a=@b }
    500 iterations of this took 1.15 seconds. 10 iterations running 1..35 took 18.73 seconds. For reference, I'm running this on an Ultrasparc-5.
      That is more or less identical to my regex solution. Very nice, though.

      $_="goto+F.print+chop;\n=yhpaj";F1:eval
RE: Generating a Pattern
by bastard (Hermit) on Jul 29, 2000 at 02:01 UTC
    1-10, 500 reps = 1 secs ( 1.09 usr 0.00 sys = 1.09 cpu)
    1-35, 10 reps = 17 secs (17.67 usr 0.02 sys = 17.69 cpu)
    #!/usr/local/bin/perl use Benchmark; $t0 = new Benchmark; for (my $x = 0; $x < 500; $x++) { my $numb = 1; for (my $x = 0; $x < 10; $x++) { my @numb = split(//, $numb); my $count = 1; my $newnumb = ""; for(my $x = 1; $x <= length($numb); $x++) { if ($numb[$x-1] ne $numb[$x]) { $newnumb .= "$count$numb[$x-1]"; $count = 1; } else { $count++; } } $numb = $newnumb; } } $t1 = new Benchmark; $td = timediff($t1,$t0); print timestr($td), "\n";
RE: Generating a Pattern
by jimt (Chaplain) on Aug 10, 2000 at 19:59 UTC
    Just to chime in with my own version,
    1-10, 500x: 2 secs ( 1.13 usr 0.00 sys = 1.13 cpu) (printing) 1-10, 500x: 1 secs ( 0.48 usr 0.00 sys = 0.48 cpu) (not printing) 1-35m 10x: 26 secs (26.53 usr 0.00 sys = 26.53 cpu) (printing) 1-35, 10x: 15 secs (15.05 usr 0.00 sys = 15.05 cpu) (not printing)
    My approach is similar to several of the ones already posted, but differs enough that I figured I might as well post it:
    $x = 1; for(1..10){ $x =~ s/((.)\2*)/length($1).$2/ge; #print "@{[split//,$x]}\n"; }
    Uncomment that print line to print everything out. And, of course, get rid of the array-de-ref function call if you don't care about spaces between the numbers.

    Incidentally, I used the array ref so I could take advantage of $" being a space and not have to worry about mapping the numbers so they'd have spaces between them.
Benchmarks OT
by premchai21 (Curate) on Mar 27, 2001 at 05:24 UTC
    Gas this OS! Am using WinNT. Cannot Benchmark:
    times not implemented at foo.pl line ...
    Rrrrr....

      The Benchmark module works on NT, and will provide useful comparisons.

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: CUFP [id://24145]
Approved by root
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others surveying the Monastery: (4)
As of 2014-10-22 03:39 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    For retirement, I am banking on:










    Results (112 votes), past polls