Beefy Boxes and Bandwidth Generously Provided by pair Networks
Clear questions and runnable code
get the best and fastest answer
 
PerlMonks  

Re: Speed/Efficiency tweaks for a fannkuch benchmark script?

by robin (Chaplain)
on Dec 01, 2005 at 15:27 UTC ( #513303=note: print w/ replies, xml ) Need Help??


in reply to Speed/Efficiency tweaks for a fannkuch benchmark script?

Taking your clever precheck a stage further gives a 50%-ish speed improvement on my iBook:
(Update: On a faster Linux PC the improvement is much less pronounced: only about 810%.)

use List::Util qw( min max ); sub fannkuch { my ( $aref, $level ) = ( @_, 0 ); my ( $index, $copy, $ok ) = ( $level, [@$aref], $level + 1 == @$ar +ef ); do { if ($ok) { if (max(@$copy[0..($copy->[0] - 1)]) != $copy->[0] && min(@$copy[($copy->[-1] - 1)..$#$copy]) != $copy->[-1 +]) { my @q = @$copy; my ( $k, $flips ); for ( $flips = 0 ; ( $k = $q[0] ) != 1 ; $flips++ ) { @q[ 0 .. $k-1 ] = reverse @q[ 0 .. $k-1 ]; } if ( $flips > $maxflips ) { $maxflips = $flips; @max_sequence = (); } push @max_sequence, join '', @$copy, "\n" if ( $maxflips == $flips ); } } else { fannkuch( $copy, 1 + $level ); } @$copy[ $index - 1, $index ] = @$copy[ $index, $index - 1 ] if $index != 0; } while $index-- > 0; return $maxflips; }
Incidentally, I tried changing the code to use Algorithm::FastPermute (which implements the same permutation algorithm in C) and the runtime actually increased. I don't know why that's happening. It may be an unfortunate side-effect of the stability improvements in my latest version of A::FP, or it may be something else entirely. Update: no, it's nothing to do with the recent changes. I get the same result using an old version too.


Comment on Re: Speed/Efficiency tweaks for a fannkuch benchmark script?
Download Code
Re^2: Speed/Efficiency tweaks for a fannkuch benchmark script?
by thundergnat (Deacon) on Dec 01, 2005 at 16:43 UTC

    Ah. Very clever. An obvious extention of the prechecks I was doing, but I did't find a way to implement them without adding more overhead than I was saving.

    Nice!

Re^2: Speed/Efficiency tweaks for a fannkuch benchmark script?
by robin (Chaplain) on Dec 01, 2005 at 17:46 UTC
    Hmm, the only problem with this is that my optimised routine gives the wrong answer. The bug is that, if the largest element is at the beginning or the smallest is at the end of the list, my test will skip it when it shouldn't. So the condition really needs to be something like:
    my ($n, $first, $last) = ($#$copy, @$copy[0,-1]); if ( ( $first == $n+1 || $first != max(@$copy[0..($first - + 1)]) ) && ( $last == 1 || $last != min(@$copy[($last - 1)..$n]) + )) { ...
    Now it's a little faster than the original on my laptop, and a little slower on the Linux box.

      Yes, but... The only case where it would yeild a wrong answer is when $n == 2. So just check for that.

      if ((max( @$copy[ 0 .. ( $copy->[0] - 1 ) ] ) != $copy->[0] && min( @$copy[ ( $copy->[-1] - 1 ) .. $#$copy ] ) != $copy->[-1]) || @$copy == 2 ) {

      Or am I missing something?

        It also fails for $n == 3, where the answers should be 231 and 312, each of which take 2 steps.

        So just do || @$copy <= 3, one might say; and indeed that would give the right answers. But how do we know it would give the right answers, except by comparing the output with the unoptimized version? Is it possible to prove that this is safe?

Log In?
Username:
Password:

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

How do I use this? | Other CB clients
Other Users?
Others taking refuge in the Monastery: (11)
As of 2014-08-22 08:50 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    The best computer themed movie is:











    Results (151 votes), past polls