"be consistent" PerlMonks

comment on

 Need Help??

Some more micro-optimization, proably getting into foolish optimization at this point. Reduced unnecesary copying of variables, performing some calculations used many times outside the loop, added a special check for sequences that start with n.

The line checking for sequences starting with n needs some explanation. It is probably the most obscure.

There are two givens for this algorithm.

• If (\$next == \$length) then (\$level + 1 == \$length).
• \$maxflips DOES NOT get reset between runs.

So: if the first character is n then the minimum \$maxflips{n} is \$maxflips{n-1} + 1. It is impossible to have a sequence to take less than length - 1 flips, so if \$length - 1 is less than \$maxflips{n-1} then it impossible for a sequence that starts with n to have more than \$maxflips{n-1} + 1. Therefore, no need to check them.

Rather than compare \$length to \$maxflips + 1, since \$level == \$length - 1, I save the calculation in the loop and compare \$level to \$maxflips.

```sub fannkuch {
my ( \$copy, \$level, \$split ) = ( @_, 0, 1 );
my ( \$index, \$next ) = ( \$level, \$level + 1 );
my \$length = length(\$copy);

if (\$next == \$length) {
(\$index, \$split) = (\$split - 1, \$level);
substr(\$copy, \$index, 0) = chop(\$copy);
}
do {
if (\$next == \$length) {
unless ( ord(\$copy) == \$length and \$level < \$maxflips )
{
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 ) {
if ( \$flips == \$maxflips) {
push @max_sequence, \$copy;
}
else {
\$maxflips     = \$flips;
@max_sequence = (\$copy);
}
}
}
}
else {
fannkuch( \$copy, \$next, \$split );
}
substr( \$copy, \$index - 1, 2 ) = reverse substr( \$copy, \$index
+ - 1, 2 );

\$split = \$next if \$index == \$split;
} while \$index--;
return \$maxflips;
}

Side by side with your code: It is only about a 4-6% increase, but it is repeatable.

```Your sub                          My sub

Pfannkuchen(1) = 0 for:            Pfannkuchen(1) = 0 for:
1                                  1
0.000351 elapsed seconds.          0.000274 elapsed seconds.

Pfannkuchen(2) = 1 for:            Pfannkuchen(2) = 1 for:
21                                 21
0.000196 elapsed seconds.          0.00016 elapsed seconds.

Pfannkuchen(3) = 2 for:            Pfannkuchen(3) = 2 for:
231                                231
312                                312
0.000275 elapsed seconds.          0.000225 elapsed seconds.

Pfannkuchen(4) = 4 for:            Pfannkuchen(4) = 4 for:
2413                               2413
3142                               3142
0.000348 elapsed seconds.          0.000288 elapsed seconds.

Pfannkuchen(5) = 7 for:            Pfannkuchen(5) = 7 for:
31452                              31452
0.000701 elapsed seconds.          0.000634 elapsed seconds.

Pfannkuchen(6) = 10 for:           Pfannkuchen(6) = 10 for:
365142                             365142
415263                             415263
416523                             416523
456213                             456213
564132                             564132
0.00376 elapsed seconds.           0.003357 elapsed seconds.

Pfannkuchen(7) = 16 for:           Pfannkuchen(7) = 16 for:
3146752                            3146752
4762153                            4762153
0.025629 elapsed seconds.          0.023704 elapsed seconds.

Pfannkuchen(8) = 22 for:           Pfannkuchen(8) = 22 for:
61578324                           61578324
0.226504 elapsed seconds.          0.209445 elapsed seconds.

Pfannkuchen(9) = 30 for:           Pfannkuchen(9) = 30 for:
615972834                          615972834
2.209246 elapsed seconds.          2.088572 elapsed seconds.

Pfannkuchen(10) = 38 for:          Pfannkuchen(10) = 38 for:
59186210473                        59186210473
24.218115 elapsed seconds.         23.077981 elapsed seconds.

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post; it's "PerlMonks-approved HTML":

• 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.

Create A New User
Domain Nodelet?
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others drinking their drinks and smoking their pipes about the Monastery: (1)
As of 2022-11-26 19:07 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?
My favourite new Perl feature (in 2022) ...

Results (40 votes). Check out past polls.

Notices?