計算量に注目してプログラムを高速化する

はじめに

概要

• アルゴリズムの計算量に注目して、プログラムを高速化する方法を紹介する
• 計算量の概要と求め方、下げ方を練習問題を通して説明する
• 計算量を下げると、データ数が増えても性能が劣化しづらくなることを示す

※この文書はC#を対象に書いているが、他言語でも考え方は同じ。

目的

• データ数が増えても性能が極端に劣化しないコードを書けるようにする
• コードレビューで性能に関する問題を発見し、改善を提案できるようになる

目標

• コードの計算量を導き出せるようになる
• 計算量を下げるための２つのアプローチを知る

対象者

• 基本的なデータ構造やアルゴリズムをある程度抑えている人
• 扱うデータ数が多いコードを書くことがある人
• プログラムの静的テスター（コードレビュアー）

計算量のはなし

そもそもなんで計算量？

• 計算量を意識すると、データ数が増えても速度が低下しにくいコードを書けるようになる。
• 計算量を見積もることができれば、コードをレビューする時に潜在的なパフォーマンス問題に気づけるようになる。

計算量とは

計算量(complexity)とはアルゴリズムの計算時間を評価するための指標で、「データの数」が増えたら「計算時間」はどう増えるかを表す。O （ビッグオーとかランダウとか）で表記する。

なお、計算量は計算時間だけではなくメモリ使用量にも使うが、この文書内では単に計算量と言ったら計算時間のことを指す。

計算量の例	意味
O(1)	データ数によらず一定時間で処理が完了する	小
O(log N) ※	データ数の2進対数に比例して処理時間が増える	↑
O(N)	データ数に比例して処理時間が増える	↓
O(N^2)	データ数の2乗に比例して処理時間が増える	大

※logは2を底とする対数
※O-表記においてlogの底は任意。底の変換により定数に置き換えられるので。一般的なデータ構造やアルゴリズムでは底が2のことが多いが、2に限らない（子が3つのTreeなど）

計算量が O(N log N) 以下であれば高速、O(N^2)以上は性能上の問題を抱える可能性がある。ただし、計算量はあくまで「データ数」と「計算時間」の関係を表しているだけであり、必ずしもO(1)のアルゴリズムがO(N)のアルゴリズムよりも早く終わるということ言ってるわけではない。

O表記の補足

定数はけす：Ｏ(3N) ⇒ O(N)
次数が小さいやつはけす：Ｏ(N^2 + N) ⇒ Ｏ(N^2)

どうやって計算量を求めるの？

「ループのネスト数」と、そのループの中で使ってる「APIの計算量」に注目するとだいたいわかる。この後にある練習問題で分かって。

身近な処理の計算量

計算量の例	意味
O(1)	ハッシュテーブルのアクセス（衝突なし）
O(log N)	二分探索
O(N)	ループ、線形探索
O(N log N)	標準APIが提供するソートアルゴリズム ※
O(N^2)	二重ループ

※N^2の場合もあるが、N log Nで覚えておけばだいたい問題ない。

System.Collections.Generic クラス達の計算量

データ構造	Add	Get	Remove	Contains
Array	-	O(1)	-	O(N)
List<T>	O(1)	O(1)	O(1) : RemoveAt O(N) : Remove	O(N)
Dictionary<TKey, TValue>	O(1)	O(1)	O(1)	O(1) : ContainsKey O(N) : ContainsValue
SortedDictionary<TKey, TValue>	O(log N)	O(log N)	O(log N)	O(log N) : ContainsKey O(N) : ContainsValue
HashSet<T>	O(1)	-	O(1)	O(1)
Queue<T>	O(1) : Enqueue	O(1) : Dequeue	-	O(N)
Stack<T>	O(1) : Push	O(1) : Pop	-	O(N)

※各操作の計算量はMSDNに明記されている

練習問題

問題１．このコードの計算量は？

// 緑の果物を特定するプログラム

// GetFruits() と GetGreenFoods() は O(1)で、
// だいたいN個の文字列を返すことが想定されるらしい
string[] fruits = GetFruits();
string[] greenfoods = GetGreenFoods();

var greenfruits = new List<string>();
foreach (var fruit in fruits)
{
    if (greenfoods.Contains(fruit))
    {
        greenfruits.Add(fruit);
    }
}

問題1．答え

答えはO(N^2)

Array.Containsの計算量はO(N)で、それがNのループの中にあるからO(N^2)となる。
よく見かけるパターンだが、データ数が増えるとクッソ重くなるコードである。

問題2．このコードの計算量は？

// 緑の果物を特定するプログラム
/
// GetGreenFoods() は O(1)で、
// だいたいN個の文字列を返すことが想定されるらしい
string[] fruits = new []{"avocado", "banana", "cherry"};
string[] greenfoods = GetGreenFoods();

var greenfruits = new List<string>();
foreach (var fruit in fruits)
{
    if (greenfoods.Contains(fruit))
    {
        greenfruits.Add(fruit);
    }
}

問題2．答え

答えはO(N)

foreachのループ回数は3回なので 3N。O表記では定数は省くのでO(N)となる。
ループがあるからと言ってNが増えるとは限らない点に注意。

コードの計算量を下げる

ここでは計算量を下げてプログラムを高速化する手法を紹介する。

実際の高速化では、プロファイラを使ってボトルネックを特定するとか、高速化の方法は計算量を下げるだけというわけでもないとか、いろいろあるがそれはまた別の機会に。

計算量を下げる方法

計算量を下げる主な方法は２種類
* 適切なデータ構造を使用するように変更する
* アルゴリズムを見直す

練習問題

問題：このプログラムの計算量をさげて高速化しろ

// 緑の果物を特定するプログラム

// GetFruits() と GetGreenFoods() は O(1)で、
// だいたいN個の文字列を返すことが想定されるらしい
string[] fruits = GetFruits();
string[] greenfoods = GetGreenFoods();

var greenfruits = new List<string>();
foreach (var fruit in fruits)
{
    if (greenfoods.Contains(fruit))
    {
        greenfruits.Add(fruit);
    }
}

答え１：適切なデータ構造を使う方法

Array.Contains は O(N) である。
Array の代わりに Contains が O(1) の HashSet<T> を使用すれば、計算量を下げられる。

// 緑の果物を特定するプログラム

string[] fruits = GetFruits();
HashSet<string> greenfoods = new HashSet<T>(GetGreenFoods());

var greenfruits = new List<string>();
foreach (var fruit in fruits)
{
    if (greenfoods.Contains(fruit)) // HashSet<T>を使うとここが O(1) になる
    {
        greenfruits.Add(fruit);
    }
}

これでこのプログラムの計算量はO(N)となった。

答え２：アルゴリズムを見直す

greenfruitsはfruitsとgreenfoodsの集合積であると考えるようにする。
集合演算にはHashSet<T>(またか！)が使える。

// 緑の果物を特定するプログラム
HashSet<string> tmp = new HashSet<string>(GetFruits());
tmp.IntersectWith(GetGreenFoods());

var greenfruits = new List<string>(tmp);

計算量が O(N) になっただけでなく、コードもすっきりした！

※HashSetは要素の重複を許容しないので、この変更は仕様を変えてしまっている可能性があるけど許して。

※IEnumerable<T>.Intersectを使っても良いかもしれない。

測定結果

データ数	元コード	答え１	答え２
1000	8 ms	1 ms	1 ms
10000	365 ms	6 ms	7 ms
100000	37182 ms	65 ms	70 ms

元コードがデータ数が10倍になると計算時間が約100倍(データ数増加の2乗分)になっているのに対して、答え１と２では約10倍に抑えられている。

計算量を下げるとプログラムが高速化することがこの結果からもわかる。

※O(N^2)は、やばい。

まとめ

• プログラムの大まかな計算量は、ループの深さと、アルゴリズムとデータ構造の計算量をかけ合わせれば導き出せる。
• プログラムの計算量を下げるには、適切なデータ構造を使用するよう変更するか、アルゴリズムを見直す。アルゴリズムを見直すには発想が必要だけど、データ構造を変えるだけならある程度機械的にできるのでお手軽かも。
• 計算量を下げると、データ数が増えても速度が低下しにくくなる。

次のステップのためのキーワード

• 計算複雑性理論
• 代表的なアルゴリズムの計算量
• 代表的なデータ構造の計算量
• 計算量以外のパフォーマンス最適化手法