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:
1st 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 2nd version; the performance gain is astounding, time both programs for the calculation up to the 40th 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.
2nd 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
}