Today I Learned
Search…
Memoization using Golang Generics
Posted on 22 Jun, 2022
Memoization helps save computation of things that have already been computed by saving them for future use. In this example we use golang generics to implement a Memoized() function that can handle use-case.
// Required Go 1.18 or greater
​
package main
​
import "fmt"
​
type FibonacciDef func(int) int
​
func Memoize[K comparable, T any](fn func(K) T) func(K) T {
// Type K needs to be comparable (and hashable) since we used it as a map Key
// Type T is any type that can act as a map value
​
cache := make(map[K]T)
return func(n K) T {
if val, ok := cache[n]; ok {
return val
}
// add to cache if not found
cache[n] = fn(n)
return cache[n]
}
}
​
func main() {
var memoizedFib FibonacciDef
var simpleFib FibonacciDef
memoizedFib = Memoize(func(num int) int {
if num < 2 {
return num
}
return memoizedFib(num-1) + memoizedFib(num-2)
})
simpleFib = func(num int) int {
if num < 2 {
return num
}
return simpleFib(num-1) + simpleFib(num-2)
}
fmt.Println(memoizedFib(50))
// takes more than 1 minute to compute
fmt.Println(simpleFib(50))
}
Copy link
Edit on GitHub