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

On Fri, 05 Jun 2015 00:50:25 +0200, Sourabh 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/FunctionalPr...

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

On Thu, Jun 04, 2015 at 04:31:07PM -0700, Sourabh wrote:

Wow, it runs in 0.44 seconds now. This is incredible! Can you explain what just happened here?

Here is a try at an explanation. To reduce the complexity involved with creating automata trees, lets define a very simple function: module Memo () where calc :: Integer -> Integer calc = (1+) And now we build a list of integers in a similar fashion to your tree-generating function: ints :: Integer -> [Integer] ints i = i : [calc (ints i !! (n-1)) | n <- [1..]] Store this in a file, fire up ghci, load the file and enter take 500 $ ints 1 You can literally watch things slowing down as new values are being printed. As you said correctly, at every call to `ints` the whole list is recalculated up to the value you need. Since `ints` is called with a new parameter at every iteration, Haskell has no way of memoizing anything. Let's add some memoization: ints2 :: Integer -> [Integer] ints2 i = let is = i : [calc (is !! (n-1)) | n <- [1..]] in is Again, load this in ghci and run take 500 $ ints2 1 Marvel at the difference. `is` has type [Integer] and as such is a constant. Already calculated values of `is` will therefore be memoized, so the whole list is only created once. Still, this is far from ideal. Enter ints2 1 !! 50000 and wait some more. The problem is that the algorithm still has O(n^2) complexity, n being the length of the list you need to create. At every iteration, `is !! (n-1)` accesses the (n-1)th element of `is` which takes itself n-1 operations. So, to generate a list of ten elements, the algorithm runs is !! 1 is !! 2 . . . is !! 9 to a total of 45 operations. For small list sizes, this makes hardly a difference, but for a list size of 50'000, this means already 1'249'975'000 operations doing nothing but traversing a list. Let's improve this further: ints3 :: Integer -> [Integer] ints3 i = i : ints3 (calc i) Here we use Haskell's lazyness to great effect. This function says: our list of ints is the initial value, prepended to the list of ints starting at the next value. take 500 $ ints3 1 and ints3 1 !! 50000 are both very fast. Every item in the list is calculated exactly once and the algorithm runs in linear time. Now you will only run into trouble at very large indices (above 10'000'000 on my computer). `ints3` is not tail recursive and will produce a stack overflow for very large lists. When you look at the source code of `iterate` you will see that it is just a generalized version of `ints3` taking an additional higher order function as input. I hope this sheds some light Stefan

On 2015-06-06 06:01, Stefan Höck wrote:

On Thu, Jun 04, 2015 at 04:31:07PM -0700, Sourabh wrote:

...

Wow, it runs in 0.44 seconds now. This is incredible! Can you explain what just happened here?

Here is a try at an explanation.

Thank you a lot for taking the time to walk through it! One thing got me thinking though:

And now we build a list of integers in a similar fashion to your tree-generating function:

ints :: Integer -> [Integer] ints i = i : [calc (ints i !! (n-1)) | n <- [1..]]

Store this in a file, fire up ghci, load the file and enter

take 500 $ ints 1

[..]

Let's add some memoization:

ints2 :: Integer -> [Integer] ints2 i = let is = i : [calc (is !! (n-1)) | n <- [1..]] in is

Again, load this in ghci and run

take 500 $ ints2 1

Marvel at the difference.

This is what's known as 'Tying the Knot' (e.g. on https://wiki.haskell.org/Tying_the_Knot), right? I wonder - would it be possible (and plausible) for a compiler to perform this rewriting automatically, such that any occurrence of code like f x = e where 'e' involves a call to 'f x' gets replaced with f x = let z = e in z and all occurences of 'f x' in 'e' get replaced with 'z'? -- Frerich Raabe - raabe@froglogic.com www.froglogic.com - Multi-Platform GUI Testing