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
_______________________________________________
Haskell-Cafe mailing list
[email protected]
http://www.haskell.org/mailman/listinfo/haskell-cafe
