背景
2025/2/15に実施された第66回横浜Go読書会（オンライン)に参加して、ソフトウェア開発における計算量について知ったので、
アウトプットしつつ自身の理解を深めようと思いました。
内容
今日読んだ本は効率的なGo ―データ指向によるGoアプリケーションの性能最適化の７章「データ駆動効率性評価」で、計算量についての話が書かれていました。計算量には漸近的計算量と推定計算量があります。
漸近的計算量
漸近的計算量とはO記法で表記される計算量を指し、以下の特徴があります。
- 入力サイズに関連して実行時間や空間の需要がどれだけ速く成長するかに注目する
- ハードウェアや環境のオーバーヘッド（式の定数項）を無視する
- 複雑な問題を解決するアルゴリズムを探す研究者にとって重要
O記法についてはDonald Knuthが1976年の論文で３つの表記法を定義しています。
上界(O)
O(f(n))と書いた場合、関数がf(n)よりも漸近的に悪く(大きく) なることがないことを意味します。
タイトな限界(Θ)
Θ(f(n))と書いた場合、正確な漸近関数、あるいは平均的、典型的なケースを意味します。
下界(Ω)
Ω(f(n))と書いた場合、関数が漸近的に良く（小さく）なることがないことを意味します。
ビッグオー表記が必ずしも正しく使われているとは限らず、面接等で、典型的なケースを説明するためにΘを使うべきところをOを使っていることがあります。クイックソートはO(N×logN)と言われるが、Ω(N×logN)もしくはO(N×logN)であって、最悪の場合はO(N^2)になります。
推定計算量
漸近的計算量とは違って式の定数項を無視しない計算量です。ただの計算量とも呼ばれます。空間計算量(space complexity)を例に挙げて説明します
次のようなSum関数を考えます。
func Sum(fileName string) (ret int64, _ error) {
b, err := os.ReadFile(fileName)//⭐️1
if err != nil {
return 0, err
}
for _, line := range bytes.Split(b, []byte("\n")) {//⭐️2
num, err := strconv.ParseInt(string(line), 10, 64)//⭐️3
if err != nil {
return 0, err
}
ret += num
}
return ret, nil
}
上記のSum関数の空間計算量(ヒープ割当てサイズ)の推定計算量は以下で表されます。
space(N) = (848 + 3.6 × N) + (24 + 24 × N) + (2.8 × N)
= 872 + 30.4 × N [bytes]
N: 入力ファイル中の整数の数
⭐️1 848 + 3.6 × Nの部分はファイルの内容を読み込む操作に必要なヒープサイズの推定計算量です。os.ReadFile(fileName)で読み込まれるファイルは以下のような改行区切りで数値が書かれたファイルを想定しています。読み込まれるファイルの整数の桁数は平均して2.6桁で各行に改行\n 1byteを追加するので、3.6 × N byteになります。848byteとはos.ReadFile関数でヒープ上に割り当てられた様々なオブジェクトに由来します。
123
45
67
⭐️2
定数の最大値は24byteで、N個のbyteスライスをヒープに確保するために、24×N byteのヒープサイズが必要です。また、[][]byte(byteスライスのスライス)を持つためには、[]byteのスライスヘッダを持たなければいけないので、24byte必要です。したがって、 (24 + 24 × N)bytes必要です。
⭐️3
平均して2.6桁の数値に対してN回のstrconv.ParseInt(string(line), 10, 64)行うので、
(2.6 × N)のヒープサイズが必要。(0.2 × N)の部分は不明だが+αのサイズが必要で、合計(2.8 × N)となります。
上記の推定計算量はNが十分大きければ
space(N) ≃ 30.4 × N [bytes]
となり、漸近的計算量と呼ばれます。この場合、空間計算量はNに比例します。
space(N) = 872 + 30.4 × N [bytes]
一方、上記のような定数項を無視しない、空間計算量は推定計算量と呼ばれます。
推定計算量と漸近的計算量が区別できると何が嬉しいのか？
まず推定計算量・漸近的計算量を計算することで以下のメリットがあると書かれています。
- 正確な計算量がわかっていなくても予想されるリソースの必要量を判断できる
- コードの最適化が簡単にできるかどうかを教えてくれる
- 最適化としてより良いアルゴリズムのアイデアを評価するのに役立つ
上記に加えて、推定計算量・漸近的計算量を区別することで、ざっくりと計算量のオーダーを意識するのではなく、入力サイズに応じてより厳密に計算量を見積もることができるのだと個人的には解釈しました。
所感
- ビッグオー表記が正しく使われない、クイックソートはO(N×logN)と言われるがワーストケースはO(N^2)である。みたいな話は自分も面接や仕事で経験したことがあります。厳密な数学的定義を知っていると、前提を正しく捉えることができて、妥当な計算量を求めることができることがあるという話だと理解しました。
- 読書会内で、この章の計算量の話は小難しく話をしているだけで、アルゴリズムの比較やパフォーマンス測定・チューニングを業務でしたことがあるエンジニアなら知っているのではないかという話が出ました。それはある意味でYESだと思います。一方で、個人的には当たり前に思えるようなことを厳密により一般的に理論立てて説明しようとすると、数学を使ってより厳密に記述することになり、結果として計算量の前提となる入力サイズを強く意識することに繋がると思いました。
- 実際の業務においては推定計算量を出そうとするよりもサクッと測定してしまって比較した方が早いケースも多いような気がします。でも、場合によって使い分けられるように理論的な面も実践面も両方知っておくと良いのではと思いました。