Send Beginners mailing list submissions to
[email protected]
To subscribe or unsubscribe via the World Wide Web, visit
http://www.haskell.org/mailman/listinfo/beginners
or, via email, send a message with subject or body 'help' to
[email protected]
You can reach the person managing the list at
[email protected]
When replying, please edit your Subject line so it is more specific
than "Re: Contents of Beginners digest..."
Today's Topics:
1. Re: Help with slow algorithm (Daniel Fischer)
2. Re: Help with slow algorithm (Diego Echeverri)
3. Re: Help with slow algorithm (Daniel Fischer)
4. Re: Help with slow algorithm (Heinrich Apfelmus)
5. Re: Re: Help with slow algorithm (Daniel Fischer)
----------------------------------------------------------------------
Message: 1
Date: Sat, 15 May 2010 03:42:49 +0200
From: Daniel Fischer <[email protected]>
Subject: Re: [Haskell-beginners] Help with slow algorithm
To: [email protected]
Cc: Diego Echeverri <[email protected]>
Message-ID: <[email protected]>
Content-Type: text/plain; charset="iso-8859-1"
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).
------------------------------
Message: 2
Date: Fri, 14 May 2010 21:00:06 -0500
From: Diego Echeverri <[email protected]>
Subject: Re: [Haskell-beginners] Help with slow algorithm
To: Daniel Fischer <[email protected]>
Cc: [email protected]
Message-ID:
<[email protected]>
Content-Type: text/plain; charset=ISO-8859-1
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
<[email protected]> 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
------------------------------
Message: 3
Date: Sat, 15 May 2010 04:16:49 +0200
From: Daniel Fischer <[email protected]>
Subject: Re: [Haskell-beginners] Help with slow algorithm
To: Diego Echeverri <[email protected]>
Cc: [email protected]
Message-ID: <[email protected]>
Content-Type: text/plain; charset="iso-8859-1"
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!
>
>
------------------------------
Message: 4
Date: Sat, 15 May 2010 10:29:12 +0200
From: Heinrich Apfelmus <[email protected]>
Subject: [Haskell-beginners] Re: Help with slow algorithm
To: [email protected]
Message-ID: <[email protected]>
Content-Type: text/plain; charset=UTF-8
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
------------------------------
Message: 5
Date: Sat, 15 May 2010 11:26:14 +0200
From: Daniel Fischer <[email protected]>
Subject: Re: [Haskell-beginners] Re: Help with slow algorithm
To: [email protected]
Message-ID: <[email protected]>
Content-Type: text/plain; charset="utf-8"
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
>
------------------------------
_______________________________________________
Beginners mailing list
[email protected]
http://www.haskell.org/mailman/listinfo/beginners
End of Beginners Digest, Vol 23, Issue 21
*****************************************
