reset password
Author Message
rabbott
Posts: 1649
Posted 12:16 Feb 18, 2019 |

If you are interested, here's my Haskell version of top_down_iter.

data FibElement = I Integer | Fib Integer | Plus deriving Show

fib_top_down_iter_v2 :: Integer -> Integer
fib_top_down_iter_v2 n = fibA ([Fib n], [])

-- The first list is reversed from the Python version.
-- I put the two lists into a tuple to reduce the number of parentheses needed.
fibA :: ([FibElement], [FibElement]) -> Integer
fibA ([I ans],  _) = ans 
fibA (I n : fibs,  s) = fibA (fibs,  I n : s) 
fibA (Plus : fibs, I n1 : I n2 : s) = fibA (I (n1+n2) : fibs,  s)
fibA (Fib n : fibs,  s) 
    | n <=2 = fibA (I 1 : fibs, s)
    | otherwise = fibA (Fib (n-2) : Fib (n-1) : Plus : fibs, s)

rabbott
Posts: 1649
Posted 16:39 Feb 18, 2019 |

This version includes an optional trace. It also drops the I constructor from FibElement. That's possible because the stack contains nothing but Integers. That is,
stack :: [Integer]. The left stack contains Fib operations, either Fib n or Plus.

 

-- Formally, Plus is a constructor. But since it is applied to no arguments,
-- we can use it effectively as a value.
-- That's also true of True and False.
data FibOp = Fib Integer | Plus deriving Show

 

fib_top_down_iter :: Integer -> Bool -> Integer
fib_top_down_iter n tr = fibAux_tr ([Fib n], []) tr

 

-- This function does the trace if requested.
fibAux_tr :: ([FibOp], [Integer]) -> Bool -> Integer
-- Note the pattern-matching for False and True.
fibAux_tr state False =                      fibAux state False
fibAux_tr state True  = trace (show state) $ fibAux state True

 

fibAux :: ([FibOp], [Integer]) -> Bool -> Integer
-- All the FibOps are done; the top of the stack is the final answer. 
fibAux ([], [ans]) _                   = ans 


-- The result of an operation is put at the top of the stack.
fibAux (Plus : fibOps, n1 : n2 : s) tr = fibAux_tr (fibOps, (n1+n2) : s) tr


-- If the guard fails, the program moves on to the next clause.
fibAux (Fib n : fibOps, s) tr | n <=2  = fibAux_tr (fibOps, 1 : s) tr


-- If we get here, we know that n > 2.
fibAux (Fib n : fibOps, s) tr          = fibAux_tr (Fib (n-2) : Fib (n-1) : Plus : fibOps, s) tr

 

> fib_top_down_iter 6 True
([Fib 6],[])
([Fib 4,Fib 5,Plus],[])
([Fib 2,Fib 3,Plus,Fib 5,Plus],[]) -- Fib 2 is 1, which is put at the top of the stack.
([Fib 3,Plus,Fib 5,Plus],[1])
([Fib 1,Fib 2,Plus,Plus,Fib 5,Plus],[1]) -- Same for Fib 1.
([Fib 2,Plus,Plus,Fib 5,Plus],[1,1])
([Plus,Plus,Fib 5,Plus],[1,1,1]) -- Plus adds the top two elements of the stack
([Plus,Fib 5,Plus],[2,1])        -- and put the result back on the stack.
([Fib 5,Plus],[3])
([Fib 3,Fib 4,Plus,Plus],[3])
([Fib 1,Fib 2,Plus,Fib 4,Plus,Plus],[3])
([Fib 2,Plus,Fib 4,Plus,Plus],[1,3])
([Plus,Fib 4,Plus,Plus],[1,1,3])
([Fib 4,Plus,Plus],[2,3])
([Fib 2,Fib 3,Plus,Plus,Plus],[2,3])
([Fib 3,Plus,Plus,Plus],[1,2,3])
([Fib 1,Fib 2,Plus,Plus,Plus,Plus],[1,2,3])
([Fib 2,Plus,Plus,Plus,Plus],[1,1,2,3])
([Plus,Plus,Plus,Plus],[1,1,1,2,3])
([Plus,Plus,Plus],[2,1,2,3])
([Plus,Plus],[3,2,3])
([Plus],[5,3])
([],[8])
8
 

Last edited by rabbott at 19:33 Feb 18, 2019.
jungsoolim
Posts: 38
Posted 10:47 Feb 19, 2019 |

After I rewrote #3 with pattern matching, I got 

ghci> fib_top_down_iter 32
2178309
(5.73 secs, 3,851,303,904 bytes)
 

My previous version took over 45 seconds. Without any optimization, only using pattern matching the efficiency has been improved 8 - 9 times!

In addition, the length of code has been reduced by 1/3!

 

 

rabbott
Posts: 1649
Posted 13:41 Feb 19, 2019 |

Good! That's about what I got running the code above (with no trace).

> fib_top_down_iter 32 False
2178309
(5.99 secs, 2,736,010,568 bytes)
 

I wonder why yours took so much more memory: 2,736,010,568 bytes vs 3,851,303,904 bytes

jungsoolim
Posts: 38
Posted 13:54 Feb 19, 2019 |

It may due to not using Haskell features correctly.

Here is what I am doing.

data FibElement = I Integer | Fib Integer | Plus | Cache Integer deriving Show

fib_top_down_iter n = fib_top_down_iter_helper ([Fib n], [])
fib_top_down_iter_helper ([I ans], _) = ans
fib_top_down_iter_helper (I n: fibs, stack) = fib_top_down_iter_helper(fibs, I n: stack)
fib_top_down_iter_helper (Fib n: fibs, stack) 
                       | n <= 2 = fib_top_down_iter_helper (I 1: fibs, stack)
                       | otherwise = fib_top_down_iter_helper ( [Fib (n - 2), Fib (n - 1), Plus] ++ fibs, stack)
fib_top_down_iter_helper (Plus: fibs, I n1: I n2: stack) = fib_top_down_iter_helper (I (n1 + n2) : fibs, stack) 

What portion of the program uses excessive memory? How could I improve it? Any comments?

Thanks!

rabbott
Posts: 1649
Posted 18:11 Feb 19, 2019 |

There doesn't seem to be anything terribly wasteful. I wonder if it's due to a combination of (a) using (I n) on the stack instead of just n as my code does and (b) putting the result of an operation back on the inp rather than directly on the stack.