Re: The Knight's Tour: solutions please
I've created a wiki page, http://haskell.org/haskellwiki/The_Knights_Tour I note the LogicT version is the shortest so far. -- Don
Probably noob question. I was looking into the first solution in the page and tried to replace sortOn f = map snd . sortBy (comparing fst) . map (f &&& id) for sortOn' f = sortBy (comparing fst) The first one was much faster? Why? Thanks! Diego
On Mon, 2008-12-01 at 22:48 +0100, Diego Echeverri wrote:
I've created a wiki page, http://haskell.org/haskellwiki/The_Knights_Tour I note the LogicT version is the shortest so far. -- Don
Probably noob question. I was looking into the first solution in the page and tried to replace
sortOn f = map snd . sortBy (comparing fst) . map (f &&& id) for sortOn' f = sortBy (comparing fst)
Presumably you mean: sortOn' f = sortBy (comparing (f . fst))
The first one was much faster? Why?
Caching. It caches all the calls to f. So f gets called once per-element in the input list rather than every time the sort needs to do a comparison. The number of comparisons sort does is proportional to n * log n. So that's a log factor more calls of f. Presumably f is reasonably expensive in this case, enough to offset the extra book-keeping needed to cache all the calls. Duncan
participants (2)
-
Diego Echeverri -
Duncan Coutts