When doing heavy computations one thing that can be done for increasing performance is not to repeat any calculation that has already been done and that can/must be reused. Instead cache the calculated value in memory, which is called

*memoization*. A great example of this is the calculation of the Fibonacci series:to calculate the n-th Fibonacci number, you need the 2 preceding ones, which normally have already been calculated. If you do not stock the preceding results, every higher Fibonacci number results in an ever greater avalanche of recalculations, which is precisely what the following program does:

__1__^{st}version:package main

import (

"fmt"

"time"

)

func main() {

result := 0

start := time.Nanoseconds()

for i:=0; i <= 25; i++ {

result = fibonacci(i)

fmt.Printf("fibonacci(%d) is: %d\n", i, result)

}

end := time.Nanoseconds()

fmt.Printf("the calculation took this amount of time: %f\n", float32(end - start)/1000000000)

}

func fibonacci(n int) (res int) {

if n <= 1 {

res = 1

} else {

res = fibonacci(n-1) + fibonacci(n-2)

}

return

}

Simple stock the n-th Fibonacci number in an array at index n, and before calculating a fibonnaci-number, first look in the array if it has not yet been calculated.

This principle is applied in the 2

^{nd}version; the performance gain is astounding, time both programs for the calculation up to the 40^{th}Fibonnaci number: normal: the calculation took this amount of time: 4.730270 s

with memoization: the calculation took this amount of time: 0.001000 s

In this algorithm memoization is obvious, but it can often be applied in other computations as well, perhaps using maps instead of arrays or slices.

__2__^{nd}version:package main

import (

"fmt"

"time"

)

const LIM = 41

var fibs [LIM]uint64

func main() {

var result uint64 = 0

start := time.Nanoseconds()

for i:=0; i < LIM; i++ {

result = fibonacci(i)

fmt.Printf("fibonacci(%d) is: %d\n", i, result)

}

end := time.Nanoseconds()

fmt.Printf("the calculation took this amount of time: %f\n", float32(end - start)/1000000000)

}

func fibonacci(n int) (res uint64) {

// memoization: check if fibonacci(n) is already known in array:

if fibs[n] != 0 {

res = fibs[n]

return

}

if n <= 1 {

res = 1

} else {

res = fibonacci(n-1) + fibonacci(n-2)

}

fibs[n] = res

return

}