関数型プログラミング 補足A 計算量とデータ構造の性能
資料
本編では, 代数 (法則) を持つ型を使うと 最適化ができる という話を繰り返してきました. たとえば 第3章 の「String は非効率」, 第7章 の「Data.Set は計算量の面で有利」, 第8章 の「stimes は繰り返し二乗法で速い」「1 パスで集計できる」「結合律で並列化できる」などです.
ところが「速い」「非効率」「有利」を実感するには, 何を基準に速い・遅いを測るのか という物差しが要ります. その物差しが 計算量 (computational complexity) と, データ構造ごとの性能特性 です. この補足章は, 本編の最適化の話を理解するために必要な最小限の道具だけを, 直感重視で用意します. アルゴリズムとデータ構造の体系的な学習は専門の教科書に譲り, ここでは「本編の主張を裏づけられる」ところまでに絞ります.
オーダー記法 — 「速さ」を測る物差し
問いは「入力が 2 倍になったら時間はどうなるか」
プログラムの速さを「1 回動かして何秒だった」で測ると, 機種・言語・その日の負荷で数字が変わってしまい, アルゴリズムそのものの良し悪しが見えません. そこで注目するのは絶対時間ではなく, 入力の大きさ n を増やしたときに, 実行時間がどう伸びるか という「伸び方」です.
たとえば要素数 n のリストから, ある値が入っているかを先頭から順に調べる関数を考えます. n が 2 倍になれば, 最悪の場合に調べる回数もおよそ 2 倍になります. このように「n に比例して伸びる」ことを O(n) と書きます. 一方, ソート済みの構造を二分探索するように「n が 2 倍でも手間は 1 段増えるだけ」なら O(\log n) です.
この「伸び方」だけに注目し, 定数倍と, 小さい項を捨てる のがオーダー記法 (ビッグオー記法) です. たとえば 3n + 100 も n も, n を 2 倍にすればほぼ 2 倍になるという意味では同じ伸び方なので, どちらも O(n) と書きます. 定数倍 (3 や 100) は機種や実装で変わる一方, 伸び方は変わらない ため, アルゴリズムの本質的な優劣を表せるのです.
よく出る 5 つのオーダー
| 記法 | 呼び方 | 入力が 2 倍になると | 典型例 |
|---|---|---|---|
| O(1) | 定数時間 | 変わらない | リストの先頭を取る, 配列の添字アクセス |
| O(\log n) | 対数時間 | 手間が 1 段増えるだけ | 二分探索, Data.Set の検索 |
| O(n) | 線形時間 | 約 2 倍 | リストの線形探索, sum, length |
| O(n \log n) | 準線形 | 約 2 倍と少し | 効率的なソート |
| O(n^2) | 二乗時間 | 約 4 倍 | 全要素の総当たり比較 |
伸び方の違いは, n が大きくなるほど劇的になります.
| n | \log_2 n | n | n \log_2 n | n^2 |
|---|---|---|---|---|
| 10 | 約 3 | 10 | 約 33 | 100 |
| 1{,}000 | 約 10 | 1{,}000 | 約 10{,}000 | 1{,}000{,}000 |
| 1{,}000{,}000 | 約 20 | 1{,}000{,}000 | 約 2{,}000 万 | 1 兆 |
n = 100 万のとき, O(\log n) はたった 20 段ですが, O(n^2) は 1 兆回に達します. 「オーダーを 1 段下げる」ことが, 現実的な時間で終わるかどうかを分ける — これが最適化を気にする理由です.
最悪・平均・最良. 同じ関数でも, 入力の中身によって手間は変わります (探している値が先頭にあれば線形探索でも 1 回で済む). 断りなくオーダーを書くときは, ふつう 最悪の場合 を指します. 本章でもその流儀に従います.
ソートで計算量を確かめる
オーダー記法は「伸び方」を予言します. 本当にその通りになるのか, Haskell のソートを 3 つ書き, 要素どうしを比較した回数を数えて 確かめてみましょう. ソートは, 入力サイズ n (要素数) による計算量の違いが最もはっきり出る題材です.
3 つのソート
まず 3 つのソートを実装し, それぞれ どんな手順で並べ替えているか を小さな具体例で追いかけます.
挿入ソート (insertion sort)
すでに整列した列へ, 要素を 1 つずつ正しい位置に挿し込みます. トランプを手札に並べる要領です. 第5章 では明示再帰で insertionSort (x:xs) = insert x (insertionSort xs) と書きました. これを高階関数 foldr で書き直すと次の 1 行になります (同じ関数です).
insertionSort :: Ord a => [a] -> [a]
insertionSort = foldr insert []
where
insert x [] = [x]
insert x (y:ys)
| x <= y = x : y : ys
| otherwise = y : insert x ys手順.
- 整列済みリストを空
[]から始める. - 入力から要素を 1 つ取り出す (
foldrなので 右端から). - その値を整列済みリストの先頭から順に比べ, 自分以上の要素が現れたらその直前に挿し込む (
insert). - 入力がなくなるまで 2–3 を繰り返す.
入力 [4,2,5,1,3] を並べ替える様子です. foldr は右端から畳むので, 末尾の 3 から順に挿し込みます.
挿す値 整列済みリスト 説明
(start) []
3 [3] 空なのでそのまま
1 [1,3] 1 <= 3 なので先頭へ
5 [1,3,5] 5 は最大, 末尾へ
2 [1,2,3,5] 1 の後, 3 の直前へ
4 [1,2,3,4,5] 3 の後, 5 の直前へ ← 完成整列済みリストが常にソートされているので, 各挿入は自分の居場所を探すだけで済みます. 逆順の入力では毎回いちばん奥まで比べることになり, これが最悪 O(n^2) の原因です.
マージソート (merge sort)
列を半分に割り, それぞれを整列してから併合 (merge) します. 典型的な 分割統治 です.
mergeSort :: Ord a => [a] -> [a]
mergeSort [] = []
mergeSort [x] = [x]
mergeSort xs = merge (mergeSort l) (mergeSort r)
where
(l, r) = splitAt (length xs `div` 2) xs
merge [] ys = ys
merge xs [] = xs
merge (x:xs) (y:ys)
| x <= y = x : merge xs (y:ys)
| otherwise = y : merge (x:xs) ys手順.
- 要素が 1 個以下ならそれ自体が整列済み (再帰の底).
- そうでなければ列を中央で 2 つに割る (
splitAt). - 各半分を再帰的にマージソートする.
- 整列済みの 2 列を, 先頭を比べて小さい方から取り出し 1 列に併合する (
merge).
入力 [5,2,4,7,1,3,8,6] を, まず 半分ずつ割り (上から下へ), 1 要素になったら 併合しながら戻り ます (下から上へ).
分割 (半分ずつ):
[5,2,4,7,1,3,8,6]
/ \
[5,2,4,7] [1,3,8,6]
/ \ / \
[5,2] [4,7] [1,3] [8,6]
/ \ / \ / \ / \
[5] [2][4] [7] [1] [3][8] [6]
併合 (小さい方から取り出す):
[5] [2] -> [2,5]
[4] [7] -> [4,7]
[2,5] [4,7] -> [2,4,5,7]
[1] [3] -> [1,3]
[8] [6] -> [6,8]
[1,3] [6,8] -> [1,3,6,8]
[2,4,5,7] [1,3,6,8] -> [1,2,3,4,5,6,7,8]割るたびに列は半分になるので深さは \log_2 n 段. 各段の併合で全体をひとなめ (O(n)) するため, 合計 O(n \log n). 入力の並びによらずこの段数なので, 最悪でも O(n \log n) を保ちます.
クイックソート (quicksort)
先頭を軸 (pivot) に選び, 残りを「軸以下」と「軸より大」に振り分け, 各々を再帰的に整列します.
import Data.List (partition)
quickSort :: Ord a => [a] -> [a]
quickSort [] = []
quickSort (p:xs) = quickSort smaller ++ [p] ++ quickSort larger
where (smaller, larger) = partition (<= p) xs -- 1 要素につき軸と 1 回比較手順.
- 空ならそのまま (再帰の底).
- 先頭を軸 (pivot) に選ぶ.
- 残りを「軸以下」と「軸より大」の 2 群に振り分ける (
partition). - 各群を再帰的にクイックソートする.
整列した軸以下 ++ [軸] ++ 整列した軸より大と連結する.
入力 [5,2,4,7,1,3,8,6] の再帰です (軸=p: <=群 | p | >群). 軸が左右をだいたい半々に分ける限り, 木の深さは約 \log n 段です.
quickSort [5,2,4,7,1,3,8,6]
軸=5: <=[2,4,1,3] | 5 | >[7,8,6]
├ quickSort [2,4,1,3]
│ 軸=2: <=[1] | 2 | >[4,3]
│ ├ [1]
│ └ quickSort [4,3] 軸=4: <=[3] | 4 | >[] -> [3,4]
│ => [1,2,3,4]
└ quickSort [7,8,6]
軸=7: <=[6] | 7 | >[8] -> [6,7,8]
結果: [1,2,3,4] ++ [5] ++ [6,7,8] = [1,2,3,4,5,6,7,8]軸選びが悪い (毎回いちばん小さい/大きい要素を選ぶ) と, 片側が空でもう片側が n-1 個に偏り, 木が縦に n 段伸びて O(n^2) に劣化します. 整列済みの入力 に先頭軸を使うと, まさにこれが起きます.
3 つとも結果は同じ (昇順に整列) ですが, 手間の伸び方が違います.
| ソート | 最良 | 平均 | 最悪 |
|---|---|---|---|
| 挿入ソート | O(n) (整列済) | O(n^2) | O(n^2) (逆順) |
| マージソート | O(n \log n) | O(n \log n) | O(n \log n) |
| クイックソート | O(n \log n) | O(n \log n) | O(n^2) (軸が毎回偏る) |
比較の回数を数える
計算量を確かめるには, 実行時間ではなく 要素どうしを何回比較したか を数えるのが確実です (比較 1 回の手間はほぼ一定なので, 比較回数がそのままオーダーの形になります). ソートに「比較したら 1 を足す」計器を仕込みます. 挿入ソートなら, 結果に加えて比較回数 Int を返すよう書き換えます.
insertionSortC :: Ord a => [a] -> (Int, [a])
insertionSortC = foldr step (0, [])
where
step x (c, s) = let (c', s') = insertC x s in (c + c', s')
insertC x [] = (0, [x])
insertC x (y:ys)
| x <= y = (1, x : y : ys) -- 1 回比較して確定
| otherwise = let (c, zs) = insertC x ys in (c + 1, y : zs)マージソート・クイックソートにも同じ要領で計器を仕込めます (完全なコードは検証用 spec にあります). これらで, 入力サイズ n を 4, 8, 16, 32, 64 と 2 倍ずつ増やしながら比較回数を測ると, 次の表が得られます.
| n | 挿入 (逆順=最悪) | n(n-1)/2 | マージ | クイック (整列済=最悪) | クイック (散在) |
|---|---|---|---|---|---|
| 4 | 6 | 6 | 4 | 6 | 5 |
| 8 | 28 | 28 | 12 | 28 | 19 |
| 16 | 120 | 120 | 32 | 120 | 71 |
| 32 | 496 | 496 | 80 | 496 | 271 |
| 64 | 2016 | 2016 | 192 | 2016 | 1055 |
読み取れることが 3 つあります.
- 挿入ソート (最悪) は厳密に n(n-1)/2. 逆順の列では, k 番目に挿す要素が既存の全部より大きいので k-1 回比較し, 合計は 0 + 1 + \cdots + (n-1) = n(n-1)/2 = O(n^2). 表の 2 列目と 3 列目がぴったり一致しています.
- n を 2 倍にしたときの伸び方が, オーダーを裏づける. 挿入 (最悪) は 28 \to 120 \to 496 \to 2016 と, 2 倍ごとに約 4 倍 (=2^2) — これが O(n^2) の指紋です. 一方マージは 12 \to 32 \to 80 \to 192 と約 2.4 倍 (n を 2 倍にしても比較はおよそ 2 倍強) で済みます — O(n \log n) の伸び方です. n = 64 では 2016 対 192 で 10 倍以上の差になります.
- クイックソートは入力次第で豹変する. 散在した (整列も逆順もしていない) 入力では平均的に O(n \log n) (n = 64 で 1055) ですが, すでに整列済みの入力 を与えると軸が毎回最小要素になり, 挿入ソートの最悪と同じ n(n-1)/2 = O(n^2) に劣化します (整列済列で 2016). 「平均は速いが最悪は遅い」— オーダー記法 の節で触れた最悪と平均の区別が, ここに現れます.
実務では自前のソートは書かない. 標準の Data.List.sort は O(n \log n) で安定な, 実用に耐えるマージソート系の実装です. ここで自作したのは, あくまで 計算量の違いを目で見る ためです.
import Data.List (sort)
example = sort [3,1,4,1,5,9,2,6] -- [1,1,2,3,4,5,6,9]データ構造ごとの性能特性
同じ「集まり」を表すのでも, どのデータ構造を選ぶかで各操作のオーダーが変わります. 本編で「String は非効率」「Set が有利」と言えたのは, この違いがあるからです.
| 構造 | 要素の検索 | 先頭に追加 | 連結・挿入 | 特徴 |
|---|---|---|---|---|
list ([a]) |
O(n) | O(1) (:) |
++ は O(左の長さ) |
順序あり, 重複可, 連結リスト |
Data.Set |
O(\log n) | — | insert O(\log n) |
重複を自動排除, 整列 |
Data.Map |
キーで O(\log n) | — | insert O(\log n) |
キー → 値の対応 |
String ([Char]) |
O(n) | O(1) | ++ は O(n) |
Char の連結リスト. メモリ・定数倍が大 |
Data.Text |
O(n) | — | 定数倍が小さい | 文字を配列にパック. 実務の既定 |
いくつか読み解きます.
第7章 の「
Data.Setは計算量の面で有利」: リストで要素の存在を確かめると先頭から総なめで O(n) です.Data.Setは内部が平衡二分木なので O(\log n) で検索できます. n = 100 万なら, 100 万回と 20 回の差です. 「集合として使いたい (存在判定・和積差) 」場面でリストを使うと, この差がそのまま遅さになります.第3章 の「
Stringは非効率」: ここは少し微妙です.Stringは[Char]そのもの, つまり 1 文字ごとに連結リストのセルを 1 つ確保します. 検索も連結もData.Textと オーダーは同じ ですが, 1 文字あたりのメモリと定数倍が大きく違います. つまり オーダーが同じでも定数倍で大きく負ける 例で, 「オーダーだけ見ればよい」わけではないことも教えてくれます. だからこそ, 文字列を多用する実務では最初からData.Textが推奨されます.
なぜ関数型では連結リストが基本なのか. list は先頭への追加 : が O(1) で, かつ元のリストを壊さずに共有できます (不変データ構造). そのため再帰と相性がよく, 本編ではまずリストを使います. ただし「途中の検索」や「末尾への追加」が多い用途では, 上の表のとおり Set / Map / Text に切り替えるのが定石です.
代数の法則が最適化を可能にする仕組み
ここまでの物差しで, 第8章 の「代数のインスタンスにすると速くできる」を読み直します. 鍵は 結合律 (a \bullet b) \bullet c = a \bullet (b \bullet c) で, これは「括弧を好きに組み替えてよい」という許可証でした. その許可が, 次の 3 つの高速化を可能にします.
(1) 繰り返し二乗法 — O(n) を O(\log n) へ
同じ値を n 個つなぐ \underbrace{x \bullet x \bullet \cdots \bullet x}_{n} (第8章の stimes n x) を考えます. 素直に左から 1 つずつ繋ぐと n - 1 回の演算, つまり O(n) です.
ところが結合律があれば, 括弧を組み替えて 半分ずつまとめる ことができます.
x^{8} = ((x \bullet x) \bullet (x \bullet x)) \bullet ((x \bullet x) \bullet (x \bullet x))
まず x^2 = x \bullet x を作り, それを二乗して x^4, さらに二乗して x^8 — と, 1 回の演算で「個数を 2 倍」にできます. 必要な演算回数は n を 2 倍にしても 1 回増えるだけなので O(\log n) です. これが stimes の既定実装が使う 繰り返し二乗法 です. n = 100 万個つなぐとき, 100 万回が約 20 回になります.
結合律がなければこの組み替えは許されません. 括弧の位置を変えると結果が変わってしまうからです. 「速くしてよい」ことを保証しているのは, まさに代数の法則です.
(2) 1 パス集計 — 走査回数を減らす
リスト xs の要素数と合計を両方ほしいとき, (length xs, sum xs) と書くと xs を 2 回 たどります. 走査は O(n) なので, 全体は O(2n), つまりデータを 2 度読みます.
第8章の Stats や Moments のように, 件数・合計・二乗和を 1 つのモノイドに束ねる と, foldMap の 1 回の走査で全部が同時に得られます. データを 1 度読むだけの O(n) です. 束ねる集計を増やしても (平均・分散・歪度…) 走査は 1 回のまま — これが「1 パス集計」で, 全データをメモリに保持せず流しながら計算する ストリーミング統計 の土台になります.
ここで効いているのは, 「モノイドの直積はまたモノイド」「準同型の組もまた準同型」という代数の性質です. 複数の集計を 1 つの型に 正しく 束ねられることが, 法則によって保証されています.
(3) 分割統治と並列化
結合律は「括弧を組み替えてよい」なので, 大きな集計を 木の形 に分けて畳めます (先ほどの マージソート も, 列を半分に割って畳むこの分割統治の一例です).
a \bullet b \bullet c \bullet d \;=\; (a \bullet b) \bullet (c \bullet d)
左辺は左から順に 3 回, 直列にしか計算できません. 右辺は (a \bullet b) と (c \bullet d) を 同時に (並列に) 計算し, 最後に 1 回合流させられます. データを k 個の塊に分ければ, 木の深さ O(\log k) の段数で畳めます. 大規模分散処理の MapReduce は, まさにこの「結合的な演算で部分結果を合流させる」考え方です.
並列には結合律, 並べ替えには可換律. 塊を 順番どおり 隣接ペアで合流するだけなら結合律で十分です. 部分結果を 任意の順序 で畳むフレームワークでは, さらに可換律 a \bullet b = b \bullet a が要ります. 加算ベースの Stats / Moments は可換なのでどちらでも安全ですが, 文字列連結のような非可換モノイドは「並列化はできても並べ替えは不可」です. どこまで最適化してよいか が, 型の満たす法則で決まります.
まとめ
- オーダー記法は「入力が 2 倍になったとき時間がどう伸びるか」を, 定数倍を捨てて表す物差し. O(\log n) \ll O(n) \ll O(n^2) の差は n が大きいほど劇的.
- 比較回数を数えれば計算量は目で確かめられる. 挿入ソート (最悪) は n 2 倍で比較 4 倍 (O(n^2)), マージソートは約 2.4 倍 (O(n \log n)). クイックソートは入力次第で O(n \log n) にも O(n^2) にもなる.
- データ構造の選択でオーダーが変わる. 検索が多いならリスト (O(n)) より
Set/Map(O(\log n)). 文字列はData.Text(オーダー同じでも定数倍が小さい). - 代数の法則が最適化の許可証. 結合律があるからこそ, 繰り返し二乗法 (O(n) \to O(\log n))・1 パス集計 (走査 2 \to 1)・分割統治/並列 が「結果を壊さずに」できる.
本編に戻るときは, 次の対応を意識すると腑に落ちます.