[Haskell-cafe] haskell in online contests

[Daniel Fischer]

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