[Haskell-beginners] Help with slow algorithm

[Diego Echeverri]

Hi Daniel. Thanks for your answer.

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

The thing is that later I do some operations with it (solve). just by
changing to ByteString
everything got faster.


> 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
> best way.

The Ord instance of ByteStrings is lexicographic. This way:

B.pack "1111"  > B.pack "112" ==> False

Although given the fact that both strings would be the same length,
the Ord instance may work just fine.

> Third point: Use STUArrays and not STArrays if possible (much faster).

Not sure if those are available in the Online Judge. I'll try it.

Thanks Again!


On Fri, May 14, 2010 at 8:42 PM, Daniel Fischer
<daniel.is.fischer at web.de> wrote:
> 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
>> try.
>>
>> Thanks!
>> 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
> best way.
>
> Third point: Use STUArrays and not STArrays if possible (much faster).
>



-- 
Att: Diego Echeverri Saldarriaga