"Mark Engelberg" <[EMAIL PROTECTED]> wrote,
> After reading about the stellar performance of the Haskell entries in the
> ICFP contest, I started reading the Haskell documentation to learn more
> about the language. My knowledge of functional programming languages
> primarily comes from Scheme.
[...]
> This seems like a perfect opportunity to exploit Haskell's list generation
> and lazy evaluation capabilities. The crux of the problem is to find a
> concise way of describing the list of all permutations of digits. I don't
> want to embarrass myself by posting my first attempt here, but I'll show you
> my second, slightly-less naive approach to writing this program:
>
[Haskell program deleted]
>
> Impressively concise, but how does it run? Well, I loaded it into the HUGS
> interpreter; typed answer, and after a couple minutes, the answer printed
> out. Not too bad, but how would this compare to a
> solution in C++?
>
[C++ program deleted]
>
> It's a little longer, but not unreasonably so. How does it run? Well,
> running it inside the debugger, it generated the correct answer within a
> couple of seconds.
>
> This is a huge difference, and makes Haskell look incredibly slow by
> comparison. The speed difference in this case is well worth the extra few
> lines of code.
After modifying you program a bit:
import List
expand a b c d e f = f + e*10 + d*100 + c*1000 + b*10000 + a*100000
xs :: [Int]
xs = [0,1..9] -- all the digits
answer =
head [ [t,h,i,r,y,w,e,l,v,n]
| t<-xs,
let es = delete t xs, e<-es,
let hs = delete e es, h<-hs,
let is = delete h hs, i<-is,
let rs = delete i is, r<-rs,
let ys = delete r rs, y<-ys,
let ws = delete y ys, w<-ws,
let ls = delete w ws, l<-ls,
let vs = delete l ls, v<-vs,
let ns = delete v vs, n<-ns,
expand t h i r t y + 5 * expand t w e l v e == expand n i n e t y]
I get
C++ (your program) : 0.31s
Haskell (above prgm): 2.63s
(This was on a 300MHz Celeron running Linux. C++ compiled
with egcs-1.1.2 and -O3.)
Still slower, but not too bad (given that C++ probably uses
inplace array manipulations). So, why the difference to
your results:
* I used a Haskell _compiler_, not the Hugs interpreter (I
used GHC 4.04pl1 and compiled with -O2).
* I added a type annotation to the definition of `xs' -
Haskell uses overloading on numerals and in your case
conservatively assumed that you want to calculate with
_arbitrary_precision_ integer arithmetic.
* I moved redundant computations out of the inner `loops'.
The farther a generator to the right, the further inside a
set of nested `loops' (actually recursions) it is. For
example, your `n<-xs\\[t,e,h,i,r,y,w,l,v]' generator
strips `t', `e', `h', `i', `r', `y', `w', and `l' from the
list although this was already done in the enclosing
generator (the one to its left).
If you get to know Haskell a little, the above are fairly
straight forward optimisations (ie, nothing surprising).
Cheers,
Manuel
