[Haskell-cafe] Space efficiency problem

Adrian Victor CRISCIU acrisciu at catedra.chfiz.pub.ro
Tue Nov 9 16:49:23 EST 2004


This may be silly, but I tried to code a simmulated annealing method to solve the travelling salesman prblem, by adapting the algorithm described in "Numerical Recipes in C". The problem is that there are so many iterations, that the program gets killed (kill -9) by the system. I use the State monad to code the optimisation algorithm, and a simple configurations generator for generating the each path. After profiling with -hc, the heap profile shows that the top-level function of the algorithm uses about 40Mb of heap space. 
How can I improve this awful program?

The optimisation algorithm is coded as

simmann = untilM theEnd refine path0

untilM :: (Monad m) => (m a -> m Bool) -> (a -> m a) -> m a -> m a
untilM p f m0 = do
	isOver <- p m0
	if isOver then m0
		  else untilM p f (m0 >>= f)

theEnd tests if the current temperature has reached the lower limit, and refine produces a new path via a random modification on the current one.

What can I do to get this running? It seems to eat up all the available space. I coded this previously in C, with destructive update of the state and path, but in Haskell, with recursion, this seems to be hoplessly inefficient.

I use ghc-6.2.1 on a Slackware box based on kernel 2.4.18 with glibc 2.2.5

Thanks for your time!


More information about the Haskell-Cafe mailing list