10件で速かった処理が100万件では使えない。反対に、計算量が同じ二つの実装に大きな速度差が出ることもあります。計算量は入力が増えたときの伸び方を考える道具、ベンチマークは特定の条件で実際の時間を確かめる道具です。両方を使って、改善すべき場所を選びます。
まず何をnとするか決める
計算量を述べる前に、入力サイズを定義します。配列の要素数をnとするのか、整数の桁数をnとするのかで意味が変わります。また、数える基本操作にも仮定があります。固定幅整数の加算を一回と数えるモデルと、非常に大きな整数の各桁を処理するモデルは同じではありません。モデルは目的に合わせて明示します。
def total(values):
result = 0
for value in values:
result += value
return result
def pair_count(values):
count = 0
for x in values:
for y in values:
if x == y:
count += 1
return count一つ目はn個の要素を一回ずつ見るため、基本操作を定数時間とすれば時間はΘ(n)です。二つ目は各xについてn個のyを見るためn²回の比較となり、Θ(n²)です。nが10倍になると、支配項による仕事量は前者で約10倍、後者で約100倍になります。実時間はほかの要因も受けるため、常に厳密な倍率になるわけではありません。
Oは上界、Θは同じ程度の伸び方
O(g(n))は、十分大きなnで定数倍のg(n)を超えないという漸近的な上界です。Θ(g(n))は上下から定数倍で挟めることを表します。3n+7はΘ(n)ですし、上界としてO(n²)と書くこともできます。普段の会話ではOを代表的な伸び方の意味で使うことがありますが、厳密な説明では上界と一致する評価を区別します。
よく現れる順序は、定数、対数、線形、n log n、二次、指数です。二分探索の比較回数が対数的になるのは、一回ごとに候補をほぼ半分へ減らすからです。100万件でも約20回の比較で絞れます。ここでは整列済みで、途中の要素へ定数時間でアクセスできる、といった前提を忘れないようにします。
最悪・平均・償却は違う問い
最悪計算量は同じサイズの入力の中で最も費用が大きい場合です。平均計算量を語るには、どんな入力がどの確率で来るかを定めます。「普通は速い」だけでは平均の根拠になりません。償却解析は、操作列全体にかかった費用を各操作へならして評価します。入力のランダム性を必ずしも仮定しません。
例えば容量を倍増する動的配列では、拡張時の追加一回に要素コピーが必要でも、n回の追加全体ではコピー数の合計をO(n)へ抑えられます。この場合、追加一回は償却O(1)です。拡張が起きる特定の一回が最悪O(n)であることとは両立します。応答時間の上限が厳しい場面では、この一回の遅延も問題になります。
空間と定数倍も設計に効く
空間計算量は必要なメモリの伸び方です。入力を含む総量と、入力以外に使う補助領域を区別して示します。全要素を複製する処理は補助領域Θ(n)、合計値だけを持つ処理は通常Θ(1)です。メモリを増やして再計算を減らすなど、時間と空間の交換もあります。
同じΘ(n)でも、連続した配列を読む処理と、離れた場所をポインタでたどる処理では、キャッシュの働きが異なります。関数呼出し、文字列の割当て、入出力などの定数倍も効きます。小さな入力では単純な実装が速く、大きな入力では漸近的に有利な実装が逆転することがあります。
測定条件をそろえる
python -m timeit -s "xs = list(range(10000))" "sum(xs)"測りたい処理と準備を分け、同じ入力、同じ処理系、同じ結果を出す条件で比較します。短い処理は繰り返して測り、複数回の結果のばらつきを見ます。timeitは小さな処理の測定に便利ですが、本番の待ち時間やGC、ネットワーク負荷をそのまま再現するものではありません。実サービスでは分位点や同時実行数も重要です。
理解を確かめる
二重ループは必ずΘ(n²)か。必ずではありません。各ループの範囲や途中終了によって回数が変わります。実行回数の和を数えます。
償却O(1)の追加操作は、どの一回も定数時間か。違います。操作列全体をならした評価であり、特定の一回が高価でもかまいません。
O(n)の処理がO(n log n)より常に速いか。有限の入力では定数倍や実装条件で逆転します。入力サイズを変えて測り、伸び方も確かめます。
この単元の概念：時間計算量 償却解析 ベンチマーク
続けて読む：キャッシュとメモリ階層