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: sometimes Haskell isn't what you want (Darren Grant)
2. Question about time consume when calculate prime numbers
(Yi Cheng)
3. Re: Question about time consume when calculate prime numbers
(Darren Grant)
4. Re: Question about time consume when calculate prime numbers
(Lorenzo Bolla)
----------------------------------------------------------------------
Message: 1
Date: Tue, 11 Sep 2012 19:50:41 -0700
From: Darren Grant <[email protected]>
Subject: Re: [Haskell-beginners] sometimes Haskell isn't what you want
To: [email protected]
Message-ID:
<CA+jD6Sija=cu1t15cnc-tiexr0nsvo7uukggsljbtdbez-r...@mail.gmail.com>
Content-Type: text/plain; charset=ISO-8859-1
On Tue, Sep 11, 2012 at 6:03 PM, Michael Carpenter <[email protected]> wrote:
> On 09/11/2012 04:21 PM, Darren Grant wrote:
>>
>> This made me think that it could be much more effective to develop AI in a
>> functional language. There's no way I could do this with Haskell presently
>> as I am still struggling to approach all problems from the FP perspective
>> first, but I do think there is the potential.
>
> There is a lot of potential here in my opinion. The two language families
> that have built their reputations through their use in AI research, Lisp and
> Prolog, share a lot in common with Haskell. AI, along with a lot of the big
> problems out there, seem to always boil down to parallel relationships
> between sets of data in a model rather than sequential object-oriented
> recipes. I would not be surprised if functional languages like Haskell
> supersede many of the imperative languages because of these problem sets.
> Sometimes I think I'm stupid to say that, but then I remember what SQL and
> RDBMS's did for the database world.
The parallel relationships point is interesting. I think sequential
cases could still be helped by FP as well.
I look at things like OpenGL wrappers for Haskell, which successfully
solve immediate interop problems, but then wonder about revisiting
whole approaches by applying new techniques. For instance, what if you
cut out the existing OpenGL API and feed an infinite list into the
device command buffer? It seems like there should be this potential
for cutting latency and improving bandwidth through system
comprehension tools, but that this sophistication has not become
accessible to application programmers.
I know there are plenty of experts hard at work on these problems, but
they are interesting.
> - Michael
>
>
> _______________________________________________
> Beginners mailing list
> [email protected]
> http://www.haskell.org/mailman/listinfo/beginners
------------------------------
Message: 2
Date: Wed, 12 Sep 2012 16:06:16 +0800
From: Yi Cheng <[email protected]>
Subject: [Haskell-beginners] Question about time consume when
calculate prime numbers
To: [email protected]
Message-ID:
<CAEK-Nme-sy=huex6vkbvncjgiw4ujkjp+zhv138_ys6zxxf...@mail.gmail.com>
Content-Type: text/plain; charset="iso-8859-1"
Recently, I'm trying to solve some problems in project euler using haskell.
When it came to problem 10, calculating the sum of all primes below
20000000, I try to write a program which can generate primes.
In my memory Eratosthenes is faster than just whether a number can be
divided by the number less then the square root of it.
Firstly, I wrote the following programs:
module Main where
isPrime x = isPrime' 3 x (round . sqrt. fromIntegral $ x)
isPrime' d target maxd
| d > maxd = True
| mod target d == 0 = False
| otherwise = isPrime' (d + 2) target maxd
main = print $ (sum (filter isPrime [3,5..2000000]) + 2)
And it consume about 11s in my computer.
Then, I tried to figure out how to solve the problem by Eratosthenes, but
failed. Later, I find a program implemented by others, meeting my purpose
and I've used it to solve the problem:
primes :: [Int]
primes = primes' [2..]
primes' :: [Int] -> [Int]
primes' [] = []
primes' (n:ns) = n : primes' (filter (\v -> v `mod` n /= 0) ns)
solve x = sum $ primes' [2..x]
main = print $ solve 2000000
Well, although the code is beautiful, it is slow. Even waiting for a
minute, no answer was printed.
In C version, Eratosthenes is faster than the method implemented in my
earlier code, which only consume 0.3s(the earlier method consume 1.6s).
So I want to know, why Eratosthenes implemented in Haskell is slow than the
ugly code implemented by me.
Could anyone tell me?
Thank you
Yi Cheng
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://www.haskell.org/pipermail/beginners/attachments/20120912/9e22aeec/attachment-0001.htm>
------------------------------
Message: 3
Date: Wed, 12 Sep 2012 02:24:48 -0700
From: Darren Grant <[email protected]>
Subject: Re: [Haskell-beginners] Question about time consume when
calculate prime numbers
To: [email protected]
Message-ID:
<CA+jD6Sif=ZTDhNmsp=pj4c_bqy8envncjugx8ixv7avvf1b...@mail.gmail.com>
Content-Type: text/plain; charset=ISO-8859-1
On Wed, Sep 12, 2012 at 1:06 AM, Yi Cheng <[email protected]> wrote:
> Recently, I'm trying to solve some problems in project euler using haskell.
> When it came to problem 10, calculating the sum of all primes below
> 20000000, I try to write a program which can generate primes.
> In my memory Eratosthenes is faster than just whether a number can be
> divided by the number less then the square root of it.
> Firstly, I wrote the following programs:
>
> module Main where
> isPrime x = isPrime' 3 x (round . sqrt. fromIntegral $ x)
> isPrime' d target maxd
> | d > maxd = True
> | mod target d == 0 = False
> | otherwise = isPrime' (d + 2) target maxd
>
> main = print $ (sum (filter isPrime [3,5..2000000]) + 2)
>
> And it consume about 11s in my computer.
> Then, I tried to figure out how to solve the problem by Eratosthenes, but
> failed. Later, I find a program implemented by others, meeting my purpose
> and I've used it to solve the problem:
>
> primes :: [Int]
> primes = primes' [2..]
>
> primes' :: [Int] -> [Int]
> primes' [] = []
> primes' (n:ns) = n : primes' (filter (\v -> v `mod` n /= 0) ns)
>
> solve x = sum $ primes' [2..x]
>
> main = print $ solve 2000000
>
> Well, although the code is beautiful, it is slow. Even waiting for a minute,
> no answer was printed.
>
> In C version, Eratosthenes is faster than the method implemented in my
> earlier code, which only consume 0.3s(the earlier method consume 1.6s).
>
> So I want to know, why Eratosthenes implemented in Haskell is slow than the
> ugly code implemented by me.
> Could anyone tell me?
>
>
> Thank you
> Yi Cheng
>
> _______________________________________________
> Beginners mailing list
> [email protected]
> http://www.haskell.org/mailman/listinfo/beginners
>
I attempted this problem as well and noticed similar results. I am
also interested in the performance characteristics of Haskell
solutions and their explanations.
Cheers,
Darren
------------------------------
Message: 4
Date: Wed, 12 Sep 2012 10:26:46 +0100
From: Lorenzo Bolla <[email protected]>
Subject: Re: [Haskell-beginners] Question about time consume when
calculate prime numbers
To: Yi Cheng <[email protected]>
Cc: [email protected]
Message-ID:
<cadjgtrw0eolg-s0rdaem03qhwe1zasxwsg0a353vv790c9p...@mail.gmail.com>
Content-Type: text/plain; charset="utf-8"
On Wed, Sep 12, 2012 at 9:06 AM, Yi Cheng <[email protected]> wrote:
> Recently, I'm trying to solve some problems in project euler using
> haskell. When it came to problem 10, calculating the sum of all primes
> below 20000000, I try to write a program which can generate primes.
> In my memory Eratosthenes is faster than just whether a number can be
> divided by the number less then the square root of it.
> Firstly, I wrote the following programs:
>
> module Main where
> isPrime x = isPrime' 3 x (round . sqrt. fromIntegral $ x)
> isPrime' d target maxd
> | d > maxd = True
> | mod target d == 0 = False
> | otherwise = isPrime' (d + 2) target maxd
>
> main = print $ (sum (filter isPrime [3,5..2000000]) + 2)
>
> And it consume about 11s in my computer.
> Then, I tried to figure out how to solve the problem by Eratosthenes, but
> failed. Later, I find a program implemented by others, meeting my purpose
> and I've used it to solve the problem:
>
> primes :: [Int]
> primes = primes' [2..]
>
> primes' :: [Int] -> [Int]
> primes' [] = []
> primes' (n:ns) = n : primes' (filter (\v -> v `mod` n /= 0) ns)
>
> solve x = sum $ primes' [2..x]
>
> main = print $ solve 2000000
>
> Well, although the code is beautiful, it is slow. Even waiting for a
> minute, no answer was printed.
>
> In C version, Eratosthenes is faster than the method implemented in my
> earlier code, which only consume 0.3s(the earlier method consume 1.6s).
>
> So I want to know, why Eratosthenes implemented in Haskell is slow than
> the ugly code implemented by me.
> Could anyone tell me?
>
>
Eratosthenes's complexity is O(n^2) (both space and time), whereas the
"ugly" one has a sub-quadratic running complexity and linear in space.
Try to profile them:
$> ghc -O2 --make -prof -auto-all <filename>
$> ./primes +RTS -p -hc
$> hp2ps primes.hp
You'll see that most of the time is spent allocating space which is never
released.
You could play a bit with strictness, but the main problem is the awful
complexity of the algorithm.
hth,
L.
> Thank you
> Yi Cheng
>
> _______________________________________________
> Beginners mailing list
> [email protected]
> http://www.haskell.org/mailman/listinfo/beginners
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://www.haskell.org/pipermail/beginners/attachments/20120912/c0ef757b/attachment-0001.htm>
------------------------------
_______________________________________________
Beginners mailing list
[email protected]
http://www.haskell.org/mailman/listinfo/beginners
End of Beginners Digest, Vol 51, Issue 18
*****************************************
