[Haskell-cafe] In for a penny, in for a pound.

[Bertram Felgenhauer]

Donald Bruce Stewart wrote:
> d:
> > Regarding the Fannkuch Shootout Entry:
> > 
> > If we are willing to specialize flop in the way shown on the wiki,  
> > another 8% can be gained by similarly specializing rotate:
> > 
> > rotate 2 (x1:x2:xs) = x2:x1:xs
> > rotate 3 (x1:x2:x3:xs) = x2:x3:x1:xs
> ...
> 
> Cheers, I've updated the proposed entry on the wiki. It now runs 40%
> faster than Bertram's original entry, and its within 25% of an
> imperative version I wrote yesterday translating from the currently
> fastest C version.

The flop machinery can still be made faster, stealing an idea from the
icc entry (namely, treating the first entry separately):

>>> cut here >>>
flop :: Int -> [Int] -> (Int, [Int])
flop 2  (x2:xs) = (x2, 2:xs)
flop 3  (x2:x3:xs) = (x3, x2:3:xs)
flop 4  (x2:x3:x4:xs) = (x4, x3:x2:4:xs)
flop 5  (x2:x3:x4:x5:xs) = (x5, x4:x3:x2:5:xs)
flop 6  (x2:x3:x4:x5:x6:xs) = (x6, x5:x4:x3:x2:6:xs)
flop 7  (x2:x3:x4:x5:x6:x7:xs) = (x7, x6:x5:x4:x3:x2:7:xs)
flop 8  (x2:x3:x4:x5:x6:x7:x8:xs) = (x8, x7:x6:x5:x4:x3:x2:8:xs)
flop 9  (x2:x3:x4:x5:x6:x7:x8:x9:xs) = (x9, x8:x7:x6:x5:x4:x3:x2:9:xs)
flop 10 (x2:x3:x4:x5:x6:x7:x8:x9:x10:xs) = (x10, x9:x8:x7:x6:x5:x4:x3:x2:10:xs)
flop n xs = rs
  where (rs, ys)       = fl n xs ys
        fl 2 (x:xs) ys = ((x, ys), n:xs)
        fl n (x:xs) ys = fl (n-1) xs (x:ys)

steps :: Int -> [Int] -> Int
steps n    (a:as) = steps' n (a,as)
steps' n (1,_)  = n
steps' n (t,ts) = steps' (n+1) (flop t ts)
<<<

This cuts the running time down from 3.32s to 2.52s on my machine, for
n=10. I've tried generating permutations as pairs in that form but that
hurt performance rather than help.

with kind regards,

Bertram