leetcodeでアルゴリズムを勉強し始めたので初投稿です。
問題
n番目のフィボナッチ数列の値を算出する
直感的に解く
fibonacci.go
func Fibo(n int) int {
if n < 2 {
return n
}
return Fibo(n-2) + Fibo(n-1)
}
n=4だったら、
Fibo(4) = Fibo(2) + Fibo(3)
Fibo(4) = Fibo(0) + Fibo(1) + Fibo(1) + Fibo(2)
Fibo(4) = 0 + 1 + 1 + Fibo(0) + Fibo(1)
Fibo(4) = 0 + 1 + 1 + 0 + 1 = 3
って感じで計算が進む。計算が重複してるので遅い。
積み上げ式
fibonacci.go
func Fibo2(n int) int {
x, y := 0, 1
for i := 0; i < n; i++ {
x, y = y, x+y
}
return x
}
n=4なら、
x,y = 1,1
x,y = 1,2
x,y = 2,3
x,y = 3,5
で 3が返される。計算重複しないので早い。
メモ化で解く
fibonacci.go
func Memorize(n int, memo map[int]int) int {
if n < 2 {
return n
}
if _, ok := memo[n]; !ok {
memo[n] = Memorize(n-2, memo) + Memorize(n-1, memo)
}
return memo[n]
}
マップに保存して、すでに計算してる場合はマップから取り出して使うようにする。
どのくらい早いのか
benchmarkで計測。
n=0..40まで計算させて、時間を比較してみた。
テストはてきとーにこんな感じで書いてみる
fibonacci_test.go
func BenchmarkFibo(b *testing.B) {
for i := 0; i < 40; i++ {
Fibo(i)
}
}
func BenchmarkFibo2(b *testing.B) {
for i := 0; i < 40; i++ {
Fibo2(i)
}
}
func BenchmarkFibo3(b *testing.B) {
memo := make(map[int]int)
for i := 0; i < 40; i++ {
Memorize(i, memo)
}
}
結果は
Fibo(ふつうのやつ) => 1.356s
Fibo2(積み上げ式) => 0.008s
Fibo３(メモ化) => 0.008s
早すぎて草。真面目にアルゴリズム勉強しようと思った。
行列を使うともっと早くなるらしい。
もっと早い方法知っていたら教えてください。