Skip to content

Instantly share code, notes, and snippets.

@icub3d
Created August 3, 2012 06:09
Show Gist options
  • Save icub3d/3244972 to your computer and use it in GitHub Desktop.
Save icub3d/3244972 to your computer and use it in GitHub Desktop.
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