Am Freitag 27 November 2009 20:41:37 schrieb vishnu:
Ive just started learning haskell pretty recently and Ive been trying to solve some online contest problems as part of this exercise. However, Ive been having almost no success. For various reasons my answers almost always are too slow. I recently stumbled across this link which was quite useful http://www.haskell.org/haskellwiki/SPOJ. This helped me speed up some of my programs where input was slowing me down.
But being a noob, to a large extent I don't even know why my programs are slow sometimes or how to tell what makes them slow. I've been attempting problems from www.codechef.com (which uses SPOJ) in actuality. Because I have an admin account I can actually compare my solution against others there (which are almost always in C/C++ or Java) to try and figure out if Im missing a trick. Recently the problem I picked up was http://www.codechef.com/problems/DDILEMMA/ and I worked through solutions that just don't seem to be fast enough. I looked at successful submissions in C++ and JAVA which seem to do mostly what I'm doing (ofcourse there are differences because those are imperative languages and I might be misunderstanding things.). I've got my program, test input that I generated, cost center analysis all up on this page. http://moonpatio.com/fastcgi/hpaste.fcgi/view?id=5120#a5137
I've been getting some significant help from the #haskell channel but unfortunately this hasn't helped me break the barrier I need to. So I was wondering if someone would be kind enough to help me understand the profiler output and help me understand how to improve performance in cases like this
Bad news first. a) According to codechef, you must also consider digits. b) Your distance function is wrong. With idx i j = (i+1)*(j+1) - 1, you write to the same position several times, resulting in garbage. You should use idx i j = i*(n+1) + j. Unfortunately, that slows things down. Now some good news. a) Since the substitution cost for a pair of letters doesn't depend on the strings, you can make a universal substitution-cost matrix (UArray (Char,Char) Int) and read the cost off that. Doesn't work wonders, but speeds things up a little. b) If the lengths of the two strings differs by more than 2, the Levenshtein distance is at least 3, so you needn't calculate. This was probably your intention, but laziness doesn't quite work the way you thought (if I interpreted your intentions correctly). With distance orig new = memf m n where m = snd $ bounds orig n = snd $ bounds new ... , if |m - n| > 2, the thunks for the array entries must still be written - although most needn't be evaluated in this case, that still takes a lot of time. Make it distance orig new = f m n and no thunks need be written at all in this case. Cuts down running time by nearly half :) I think you could speed it up significantly by calculating the distance more lazily. The profiling output is pretty straightforward. You have two functions that take up more or less all the time, one is substitutionCost, the other distance. The former is comparatively benign, the letterHash should be calculated only once and kept alive through the entire run, but you use a Map.lookup and `elem` (plus a branch); with 26 letters, a lookup takes on average about 4 comparisons, then in general two comparisons for `elem`. An array-lookup will be much faster. The latter uses really a lot of time. As said before, a large part of it is because you're not lazy enough. Still, it is a complicated calculation, so it remains a time-consuming task. For more detailed information which parts of it take the most time, add further cost centres ({-# SCC "thing" #-} annotations). Be aware however, that profiling often rules out optimisations and thus changes the run-time behaviour of your code.
thanks