Daniel Fischer daniel.is.fischer at web.de
Fri Nov 27 20:04:31 EST 2009

```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
> 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
> 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

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