[Haskell-beginners] Help with slow algorithm
daniel.is.fischer at web.de
Fri May 14 21:42:49 EDT 2010
On Saturday 15 May 2010 03:13:24, Diego Echeverri wrote:
> Hi guys.
> 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!
> Can anybody point me out of better (faster) ways to improve the code?
> I don't need my code fixed, just suggestions and clues about things to
> Diego Echeverri
One point: Packing a long list is bad. That takes a lot of memory and is
slow, if you create a list, it's going to be faster to use normal String-IO
to output it.
Another point: biggerOrEquals is also too slow. Using the Ord instance for
ByteStrings will be faster. But I think splitting the ByteStrings isn't the
Third point: Use STUArrays and not STArrays if possible (much faster).
More information about the Beginners