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)
-
Are you posting in the right place? Check out Where do I post X? to know for sure.
-
Posts may use any of the Perl Monks Approved HTML tags. Currently these include the following:
<code> <a> <b> <big>
<blockquote> <br /> <dd>
<dl> <dt> <em> <font>
<h1> <h2> <h3> <h4>
<h5> <h6> <hr /> <i>
<li> <nbsp> <ol> <p>
<small> <strike> <strong>
<sub> <sup> <table>
<td> <th> <tr> <tt>
<u> <ul>
-
Snippets of code should be wrapped in
<code> tags not
<pre> tags. In fact, <pre>
tags should generally be avoided. If they must
be used, extreme care should be
taken to ensure that their contents do not
have long lines (<70 chars), in order to prevent
horizontal scrolling (and possible janitor
intervention).
-
Want more info? How to link
or How to display code and escape characters
are good places to start.
|