Syntactic Confectionery Delight PerlMonks

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

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

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.

Replies are listed 'Best First'.
Re^3: Speed/Efficiency tweaks for a fannkuch benchmark script?
by thundergnat (Deacon) on Dec 01, 2005 at 19:20 UTC

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?

Ah. Yes, ok I see your point now. I might be able to make a case for n being in the first position being safe to ignore, but how to prove when 1 is in the last...

Create A New User
Domain Nodelet?
Node Status?
node history
Node Type: note [id://513363]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others cooling their heels in the Monastery: (7)
As of 2022-08-08 20:36 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?

No recent polls found

Notices?