Send Beginners mailing list submissions to
[email protected]
To subscribe or unsubscribe via the World Wide Web, visit
http://mail.haskell.org/cgi-bin/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. parallel map/filter (Csaba Marosi)
2. Haskell Bin Tree Cellular Automata. (Sourabh)
3. Re: Haskell Bin Tree Cellular Automata. (Henk-Jan van Tuyl)
4. Re: Haskell Bin Tree Cellular Automata. (Sourabh)
5. Re: Haskell Bin Tree Cellular Automata. (Henk-Jan van Tuyl)
----------------------------------------------------------------------
Message: 1
Date: Thu, 4 Jun 2015 19:16:37 +0000
From: Csaba Marosi <[email protected]>
To: [email protected]
Subject: [Haskell-beginners] parallel map/filter
Message-ID:
<caej73sloa4jxz8sexovu9+yqzrvry_+4vf+sxv1rcvb-xcr...@mail.gmail.com>
Content-Type: text/plain; charset=UTF-8
Hi,
I'm trying to use parallelism in Haskell, parMap in particular.
My code is essentially this:
import Control.Parallel.Strategies
slow :: String -> (String, [Int])
fast x = (x, [0..255])
main :: IO ()
main = do
content <- readFile "4.txt" --a 327 lines long file
print $ parMap rpar slow $ lines content
For the full/compiling code, see:
https://github.com/csmarosi/cryptopals/blob/bf1ca794f897858f9008fb8740a1c3ef1997482b/s01p04.hs
What do I miss here? The code should be trivial to run on multiple
cores, but it seem to use only a single CPU core, i.e.
$ ghc -O2 -v0 -threaded --make s01p04.hs
slow gives:
$ time ./s01p04 +RTS -N2 | wc
1 1 64028
real 0m8.903s
user 0m7.888s
sys 0m1.792s
whereas fast is:
$ time ./s01p04 +RTS -N2 | wc
1 1 320787
real 0m0.016s
user 0m0.012s
sys 0m0.012s
Bonus question: is there a parallel filter?
I use Debian sid packages, ghc version 7.8.4
Some multi-threading seems to go on, since without -N2, the sys time
is below 0.1s.
BTW, the slow code use ~300K heap according to valgrind.
Thanks,
Csabi
------------------------------
Message: 2
Date: Thu, 4 Jun 2015 15:50:25 -0700
From: Sourabh <[email protected]>
To: [email protected]
Subject: [Haskell-beginners] Haskell Bin Tree Cellular Automata.
Message-ID:
<CAK0HM3=tPgPDznMrgw7StUTUrst79yun75=xyrv1-ig7bfb...@mail.gmail.com>
Content-Type: text/plain; charset="utf-8"
Hello all!
I am trying to solve the following problem on HackerRank. It asks us to
compute a cellular automata based on a binary tree:
https://www.hackerrank.com/challenges/the-tree-of-life
I have got 9/10 test cases passing. The last test case times out on the
server. But I was able to download the input and expected output, and
verify that it is functionally correct. The problem is that the big input
is supposed to run within 5 sec, and mine is taking 145 seconds, LOL!
Here was my first implementation:
https://github.com/cbrghostrider/Hacking/blob/master/HackerRank/FunctionalProgramming/Recursion/cellular_automata_functionally_correct.hs
I figured out that I am constantly re-computing the trees, and decided to
try and memoize the results. Here is my memoization attempt:
https://github.com/cbrghostrider/Hacking/blob/master/HackerRank/FunctionalProgramming/Recursion/cellular_automata_memoize_attempt.hs
Basically I have changed the simulateCellularAutomata function, which
computed the new trees, into a list (automataTrees - line 60). I was
expecting the results to be memoized, but the runtime is unchanged.
I was wondering if someone can help me figure out what I'm doing wrong with
the memoization. Or suggest other ways to memoize this perhaps?
--
Thanks much!
SSJ
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://mail.haskell.org/pipermail/beginners/attachments/20150604/92291c12/attachment-0001.html>
------------------------------
Message: 3
Date: Fri, 05 Jun 2015 01:28:30 +0200
From: "Henk-Jan van Tuyl" <[email protected]>
To: [email protected], Sourabh <[email protected]>
Subject: Re: [Haskell-beginners] Haskell Bin Tree Cellular Automata.
Message-ID: <op.xzqbhscypz0j5l@alquantor>
Content-Type: text/plain; charset=iso-8859-15; format=flowed;
delsp=yes
On Fri, 05 Jun 2015 00:50:25 +0200, Sourabh <[email protected]>
wrote:
> I figured out that I am constantly re-computing the trees, and decided to
> try and memoize the results. Here is my memoization attempt:
> https://github.com/cbrghostrider/Hacking/blob/master/HackerRank/FunctionalProgramming/Recursion/cellular_automata_memoize_attempt.hs
>
> Basically I have changed the simulateCellularAutomata function, which
> computed the new trees, into a list (automataTrees - line 60). I was
> expecting the results to be memoized, but the runtime is unchanged.
At a glance: maybe if you change the line
automataTrees starttree rule = (starttree) : [ simulateAutomataStep
Nothing rule ((automataTrees starttree rule) !! (n-1)) | n <- [1..]]
to
automataTrees starttree rule = iterate (simulateAutomataStep Nothing
rule) starttree
it will run faster. The function 'iterate' can be found in Prelude and
Data.List.
Regards,
Henk-Jan van Tuyl
--
Folding@home
What if you could share your unused computer power to help find a cure? In
just 5 minutes you can join the world's biggest networked computer and get
us closer sooner. Watch the video.
http://folding.stanford.edu/
http://Van.Tuyl.eu/
http://members.chello.nl/hjgtuyl/tourdemonad.html
Haskell programming
--
------------------------------
Message: 4
Date: Thu, 4 Jun 2015 16:31:07 -0700
From: Sourabh <[email protected]>
To: Henk-Jan van Tuyl <[email protected]>
Cc: [email protected]
Subject: Re: [Haskell-beginners] Haskell Bin Tree Cellular Automata.
Message-ID:
<cak0hm3k4orvedmvq+3z36xdnk3mffcozpwrj05u1y9+55u7...@mail.gmail.com>
Content-Type: text/plain; charset="utf-8"
Wow, it runs in 0.44 seconds now. This is incredible! Can you explain what
just happened here?
On Thu, Jun 4, 2015 at 4:28 PM, Henk-Jan van Tuyl <[email protected]> wrote:
> On Fri, 05 Jun 2015 00:50:25 +0200, Sourabh <[email protected]>
> wrote:
>
> I figured out that I am constantly re-computing the trees, and decided to
>> try and memoize the results. Here is my memoization attempt:
>>
>> https://github.com/cbrghostrider/Hacking/blob/master/HackerRank/FunctionalProgramming/Recursion/cellular_automata_memoize_attempt.hs
>>
>> Basically I have changed the simulateCellularAutomata function, which
>> computed the new trees, into a list (automataTrees - line 60). I was
>> expecting the results to be memoized, but the runtime is unchanged.
>>
>
> At a glance: maybe if you change the line
> automataTrees starttree rule = (starttree) : [ simulateAutomataStep
> Nothing rule ((automataTrees starttree rule) !! (n-1)) | n <- [1..]]
> to
> automataTrees starttree rule = iterate (simulateAutomataStep Nothing
> rule) starttree
> it will run faster. The function 'iterate' can be found in Prelude and
> Data.List.
>
> Regards,
> Henk-Jan van Tuyl
>
>
> --
> Folding@home
> What if you could share your unused computer power to help find a cure? In
> just 5 minutes you can join the world's biggest networked computer and get
> us closer sooner. Watch the video.
> http://folding.stanford.edu/
>
>
> http://Van.Tuyl.eu/
> http://members.chello.nl/hjgtuyl/tourdemonad.html
> Haskell programming
> --
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://mail.haskell.org/pipermail/beginners/attachments/20150604/8e388574/attachment-0001.html>
------------------------------
Message: 5
Date: Fri, 05 Jun 2015 10:57:45 +0200
From: "Henk-Jan van Tuyl" <[email protected]>
To: Sourabh <[email protected]>
Cc: [email protected]
Subject: Re: [Haskell-beginners] Haskell Bin Tree Cellular Automata.
Message-ID: <op.xzq1unptpz0j5l@alquantor>
Content-Type: text/plain; charset=iso-8859-15; format=flowed;
delsp=yes
'iterate' uses optimization techniques, see the source code[0][1] (click
the 'source' links). I didn't study these techniques in detail.
[0]
http://haddocks.fpcomplete.com/fp/7.8/20140916-162/base/Prelude.html#v:iterate
[1]
http://haddocks.fpcomplete.com/fp/7.8/20140916-162/base/GHC-Exts.html#v:build
On Fri, 05 Jun 2015 01:31:07 +0200, Sourabh <[email protected]>
wrote:
> Wow, it runs in 0.44 seconds now. This is incredible! Can you explain
> what
> just happened here?
>
> On Thu, Jun 4, 2015 at 4:28 PM, Henk-Jan van Tuyl <[email protected]>
> wrote:
>
>> On Fri, 05 Jun 2015 00:50:25 +0200, Sourabh <[email protected]>
>> wrote:
>>
>> I figured out that I am constantly re-computing the trees, and decided
>> to
>>> try and memoize the results. Here is my memoization attempt:
>>>
>>> https://github.com/cbrghostrider/Hacking/blob/master/HackerRank/FunctionalProgramming/Recursion/cellular_automata_memoize_attempt.hs
>>>
>>> Basically I have changed the simulateCellularAutomata function, which
>>> computed the new trees, into a list (automataTrees - line 60). I was
>>> expecting the results to be memoized, but the runtime is unchanged.
>>>
>>
>> At a glance: maybe if you change the line
>> automataTrees starttree rule = (starttree) : [ simulateAutomataStep
>> Nothing rule ((automataTrees starttree rule) !! (n-1)) | n <- [1..]]
>> to
>> automataTrees starttree rule = iterate (simulateAutomataStep Nothing
>> rule) starttree
>> it will run faster. The function 'iterate' can be found in Prelude and
>> Data.List.
>>
>> Regards,
>> Henk-Jan van Tuyl
--
Folding@home
What if you could share your unused computer power to help find a cure? In
just 5 minutes you can join the world's biggest networked computer and get
us closer sooner. Watch the video.
http://folding.stanford.edu/
------------------------------
Subject: Digest Footer
_______________________________________________
Beginners mailing list
[email protected]
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
------------------------------
End of Beginners Digest, Vol 84, Issue 6
****************************************
