ビッグオーは暗記せず、倍にして測る
一言でいうと
「この関数はO(n)です」は、暗記して言うものではなく、測って言うものです。入力を2倍にしたときに時間が何倍になるかを見れば、隠れた二次が明らかになり、繰り返し測った分布を見れば、「速くなった」がノイズなのか改善なのかを見分けられます。
なぜ必要なのか
ステージング環境で100件に0.1msだった重複除去が、本番で5万件に出会って数秒になる、ということはよくあります(例)。コードは1行も変わっておらず、テストはすべて緑でした。小さな入力では、二次の関数も速いからです。問題は「どれだけ速いか」ではなく「入力が増えたときにどう増えるか」であり、その問いには、1回の測定では答えられません。
逆に、コードの形だけを見て判断しても間違えます。二重のループでも、内側がいつも3回なら線形ですし、ループがなくif x not in seen:の1行だけでも、seenがlistなら、その1行がリストを先頭から走査します。TimeComplexityのwikiは、CPythonを基準に、listのx in s・insert・途中の要素のpopをO(n)、setのx in sを平均O(1)(最悪O(n))と記載しています。ここでnはコンテナに今入っている要素数であり、ループの中で呼ばれると掛け算になります。
どう動くのか
倍増実験: かかる時間がおよそc·n^kなら、t(2n)/t(n) ≈ 2^kです。比率が2の近くなら線形、4の近くなら二次、8の近くなら三次です。指数はlog2(比率)で読みます。n log nは、1回2倍にしたときに2をわずかに超えるだけなので、この方法では線形と見分けにくく、このラボでは線形と二次だけを分けます。サイズはn、2n、4n、8nのように何回か増やして比率を3つ得て、その中央値を代表として使います。1組だけを見ると、ノイズ1つで結論が覆ります。
時計: time.perf_counterは、短い区間を測るために最も高い分解能を提供する時計で、2回読んだ値の差だけに意味があります。CPythonでは、後戻りしない(monotonic)時計です。一方、time.time()は、システム時計が後ろへ調整されると、以前より小さい値を返すことがあると、ドキュメントに書かれています。どの時計が調整可能かは、time.get_clock_info()のadjustable・monotonicで直接問い合わせられます。
反復と代表値: 同じコードを7回測ると、7つの異なる数字が出ます。timeitのドキュメントは、反復結果の平均と標準偏差を出すことはあまり役に立たないと述べています。もっとも小さい値が、そのマシンがそのコードを実行できる下限であり、大きい値はたいてい、Pythonではなく別のプロセスの干渉によるものだからです。そこでこのラボでは、コード自体の増加率を見るとき(倍増の比率)は、最小値どうしを割ります。一方、改善の前後を比較して報告するときは、中央値と分布を一緒に書きます。statistics.medianのドキュメントにあるとおり、中央値は外れ値に左右されにくい代表値で、2つの分布が重ならない(改善後のもっとも遅いサンプルが、改善前のもっとも速いサンプルより速い)ことは、平均1組よりはるかに強い証拠です。timeitは、デフォルトでは測定中にガベージコレクションを無効にし、反復のデフォルトは5です。
測定ツールが守るべきことがもう1つあります。入力を作る時間は測りません。線形の入力作成の時間が混ざると、二次の関数の比率が4より小さく出て、二次が隠れてしまいます。また、入力を書き換える関数があるので、反復ごとに入力を新しく作ります。
隠れた二次の3つ: listに対するin、list.insert(0, x)、そしてイミュータブルなシーケンスの繰り返しの連結です。共通のシーケンス操作のドキュメントは、イミュータブルなシーケンスを連結すると常に新しいオブジェクトが作られるため、繰り返しの連結は全体の長さに対して二次のコストがかかると記し、strにはstr.join()やio.StringIO、bytesにはbytes.join()・io.BytesIO・bytearrayを代替手段として挙げています。strのa += bは、CPythonが最適化してくれる場合がありますが、PEP 8は、その最適化はCPythonでも壊れやすく、参照カウントを使わない実装にはそもそも存在しないので、当てにしないようにと述べています。このラボがstrではなくbytesを測る理由です。
直すときに守ること: 重複除去をlist(set(items))に変えると速くなりますが、setは順序のないコレクションなので、結果の順序が変わります。dictは3.7から挿入順序の保持が言語仕様なので、dict.fromkeys(items)は最初に出てきた順序を保ちます。速くなった関数が別の答えを出すなら、それは改善ではなくバグです。
現場での姿
性能改善のPRに「ローカルで1回測ったら12%速くなった」と書かれているなら、その数字はまだ何も証明していません。同じ条件で何回測ったのか、前後の分布が重なっているか、そして入力が10倍になるとどうなるかを、一緒に尋ねる必要があります。倍増実験で指数が得られれば、「今8千件で0.2秒なら、10万件では何秒か」を外挿でき、その数字をバジェットと比べて、今直すかどうかを決めます。外挿は同じ増加率が続くという仮定の上にあり、データがCPUキャッシュを超える地点では、比率自体が変わることがあります。その話は「コンピュータ構成」コースが扱います。どこが遅いのかを探すプロファイリング(cProfileのtottime・cumtime)は「CPU・メモリリークの見極め」コースが、サービス全体に負荷をかけてパーセンタイルでリグレッションを判定することは「負荷テスト」コースが扱います。このモジュールは、その間にあって、関数1つの増加率を測る場所です。
次のラボですること
2つの時計の性質をPodに直接問い合わせたあと、反復・中央値・最小値を出す測定ツールを作ります。計算量が隠れている関数5つを4つのサイズで測って、比率と指数を求め、線形と二次に分けます。もっとも一般的な二次である重複除去を、順序を保ちながら直し、改善の前後を分布で比較したあと、10万件で何秒かかるかを外挿して、バジェットと比べます。