こんにちは。Tomoyuki（@tomoyuki65）です。
コードを書く際に大事なこととして、データ量が増えても処理が重くならないよう、そしてそこがボトルネックにならないようにしておくことが大事です。
例えば新規サービスをリリース直後は利用者が少なくて問題がなかったとしても、その後に利用者数が増え、それによってパフォーマンス低下や処理が壊れるということがあったりします。
そういった問題を未然に防ぐためには、ビッグオー記法（Big-O記法）などを用いながら時間計算量や空間計算量を考慮してコードを書く必要がでてきます。
この記事では、Go言語（Golang）とビッグオー記法（Big-O記法）を用いて、時間計算量や空間計算量についてご紹介します。
Go言語（Golang）とビッグオー記法（Big-O記法）で時間計算量と空間計算量を学ぶ
ビッグオー記法（Big-O記法）とは？
まずビッグオー記法（Big-O記法）というのは、アルゴリズムの計算量（処理時間やメモリ資料量）が、入力データのサイズ（件数など）に対してどの程度増えるのかを表すための数学的な記法です。
例えば入力データのサイズをnとし、そのnが大きくなった時の増え方の上限を表しています。（ただし、定数倍や小さな差は無視します。）
これによってアルゴリズムの効率を比較したり、入力データのサイズが大きくなった時の最悪ケースの成長具合を知ることが可能です。
代表的な計算量まとめ
代表的な計算量としては、主に以下のような6種類があり、入力データのサイズnが大きくなるほど、次の順で遅くなっていくのを表します。
| 記法 | 名前 | 例 | イメージ |
|---|---|---|---|
| O(1) | 定数時間 | 配列の要素を1つ読む | 常に同じ速さ |
| O(log n) | 対数時間 | 二分探索 | 少しずつ増える |
| O(n) | 線形時間 | 配列を1回走査 | 入力に比例 |
| O(n log n) | 線形対数 | 高速ソート | 実用的に高速 |
| O(n²) | 二次時間 | 二重ループ | 急に遅くなる |
| O(2ⁿ) | 指数時間 | 総当たり | 非常に遅い |
Go言語（Golang）での各計算量のサンプルコード
O(1)
package main
import (
"fmt"
)
func main() {
// 5個の要素を持つ配列を定義
items := [5]int{1, 2, 5, 10, 20}
// 対象の要素を一つログ出力
fmt.Println(items[0])
}
実行結果
1
O(log n)
package main
import (
"fmt"
)
func main() {
// 5個の要素を持つ配列を定義
items := [5]int{1, 2, 5, 10, 20}
// 配列から探したい要素の値を設定
target := 10
// 結果のインデックスを格納する変数定義（見つからない場合は-1とする）
resultIndex := -1
// 二分探索で対象の要素を探す
low, high := 0, len(items)-1
for low <= high {
// 真ん中のインデックスを取得
mid := (low + high) / 2
if items[mid] == target {
// 真ん中が対象データの場合
resultIndex = mid
break
} else if items[mid] < target {
// 真ん中の値より対象データが大きい場合
low = mid + 1
} else {
// 真ん中の値より対象データが小さい場合
high = mid - 1
}
}
// 結果をログ出力
if resultIndex != -1 {
fmt.Printf("対象要素のインデックス：%d", resultIndex)
} else {
fmt.Println("対象の要素はありませんでした。")
}
}※ループ毎に要素を半分にして値を探していく
実行結果
対象要素のインデックス：3
O(n)
package main
import (
"fmt"
)
func main() {
// 5個の要素を持つ配列を定義
items := [5]int{1, 2, 5, 10, 20}
// 全ての要素をログ出力
for i, v := range items {
fmt.Printf("インデックス：%d, 値：%d\n", i, v)
}
}※配列の要素数が増えると単純に計算量も増える
実行結果
インデックス：0, 値：1
インデックス：1, 値：2
インデックス：2, 値：5
インデックス：3, 値：10
インデックス：4, 値：20
O(n log n)
package main
import (
"fmt"
"sort"
)
func main() {
// 5個の要素を持つ配列を定義
items := [5]int{1, 2, 5, 10, 20}
// 配列を参照するスライスを使ってソート処理（内部的にO(n log n)の処理）
sort.Ints(items[:])
// ログ出力
fmt.Println(items)
}※データを整理しながら処理するため、要素数が増えても単純に計算量が比例せず、現実的に実行できる計算量となる。他の例だとマージソート。
実行結果
[1 2 5 10 20]
O(n²)
package main
import (
"fmt"
)
func main() {
// 3個の要素を持つ配列を定義
items := [3]int{1, 10, 100}
// 2重ループで配列の全ペアの和を計算
for i := 0; i < n; i++ {
for j := 0; j < n; j++ {
fmt.Printf("%d + %d = %d\n", items[i], items[j], items[i]+items[j])
}
}
}※2重ループで「n × n = n²回処理」されるため、例えば配列の要素数が10倍になったら、計算量が一気に100倍になってしまう。（こういうのは避けたい！！）
実行結果
1 + 1 = 2
1 + 10 = 11
1 + 100 = 101
10 + 1 = 11
10 + 10 = 20
10 + 100 = 110
100 + 1 = 101
100 + 10 = 110
100 + 100 = 200
O(2ⁿ)
package main
import (
"fmt"
)
// フィボナッチ数列のn番目の値を返す関数
func fib(n int) int {
// nが0なら0、nが1なら1を返す
if n <= 1 {
return n
}
// 前の2つの数字の合計が次の数字になるという規則があるため、
// fib(n) = fib(n-1) + fib(n-2)を求める
return fib(n-1) + fib(n-2)
}
func main() {
// フィボナッチ数列の10番目の値をログ出力
n := 10
fmt.Println(fib(n))
}※フィボナッチ数列は「0, 1, 1, 2, 3, 5, 8, 13…」という数列で、F(0)=0、F(1)=1、F(n)=F(n-1) + F(n-2) (n >= 2)というような、前の2つの数字の合計が次の数字になるという規則があります。nが大きくなると処理が指数的に増えるため、計算量が急激に増えるので注意しましょう。
実行結果
55
コードを書く際に大事なこと
上記で代表的な計算量についてまとめましたが、計算量がO(n²)やO(2ⁿ)だと入力データのサイズが大きくなると計算量が急激に増えるということ（それによってパフォーマンス低下や処理が壊れる可能性がある）なので、その処理が将来的に入力データのサイズが大きくなる可能性があるならアルゴリズムを改善するべきです。
時間計算量と空間計算量について
上記のようなループ回数や再帰の深さによって実行にどれくらい時間がかかるかを表す計算量のことを「時間計算量（Time Complexity）」といいます。
加えて、入力そのものはカウントせず、追加でどれくらいメモリを使うか（変数、配列、スライス、map、再帰スタック、構造体など）を表す計算量のことを「空間計算量（Space Complexity）」といいます。
例えば実務などでは、大量データを扱う処理においてメモリがオーバーフローしてサーバーが落ちるということがあったりするため、時間計算量だけではなく空間計算量も意識してコードを書くのが大事になります。
最後に
今回はGo言語（Golang）とビッグオー記法（Big-O記法）による計算量について解説しました。
実務においては機能をリリースした後に利用者数が増加することでパフォーマンスが低下したり、最悪サーバーが止まるということも起こり得るため、特にその機能が将来的に大量データを扱ったりするようなことが想定される場合は、事前に対策しておくのが品質面を考慮する上でも大事かなと思います。
具体的な改善方法はケースバイケースなので、無理に覚える必要はありませんが、今回ご紹介したような『感覚』は理解しておいた方がいいでしょう。
コメント