Determinism Counts! (Memoization)
package main | |
import ( | |
"fmt" | |
"time" | |
) | |
func Fibonacci(n int64) int64 { | |
var f int64 | |
if n <= 1 { | |
f = 1 | |
} else { | |
f = Fibonacci(n-1) + Fibonacci(n-2) | |
} | |
return f | |
} | |
var fibonacciLUT map[int64]int64 | |
func MemoizedFibonacci(n int64) int64 { | |
var f int64 | |
if stored, ok := fibonacciLUT[n]; ok { | |
return stored | |
} | |
if n <= 1 { | |
f = 1 | |
} else { | |
f = MemoizedFibonacci(n-1) + MemoizedFibonacci(n-2) | |
} | |
fibonacciLUT[n] = f | |
return f | |
} | |
func testFib(count int64, name string, f func(int64) int64) { | |
begin := time.Now() | |
var x int64 | |
for x = 0; x < count; x++ { | |
f(x) | |
} | |
end := time.Now() | |
msg := "%d iterations of %s took %v to complete.\n" | |
fmt.Printf(msg, count, name, end.Sub(begin)) | |
} | |
func init() { | |
fibonacciLUT = make(map[int64]int64) | |
} | |
func main() { | |
testFib(50, "Non-memoized", Fibonacci) | |
testFib(50, "Memoized", MemoizedFibonacci) | |
} |
$ go run fibonacci.go | |
50 iterations of Non-memoized took 5m37.824026s to complete. | |
50 iterations of Memoized took 106us to complete. |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment