[Haskell-beginners] Re: Help with slow algorithm
daniel.is.fischer at web.de
Sat May 15 05:26:14 EDT 2010
On Saturday 15 May 2010 10:29:12, Heinrich Apfelmus wrote:
> Diego Echeverri wrote:
> > I've been playing with https://www.spoj.pl/ to get better with
> > Haskell. I'm trying to do: https://www.spoj.pl/problems/PALIN/
> > Basically given a number k, you have to find a number bigger than k
> > that is palindrome. The thing is that k can be 1000000 digits long.
> > I have learnt a bunch of things doing this exercise but I'm still
> > getting time-limit exception.
> > Here's the code: http://gist.github.com/401880
> > I believe that the bottleneck is in the addOne function (Specially in
> > the case where you have a bunch of nines). I have rewritten it to use
> > STArray but isn't fast enough.
> > doing: addOne $ B.replicate 500000 'a' takes too much time!
> Are you sure that you are using a fast algorithm? For instance, starting
> with k and counting up until you reach a palindrome is definitely not a
> good idea; you need to do something cleverer.
Deceived by a name :)
He did something cleverer. His algorithm is good, just the implementation
leaves much room for improvement.
> Heinrich Apfelmus
More information about the Beginners