Memoization in Golang

Memoization is a technique used to improve the performance of algorithms by storing the results of expensive function calls and returning the cached result when the same inputs occur again. This can be especially useful for recursive functions, where the same subproblems may be solved multiple times.

func fibonacci(n int) int {
 if n <= 1 {
  return n
 }
 return fibonacci(n-1) + fibonacci(n-2)
}

The fibonacci function above is a recursive function that calculates the nth number in the Fibonacci sequence, which is defined as follows:

• The first number is 0.
• The second number is 1.
• Each subsequent number is the sum of the previous two numbers.

The fibonacci function calculates the nth number by recursively calling itself with n-1 and n-2 as the input values. For example, to calculate fibonacci(5), the function would make the following recursive calls:

fibonacci(5)
= fibonacci(4) + fibonacci(3)
  = (fibonacci(3) + fibonacci(2)) + (fibonacci(2) + fibonacci(1))
    = ((fibonacci(2) + fibonacci(1)) + (fibonacci(1) + fibonacci(0))) + ((fibonacci(1) + fibonacci(0)) + fibonacci(1))

As you can see, the function calculates the same values multiple times as it recursively calls itself. For example, fibonacci(2) is calculated three times in the above example. This can lead to a significant performance problem, especially for larger input values, as the time complexity of the function is exponential.

Simple memoization

To avoid this issue, you can use memoization to store the results of function calls and return the cached result when the same input value occurs again. This can help to improve the performance of the fibonacci function by avoiding unnecessary recalculations of the same result.

package main

import "fmt"

var cache = make(map[int]int)

func fibonacci(n int) int {
 if n <= 1 {
  return n
 }
 if v, ok := cache[n]; ok {
  return v
 }
 result := fibonacci(n-1) + fibonacci(n-2)
 cache[n] = result
 return result
}

func main() {
 fmt.Println(fibonacci(40))
}

The code above use a simple memoization technique, the cache map is a key value data structure that holds unique the result during each iteration. Inside the ifblock it checks to see if the target being calculated has already existed in the map, if so it will return the value directly instead of repeating the duplicate calculation.

Advanced memoization with struct

In Go, structs can be used to implement memoization by storing the results of function calls in a map keyed by the input parameters. for example:

type memoized struct {
 f     func(int) int
 cache map[int]int
}

This code defines a struct type called memoized that has two fields:

• f: a field of type func(int) int representing a function that takes an integer as input and returns an integer as output.
• cache: a field of type map[int]int representing a cache of the results of the function f. The keys in the map are the input values and the values are the corresponding results.

The memoized struct can be used to implement memoization for a function f by storing the results of function calls in the cache map. When the function is called with a given input value, the cache can be checked to see if the result has already been calculated. If it has, the result can be retrieved from the cache. If not, the function can be called to calculate the result, which can then be stored in the cache for future use.

now we can define a memoize function as a higher-order function that takes a function f of type func(int) int as input and returns a pointer to a memoized struct.

func memoize(f func(int) int) *memoized {
 return &memoized{f: f, cache: make(map[int]int)}
}

This function creates a new memoized struct with the input function f and an empty cache map, and returns a pointer to this struct. The returned memoized struct can be used to implement memoization for the function f by storing the results of function calls in the cache map. When the function is called with a given input value, the cache can be checked to see if the result has already been calculated. If it has, the result can be retrieved from the cache. If not, the function can be called to calculate the result, which can then be stored in the cache for future use. This can help to improve the performance of the function by avoiding unnecessary recalculations of the same result.

To implement that we can define a call method on the memoized struct with the following signature:

func (m *memoized) call(x int) int

The call function will carry out the cache checking process as the following.

func (m *memoized) call(x int) int {
 if v, ok := m.cache[x]; ok {
  return v
 }
 result := m.f(x)
 m.cache[x] = result
 return result
}

The method takes an integer x as input and returns an integer. The method is used to call the function stored in the f field of the memoized struct, with the input value x. The method implements memoization for the function by using the cache field to store the results of function calls.

The method first checks the cache map to see if the result for the input value x has already been calculated and stored. If it has, the method returns the cached result from the map. If not, the method calls the function m.f with the input value x to calculate the result, and then stores the result in the cache map before returning it.

By using the call method to call the function stored in the memoized struct, you can benefit from the performance improvement of memoization without modifying the original function. This can be especially useful when you want to apply memoization to an existing function that you do not have control over or do not want to modify.

Conclusion

Using structs as memoization can be an effective way to improve the performance of algorithms in Go, particularly for recursive functions or functions that are called repeatedly with the same inputs. However, it is important to consider the trade-offs between the additional memory usage and the improved performance, and to carefully choose when and how to use memoization in your code.