達人プログラマーを熟読中、今まで考えないようにしていた計算量の見積もりが出てきたのでメモ
規模のスケールでそのアルゴリズムのパフォーマンスはどう変化するか？
- データを200万回追加しました。
- 毎日1000件データが増えます。
- サービスは2019年の3月までがサポート予定です。
などなど、処理の内容は変わらないが、処理対象の規模が変動するのが一般的だと思う。
プログラマーなら現在のシステムの処理速度がどのように変化するか？という点を常に意識したい。
単純なループ
O(n)
基本は1からnまでの繰り返し
具体例としては、
- 順次検索
- 配列の最大値取得
- チェックサムの生成
- forループの中でSQLを実行する(ぐるぐる系)
- テーブルのフルスキャン
等
データの量に応じて処理時間は比例の関係にある。
ネストしたループ
O( n^2 )
1からnまでのループと1からmまでのループがネストしている場合、は$O(n*m)$となる
具体例としては
- バブルソート
- nestd loop join
等
二分割
O( log(n) )
2分木を活用するような処理を含む場合、計算量は対数($log$)に近いものになる
具体例としては
- インデックススキャン
- 2分木探索
処理規模が大きくなっても、処理コストが$O(n)$より増えにくいという特性を活かして、DBでは一般的にBTree indexを活用している。
| n | n^2 | log2(n) |
|---|---|---|
| 1 | 1 | 0 |
| 2 | 4 | 1 |
| 3 | 9 | 1.5849625007 |
| 4 | 16 | 2 |
| 5 | 25 | 2.3219280949 |
| 100 | 10000 | 6.6438561898 |
| 1000 | 1000000 | 9.9657842847 |
| 10000 | 100000000 | 13.2877123795 |
小規模の場合、$O(n)$に負ける場合があるが規模がスケールする可能性があるなら採用する価値はある
分割統治法
O(n log(n))
入力を分割し、それら2つをそれぞれ独立したものとして操作した後、結果を結合するようなアルゴリズムは$O(n log(n))$となる。具体例は分割したグループを再帰的にソートするクイックソート(平均)等
組み合わせ
O(C^n)
1から5までの順列をの組み合わせは？$5!=5*4*3*2*1=120$という風にパターンは120となる
6までの組み合わせ、7までの組み合わせとスケールしていくと組み合わせパターンは
6倍、42倍と増えていく。計算が現実的でないときは規模を小さくしたり、近似で妥協する。
一般的にこれらの問題は組合せ爆発と呼ばれる
例
- 巡回セールスマン問題
- ナップサック問題
- ハミルトン閉路問題
結論
組合せ爆発を避けつつスケールにに強い最適なシステムが作れるのが理想。
オマケ(各計算量の増減の比較1~10まで)
| 単純ループ – n | ネストループ – n^2 | 2分割 – log(n) | 分割統治 – n*log(n) | 組み合わせ – n! |
|---|---|---|---|---|
| 1 | 1 | 0 | 0 | 1 |
| 2 | 4 | 1 | 2 | 2 |
| 3 | 9 | 1.5849625007 | 4.7548875022 | 6 |
| 4 | 16 | 2 | 8 | 24 |
| 5 | 25 | 2.3219280949 | 11.6096404744 | 120 |
| 6 | 36 | 2.5849625007 | 15.5097750043 | 720 |
| 7 | 49 | 2.8073549221 | 19.6514844544 | 5040 |
| 8 | 64 | 3 | 24 | 40320 |
| 9 | 81 | 3.1699250014 | 28.529325013 | 362880 |
| 10 | 100 | 3.3219280949 | 33.2192809489 | 3628800 |
スケールが起こった場合、2分木をつかったアルゴリズムが如何に優秀かイメージが付くと思う
DBやSQLのチューニングをするときは心がけたい。