
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

On May 14, 2010, at 21:13 , Diego Echeverri wrote:
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!
http://www.haskell.org/haskellwiki/Performance/GHC is the place to start. -- brandon s. allbery [solaris,freebsd,perl,pugs,haskell] allbery@kf8nh.com system administrator [openafs,heimdal,too many hats] allbery@ece.cmu.edu electrical and computer engineering, carnegie mellon university KF8NH

Thanks Brandon.
BTW... I just noticed I "Fucked up" the last gist.
http://gist.github.com/401924
On Fri, May 14, 2010 at 8:23 PM, Brandon S. Allbery KF8NH
On May 14, 2010, at 21:13 , Diego Echeverri wrote:
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!
http://www.haskell.org/haskellwiki/Performance/GHC is the place to start.
-- brandon s. allbery [solaris,freebsd,perl,pugs,haskell] allbery@kf8nh.com system administrator [openafs,heimdal,too many hats] allbery@ece.cmu.edu electrical and computer engineering, carnegie mellon university KF8NH
-- Att: Diego Echeverri Saldarriaga

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

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

On Saturday 15 May 2010 04:00:06, Diego Echeverri wrote:
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.
You should think a little about avoiding that.
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.
Quite. You only test ByteStrings of equal length, so the Ord instance works 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.
They're also provided by Data.Array.ST, so they are available.
Thanks Again!

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. Regards, Heinrich Apfelmus -- http://apfelmus.nfshost.com

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.
Regards, Heinrich Apfelmus

Daniel Fischer wrote:
Heinrich Apfelmus wrote:
Diego Echeverri wrote:
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.
Oops, my bad. :-$ Regards, Heinrich Apfelmus -- http://apfelmus.nfshost.com
participants (4)
-
Brandon S. Allbery KF8NH
-
Daniel Fischer
-
Diego Echeverri
-
Heinrich Apfelmus