こんにちは、アルバイトの齋藤です。
今回はプログラマの方なら誰でも実装したことがあるのではないでしょうか、フィボナッチ数列を求めるアルゴリズムについてGolangで実装してみたいと思います。

フィボナッチ数列とは

F0 = 0
F1 = 1
Fn + 2 = Fn + Fn + 1 (n ≧ 0)

今回はこの定義をフィボナッチ数列とします。

え、実装するだけ？

と思う方もいらっしゃるかと思いますので、少しパフォーマンスチューニングの話も入り交えて実装しようと思います。

一般的に思いつくもの

といえば再帰を用いた実装だと思います。ではやってみましょう

func fib1(i int) int {
if i < 1 {
return 0
}
if i < 3 {
return 1
}
return fib1(i-1) + fib1(i-2)
}

出来ましたね
ではベンチマークを図ってみましょう。テストとしてfib1(10)を回してみたいと思います

なるほどなるほど…

では次は「Golangって再帰に弱い」とよく聞くので、再帰を使わずに実装してみましょう

再帰使わない

悩んだ結果、こうなりました

func fib2(i int) int {
a := []int{1, 1}
j := 1
for ; j < i; j++ {
a[j%2] += a[(j+1)%2]
}
return a[j%2]
}

Golangのsliceを使って実装しています。こうすれば再帰は使わずに実装できますね
ではベンチマーク行ってみましょう

おぉ、341nsから一気に26.6nsまで行きましたね
ではこれを軸に改良していきましょう

ループの回数を減らしてみる

今までは i 分だけ回してましたが、 i/2 分だけにしてみましょう

func fib3(i int) int {
a := []int{1, 1}
j := 2
for ; j < i; j += 2 {
a[j%2] += a[(j+1)%2]
a[(j+1)%2] += a[j%2]
}
return a[(i+1)%2]
}

だんだん読みづらくなってきました…
ベンチマーク行ってみましょう

17.4ns!!どんどん早くなって行ってますね
ここまでは自分で工夫して行きましたがそろそろ限界なのでいろいろ調べてみましょう

Golangのパフォーマンスチューニング

よく挙げられていたのは

• メモリのアロケーション回数を減らす
• 要素数が事前にわかっている場合には append を使わない
• channel を使わない
• 関数（メソッド）を呼ばない

などなど…
いろいろ調べましたが、今回のコードで悪いところといえばsliceを使っているところですかね？(本来はトリニボッチとかに対応するためにsliceにしたのですが…)
ではこれをただのIntの変数に変えてみましょう

これが一番早いと思います

func fib4(i int) int {
a := 1
b := 1
j := 2
for ; j < i; j += 2 {
a += b
b += a
}
if i%2 == 0 {
return b
}
return a
}

見る限り爆速そうですね(適当)
ではベンチマークしてみましょう

え？5.20ns？めちゃくちゃ早くなった！！！！
やっぱり毎回sliceでアクセスするのは遅いですね(というかsliceの値にアクセスするのに%演算子要らなくないか…？)

まとめ

ということでフィボナッチ数列を求めるプログラムが341nsから5.2nsになり、約65倍の高速化に成功しました！
ベンチマークに関しては使うのが初めてだったのでオプションとか使っていないのでもう少し調べてやってみたいですね