This tweaks the implementation rather than the algorithm, which means it comes into the realm of what are usually called micro-optimisations--but it does achieve a near 300% speedup:
#! perl -slw
use strict;
use Time::HiRes qw( gettimeofday tv_interval );
my $maxflips = 0;
my @max_sequence;
for my $num ( 1 .. 10 ) {
my @start_time = gettimeofday();
@max_sequence = ();
print "Pfannkuchen($num) = " . fannkuch( pack 'C*', 1 .. $num ) .
+" for:";
print unpack 'C*', $_ for sort @max_sequence;
my @end_time = gettimeofday();
print tv_interval ( \@start_time, \@end_time ), " elapsed seconds.
+\n";
}
sub fannkuch {
my ( $a, $level ) = ( @_, 0 );
my ( $index, $ok, $copy, ) = ( $level, $level + 1 == length( $a
+), $a );
do {
if ($ok) {
if( ord( $copy ) != 1
and ord( substr( $copy, -1 ) ) != length( $copy )
) {
my $q = $copy;
my ( $k, $flips );
for ( $flips = 0; ( $k = ord( $q ) ) != 1; $flips++ )
+{
substr( $q, 0, $k ) = reverse substr( $q, 0, $k );
}
if ( $flips > $maxflips ) {
$maxflips = $flips;
@max_sequence = ();
}
push @max_sequence, $copy
if ( $maxflips == $flips );
}
}
else {
fannkuch( $copy, 1 + $level );
}
substr( $copy, $index - 1, 2 ) = reverse substr( $copy, $index
+ -1, 2 );
} while $index--;
return $maxflips;
}
__END__
P:\test>513179-3
Pfannkuchen(1) = 0 for:
0.000368 elapsed seconds.
Pfannkuchen(2) = 1 for:
21
0.000206 elapsed seconds.
Pfannkuchen(3) = 2 for:
231
312
0.000298 elapsed seconds.
Pfannkuchen(4) = 4 for:
2413
3142
0.000434 elapsed seconds.
Pfannkuchen(5) = 7 for:
31452
0.001012 elapsed seconds.
Pfannkuchen(6) = 10 for:
365142
415263
416523
456213
564132
0.005817 elapsed seconds.
Pfannkuchen(7) = 16 for:
3146752
4762153
0.039062 elapsed seconds.
Pfannkuchen(8) = 22 for:
61578324
0.339917 elapsed seconds.
Pfannkuchen(9) = 30 for:
615972834
3.313848 elapsed seconds.
Pfannkuchen(10) = 38 for:
59186210473
35.109115 elapsed seconds.
It does limit the algorithm to a maximum of 255 elements (without modifying it to go unicode), but I don't think anyone will be waiting around long enough to notice:)
Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
Lingua non convalesco, consenesco et abolesco. -- Rule 1 has a caveat! -- Who broke the cabal?
"Science is about questioning the status quo. Questioning authority".
In the absence of evidence, opinion is indistinguishable from prejudice.
-
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.