Dynamic Programming in Go

Introduction

Dynamic Programming can be thought of as an approach of breaking a complex problem into sub-problems, solving each of these sub-problems one time only, and saving their solutions for future use. As we will see later in this blog, this approach offers efficiency and modularity benefits over other approaches that we will be exploring in a bit.

Dynamic Programming Techniques

When we talk about Dynamic Programming, we must as well discuss its techniques. Below are the techniques:

  • Memoization: the technique is known as “Memoization” (not to be confused with Memorization). Memoization is a technique for improving the performance of a recursive function/algorithm. In other words, it offers an optimization to speed up programs by storing the solutions of expensive function calls and returning the cached solution when the same inputs are fed to the program again.

  • Tabulation: another optimization technique used in Dynamic Programming is Tabulation (also known as the Bottom-Up technique). As you might guess, this technique uses a tabular approach by first filling up a table, then solve the original problem based on the solutions filled in the table. We will not be looking into this technique in this blog but Memoization.

Now that we have discussed what Dynamic Programming is and its techniques. Now, let’s step into the coding part. We are going to use the Fibonacci Sequence problem as an example, solving it using three distinct approaches. If you are reading about the Fibonacci Sequence for the first time, think of it as the series of numbers in which the next number is found by adding up the two numbers before it. For example, the sequence [0, 1, 1, 2, 3, 5, 8, 13, 21, 34] forms the first ten entries of the Fibonacci series. With that explained, a Fibonacci(10) will result in 55.

The first step to starting any of the approaches is to define a function to help us track the execution time consumed by each of the solutions we will be presenting:

// for tracking program's execution time
func trackTime(start time.Time, result int, name string) {
	elapsed := time.Since(start)
	log.Printf("---> %s solution | result: %v | took: %s", name, result, elapsed)
}

Recursion

One quick approach that is likely to come to mind when faced with the Fibonacci Sequence problem above is to use a Recursion. Perfect. But, let’s see the implementation and efficiency of this approach:

// the recursive function approach definition
func expensiveFib(n int) int {
  if n < 2 {
  	return n
  }

  result := expensiveFib(n-1) + expensiveFib(n-2)

  return result
}

Running the Recursion solution with an input of 50 will result in 12586269025 with an execution time of roughly 1m and 6.413943065s. So, why does it take this long time?  Simply put, the reason is due to the recursive call of the function; we are checking if the input is less than 2. If yes, we return the input, and move to the next stack of the function calls. In this case, the returned input would be either 1 or 0. On the other hand, if 2 is not greater than the input, we call the function twice; one time with the input - 1 and the second time with the input - 2, and sum the result of both calls. The image below depicts the process (using an input of 5): Fibonacci Sequence image

Loop

Another approach that is likely to be thought of is to use a loop. Let’s see the implementation and efficiency of this approach:

// the loop approach definition
func fibByLoop(n int) int {
	fibBox := []int{0, 1}

	for  i := 0; i < n; i++ {
		v := fibBox[i] + fibBox[i+1]
		fibBox = append(fibBox, v)
	}

	result := int(fibBox[n])
	defer trackTime(time.Now(), result, "Loop")
	
	return result
}

Running the Loop solution with an input of 50 will result in 12586269025 with an execution time of roughly 2.356µs. That seems way faster than the Recursive approach. From 1m and 6.413943065s down to 1.428µs. Impressive! So what is the algorithm behind this solution? The answer is, we used an iterative approach. Let us review the steps below:

  • We create and initialize an array, namely fibBox to values of 0 and 1 (those are the starting point for the Fibonacci Sequence).
  • In the loop, we created another variable namely i, and initialized it to 0. This is used as an index of fibBox in each iteration.
  • We iterate over the parameter n and check if i < n. As long as i < n, we decrement n.
  • In each iteration, we sum up the values of current and next indexes in fibBox (e.g., fibBox[i] + fibBox[i+1] ), and append the result to fibBox. Once the loop is done running, we return the value of fibBox[n]; that is the result of the Fibonacci Sequence of the input we were given.

Memoization

Another approach would be Memoization. Let’s see the implementation and efficiency of this approach. As explained above, Memoization improves the performance of Recursion, which means we should start by implementing a recursive function first (we will use the one defined above) then, we will improve its efficiency by storing and reusing the solutions in the cache.

// we made a few changes to the one used used above in the Recursion solution
func refinedExpensiveFib(n int, cache map[int]int) int {
	if n < 2 {
		cache[n] = n   // n is either 0 or 1
		return n
	}

	// check cache before calling the function recursively
	if _, ok := cache[n-1]; !ok {
		// we haven't come across n-1 before
		cache[n-1] = refinedExpensiveFib(n-1, cache)
	}
	// At this point, n-1 is in the cache. You could log n-1

	if _, ok := cache[n-2]; !ok {
		// we haven't come across n-1 before
		cache[n-2] = refinedExpensiveFib(n-2, cache)
	}
	// At this point, n-2 is in the cache. You could log n-2

	// returns the summed up cache
	return cache[n-1] + cache[n-2]
}

Finally, we define a memoize() that will consume refinedExpensiveFib() :

// the memoize approach definition
func memoize(n int) int {
    cache := make(map[int]int)
    result := make([]int, n)

    for i := 1; i <= n; i++{
		result[i-1] = refinedExpensiveFib(i, cache)
	}

	return result[n-1]
}

Running the Memoization solution with an input of 50 will result in 12586269025 with an execution time of roughly 181ns. That is absolutely way faster and more efficient than the Loop solution which resulted in 2.356µs. In addition to performance gain, we also have the flexibility of making the solution modular and somehow readable.

The full program below [I would advise that you run each solution individually]:

package main

import (
	"log"
	"time"
)

func main(){
	input := 50

	//Recursion
	start := time.Now()
	result := expensiveFib(input)
	defer trackTime(start, result, "Recursion")

	//Loop
	fibByLoop(input)

	//Memoization
	memoize(input)
}

/* function for measuring the execution the */
func trackTime(start time.Time, result int, name string) {
	elapsed := time.Since(start)
	log.Printf("---> %s solution | result: %v | took: %s", name, result, elapsed)
}

/* Recursion solution */
func expensiveFib(n int) int {
  if n < 2 {
  	return n
  }

  result := expensiveFib(n-1) + expensiveFib(n-2)

  return result
}


/* using loop */
func fibByLoop(n int) int {
	fibBox := []int{0, 1}

	for  i := int(0); i < n; i++ {
		v := fibBox[i] + fibBox[i+1]
		fibBox = append(fibBox, v)
	}

	result := int(fibBox[n])
	defer trackTime(time.Now(), result, "Loop")
	
	return result
}


/* Memoization solution */
// using memoization
func refinedExpensiveFib(n int, cache map[int]int) int {
	if n < 2 {
		cache[n] = n   // n is either 0 or 1
		return n
	}

	// check cache before calling the function recursively
	if _, ok := cache[n-1]; !ok {
		// we haven't come across n-1 before
		cache[n-1] = refinedExpensiveFib(n-1, cache)
	}
	// At this point, n-1 is in the cache. You could log n-1

	if _, ok := cache[n-2]; !ok {
		// we haven't come across n-2 before
		cache[n-2] = refinedExpensiveFib(n-2, cache)
	}
	// At this point, n-2 is in the cache. You could log n-2

	// returns the summed up cache
	return cache[n-1] + cache[n-2]
}

func memoize(n int) int {
	cache := make(map[int]int)
    bucket := make([]int, n)

    for i := 1; i <= n; i++{
		bucket[i-1] = refinedExpensiveFib(i, cache)
	}

	result := bucket[n-1]
	defer trackTime(time.Now(), result, "Memoization")
	return result
}

Running the main() will result in:

2020/09/19 21:44:40 ---> Recursion solution   | result: 12586269025 | took: 2m18.47818166s
2020/09/19 21:42:22 ---> Loop solution        | result: 12586269025 | took: 2.356µs
2020/09/19 21:44:40 ---> Memoization solution | result: 12586269025 | took: 181ns

Memoization offers a modularity and code readability benefits over the Loop approach; we saw how we improved/refined the logic in expensiveFib() (we named it refinedExpensiveFib()), then we called it inside the memoize().

Conclusion

In this blog, we explored three different approaches to solving the Fibonacci Sequence problem. We weighed each approach’s efficiency, readability, and modularity. You can read more on Memoization in this blog: Dynamic Programming and Memoization and the Compute versus Storage Tradeoff

I hope you enjoyed reading through as much as I enjoyed writing this blog.

Let’s keep “Go”-ing :)