Help with improving a program - Beginners - Haskell.org

newer
Simple Continuation question

Help with improving a program

older
foldM efficiency

Marcelo Lacerda

10 Jul 2014 10 Jul '14

2:02 a.m.

Hi I'm just starting with haskell and want some help with it. I tried to solve the Store Credit[1] problem from google code jam just to practice, the result was a slow code[2] that I find hard to read. Can you guys give me some directions on how to improve it? [1] - https://code.google.com/codejam/contest/351101/dashboard#s=p0 [2] - http://pastebin.com/jNGxGP5H

Attachments:

signature.asc (application/pgp-signature — 897 bytes)

Reply

Sign in to reply online Use email software

Show replies by date

Frerich Raabe

10 Jul 10 Jul

8:52 a.m.

On 2014-07-10 04:02, Marcelo Lacerda wrote:

Hi I'm just starting with haskell and want some help with it.

I tried to solve the Store Credit[1] problem from google code jam just to practice, the result was a slow code[2] that I find hard to read.

Can you guys give me some directions on how to improve it?

Accessing list elements via (!!) is rather inefficent for larger lists (it's an O(n) operation), so try to avoid that. Also, the 'comb' function won't scale very well for your particular use case. Since you only want to get all pairs, something like pairs :: [a] -> [(a, a)] pairs [] = [] pairs [x] = [] pairs (x:xs) = map (\e -> (x, e)) xs ++ pairs xs ...would do, performing a lot better than 'comb 2'. The repeated usage of (++) isn't exactly efficient either though but I couldn't think of a way to avoid that while writing this mail. :-) -- Frerich Raabe - raabe@froglogic.com www.froglogic.com - Multi-Platform GUI Testing

Reply

Sign in to reply online Use email software

Francesco Ariis

9:24 a.m.

On Wed, Jul 09, 2014 at 11:02:14PM -0300, Marcelo Lacerda wrote:

Hi I'm just starting with haskell and want some help with it.

I tried to solve the Store Credit[1] problem from google code jam just to practice, the result was a slow code[2] that I find hard to read.

Can you guys give me some directions on how to improve it?

[1] - https://code.google.com/codejam/contest/351101/dashboard#s=p0 [2] - http://pastebin.com/jNGxGP5H

Don't know about efficiency, but I never liked (!!). Maybe computing all pairs+positions in advance using |zip| would be a little better? I attach my .hs; code is quite caveman-Haskell, but hopefully the idea is clear -F

Reply

Sign in to reply online Use email software

Frerich Raabe

9:35 a.m.

On 2014-07-10 11:24, Francesco Ariis wrote:

On Wed, Jul 09, 2014 at 11:02:14PM -0300, Marcelo Lacerda wrote:

...
Hi I'm just starting with haskell and want some help with it.

I tried to solve the Store Credit[1] problem from google code jam just to practice, the result was a slow code[2] that I find hard to read.

Can you guys give me some directions on how to improve it?

[1] - https://code.google.com/codejam/contest/351101/dashboard#s=p0 [2] - http://pastebin.com/jNGxGP5H

Don't know about efficiency, but I never liked (!!). Maybe computing all pairs+positions in advance using |zip| would be a little better?

Yeah, that's what I went for as well. I'm attaching my solution for comparison to this mail. -- Frerich Raabe - raabe@froglogic.com www.froglogic.com - Multi-Platform GUI Testing

Reply

Sign in to reply online Use email software

Florian Gillard

1:24 p.m.

I don't know if this is any good but here is my attempt to solve this. I used comprehensions. It seems to be working fine with the test files :) On Thu, Jul 10, 2014 at 11:35 AM, Frerich Raabe wrote:

On 2014-07-10 11:24, Francesco Ariis wrote:

...
On Wed, Jul 09, 2014 at 11:02:14PM -0300, Marcelo Lacerda wrote:

...
Hi I'm just starting with haskell and want some help with it.

I tried to solve the Store Credit[1] problem from google code jam just to practice, the result was a slow code[2] that I find hard to read.

Can you guys give me some directions on how to improve it?

[1] - https://code.google.com/codejam/contest/351101/dashboard#s=p0 [2] - http://pastebin.com/jNGxGP5H

Don't know about efficiency, but I never liked (!!). Maybe computing all pairs+positions in advance using |zip| would be a little better?

Yeah, that's what I went for as well. I'm attaching my solution for comparison to this mail.

-- Frerich Raabe - raabe@froglogic.com www.froglogic.com - Multi-Platform GUI Testing

_______________________________________________ Beginners mailing list Beginners@haskell.org http://www.haskell.org/mailman/listinfo/beginners

Reply

Sign in to reply online Use email software

Marcelo Lacerda

12 Jul 12 Jul

12:13 a.m.

Thanks for all the replies, I really liked Florian's answer, even though, if I were to adopt that style, I think the haskell gods would shunne me for using mixing too much pure and impure code. On 07/10/2014 10:24 AM, Florian Gillard wrote:

I don't know if this is any good but here is my attempt to solve this.

I used comprehensions.

It seems to be working fine with the test files :)

On Thu, Jul 10, 2014 at 11:35 AM, Frerich Raabe wrote:

...
On 2014-07-10 11:24, Francesco Ariis wrote:

...
On Wed, Jul 09, 2014 at 11:02:14PM -0300, Marcelo Lacerda wrote:

...
Hi I'm just starting with haskell and want some help with it.

I tried to solve the Store Credit[1] problem from google code jam just to practice, the result was a slow code[2] that I find hard to read.

Can you guys give me some directions on how to improve it?

[1] - https://code.google.com/codejam/contest/351101/dashboard#s=p0 [2] - http://pastebin.com/jNGxGP5H

Don't know about efficiency, but I never liked (!!). Maybe computing all pairs+positions in advance using |zip| would be a little better?

Yeah, that's what I went for as well. I'm attaching my solution for comparison to this mail.

-- Frerich Raabe - raabe@froglogic.com www.froglogic.com - Multi-Platform GUI Testing

_______________________________________________ Beginners mailing list Beginners@haskell.org http://www.haskell.org/mailman/listinfo/beginners

_______________________________________________ Beginners mailing list Beginners@haskell.org http://www.haskell.org/mailman/listinfo/beginners

Reply

Sign in to reply online Use email software

4010

Age (days ago)

4012

Last active (days ago)

Download

5 comments

4 participants

tags

participants (4)

Florian Gillard
Francesco Ariis
Frerich Raabe
Marcelo Lacerda