0

I am learning more about dynamic programming and was trying to implement it in haskell. I was running tests with different ways to write the algorithms and found that one is faster than the other. Here it is in the fibonacci problem

fib1 :: [Integer]
fib1 = 0:1:zipWith (+) fib1 (tail fib1)

fib2 :: [Integer]
fib2 = 0:1:[(fib2 !! (n-1)) + (fib2 !! (n-2)) | n <- [2..]]

fib1 is much faster than fib2 but I can't tell why. fib2 seems intuitive, the nth number is (n-1)st plus the (n-2)nd. And I get fib1, but it looks like it is zipping over the whole list everytime so wouldn't that take longer than. Just calculating the next index?

Ro-Bert
  • 41
  • 4
  • 2
    The cost of computing `fib2 !! n` grows linearly with n. This is a linked list not a vector. BTW recent question on Fibonacci with some pointers: [SO_q66180076](https://stackoverflow.com/questions/66180076/fibonacci-numbers-without-using-zipwith) – jpmarinier Feb 16 '21 at 21:21
  • I realize that fib2 !! n is linear due to the linked list. But what about fib1? Is that not a linked list too? – Ro-Bert Feb 16 '21 at 22:09
  • @Ro-Bert Yes, but each time `fib1` is asked to produce another number it only needs to do O(1) work, not O(n) like `fib2`. (Plus the time it takes to do an `Integer` addition, obviously, but that's the same for both implementations.) – Daniel Wagner Feb 16 '21 at 23:17
  • Okay. I think I kind of expected that was happening. I knew fib2 had that O(n) for each time so it's actually O(n^2). So then am I not understanding zipWith correctly? I feel like that should be O(n) too. Unless it doesn't run through the lists like a for loop might. – Ro-Bert Feb 17 '21 at 07:16
  • Actually, this helped a lot. I was thinking that zipWith would be linear too. But this helped me to research. I found this thread https://stackoverflow.com/questions/55291798/time-complexity-of-zipwith-fibonacci-in-haskell?rq=1 which explains it pretty well. – Ro-Bert Feb 17 '21 at 07:32
  • There's a related question in https://stackoverflow.com/questions/3208258/memoization-in-haskell/3209189#3209189 – Masse Feb 17 '21 at 12:53

2 Answers2

0

Lists in Haskell are lazy. They're being calculated as they're being used, but not further.

The function fib1 indeed calculates the whole list, but only does it once, and only up to the index you're asking for.

The function fib2 does a lot of extra work: it potentially calculates elements many, many times over.

Just try to do it with pen and paper. For example, in the case of fib2 !! 5, the list needs to be expanded up to index 5. Calculating fib2 !! 0 and fib2 !! 1 takes little time, as they are constants. The next element, fib2 !! 2 is calculated by adding fib2 !! 0 and fib2 !! 1, and then fib2 !! 3 = fib2 !! 1 + fib2 !! 2, and so on.

BUT.

The most important thing to note here, is that the compiler and/or runtime does not memoize the fib2 function, meaning: it does not remembers previous calculations. So every time the code hits a fib2 !! n it starts calculating it all over again, it doesn't matter how many time this has been done before, even if this happened in the very same (recursive) function call.

Regarding computational efficiency, your fib2 implementation is equivalent to this:

fib3' :: Integer -> Integer
fib3' 0 = 0
fib3' 1 = 1
fib3' n = fib3' (n - 2) + fib3' (n - 1)

fib3 :: [Integer]
fib3 = [fib3' n | n <- [0..]]

which suffers from the same inefficiency, I merely factored out the list part.

On the other hand, fib1 takes advantage of the previous calculations, by using them to avoid re-calculating them. And that's the core idea behind dynamic programming: use a data structure that can be used to store and retrieve results of previous calculations to exchange a potentially expensive recursive function call to a - hpefully - much cheap lookup.

netom
  • 3,322
  • 2
  • 21
  • 21
0

@netom sorry but I don't think that's what's happening. I ran some tests on time and to calculate the 10000th number took 0.7 seconds. In the same run it was instant to calculate the 10000th + 9999th (the 10001th number) showing it remembered.

I then tested the time it took to freshly calculate the 10001st and it took the same time to calculate the 10001st as if it calculated the 10000 and remembered all the rest. To calculate the 10001st, it does not calculate for 10000 and 9999 (in separate recursions) it behaves like you'd expect if it just indexed the remembered list.

The recursive function however takes almost twice as long! So they're both using dynamic programming correctly. But as I've found, the fib2 takes O(n) each step to access the array but fib1 zips it in O(1) each step.

Ro-Bert
  • 41
  • 4