コンテンツへスキップ
Topos Uranos
日本語

アルゴリズムのコスト

要約

ここまでこのコースは、アルゴリズムをただ一つの問いで判断してきた。言ったとおりのことをするか？　このレッスンは二つ目の問いを加える。正しいプログラムが実際に役立つかどうかを決める問い、すなわち、どれだけのコストがかかるか？　である。コストはまず時計を使わずに、支配的な演算が何回実行されるかを数えることで測られ、データのサイズ nn の関数になる。この関数で大事なのは、与えられた nn での値ではなく、どのように増えるかである。nn、nlog⁡nn \log n、n2n^2、2n2^n の表を見ると、アルゴリズムの違いは、データが十個では見えないが、百万個では深い溝になることがわかる。OO 記法は、形式的な定義なしに、これらの増加のオーダーの略記として導入され、コースですでに見た例が添えられる。ユークリッドの互除法は対数、ベクターの総和は線形、すべての組の比較は 2 乗、素朴なフィボナッチは指数である。続いて <chrono> の時計 std::chrono::steady_clock で測定し、一回の測定がなぜ人を欺くのか、なぜ最適化を有効にしサニタイザなしで測るのか、測定を予測とどう突き合わせるのかを学ぶ。nn を 2 倍にすると、線形のアルゴリズムは時間が 2 倍になり、2 乗のアルゴリズムは 4 倍になる。

学習目標

  1. 一重または二重のループをもつアルゴリズムの支配的な演算を、データのサイズ nn の関数として数えることができる。
  2. アルゴリズムを定数、対数、線形、nlog⁡nn \log n、2 乗のいずれかに分類し、nn を 2 倍にしたとき時間がどう変わるかを予測できる。
  3. std::chrono::steady_clock で実行時間を測定し、測定を予測と比べることができる。
  4. 与えられたデータのサイズに対して二つのアルゴリズムから一つを選び、その選択を増加のオーダーで根拠づけることができる。

演算を数える

二つ目の問い

レッスン 正しいループの設計 と 再帰 では、アルゴリズムが正しいこと、すなわち停止し、その結果が事後条件を満たすことを証明する方法を学んだ。ところが、レッスン 数値アルゴリズム は同じように正しい二つの素数判定を示した。一つはおよそ nn 回の除算、もう一つはおよそ n\sqrt{n} 回の除算を行う。またレッスン 再帰 は、F30F_{30} を計算する二つの正しい方法を示した。一つは 2 692 5372\,692\,537 回の呼び出し、もう一つは 29 回の加算である。そうであれば、正しさだけでは選べない。二つの正しいアルゴリズムのうち、一方は一瞬で答え、もう一方は答えが意味を失う前に終わらないこともある。したがって、アルゴリズムに向ける二つ目の問いは、どれだけのコストがかかるか、である。

コストは時計で測ることもでき、第 4 節でそれを行う。しかし一回の実行時間は、マシン、コンパイラ、そのオプション、そして同じ時刻にコンピュータが何をしているかに左右され、そこからは別のマシンでのアルゴリズムについて何も導けない。それらのどれにも左右されないのは、アルゴリズムが踏むステップの数である。ここからこのレッスンの最初の決定が導かれる。コストは数えることで測り、時計はその数を確かめるために取っておく。

サイズと支配的な演算

すべてのステップ（加算の一つ一つ、比較の一つ一つ、添字の増分の一つ一つ、メモリへのアクセスの一つ一つ）を数えるのは面倒で無益である。ほとんどすべてが一定の比率で一つの主要なステップに伴うからである。そこで支配的な演算を選ぶ。定数倍を除けばほかのどの演算以上の回数だけ実行され、そのためすべてを代表する演算である。ベクターの要素の総和では加算、最大値の探索では比較、素数判定では除算がそれにあたる。それが実行される回数は、nn と書く入力サイズの関数として表す。入力サイズとは、ベクターの要素数、判定する数、桁数などである。

nn 個の要素からなるベクターを走査し、各要素に一定量の仕事をする単純なループは、支配的な演算を nn 回実行する。これに対して空でないベクターの最大値は、最初の要素を候補として始め、残りの要素をそれぞれ候補と比べる。比較は n−1n - 1 回である。nn と n−1n - 1 の違いは現実のものだが、第 3 節で見るように、大事なことは何も変えない。

最悪の場合

同じサイズのデータでいつも同じ回数の演算を実行するとは限らないアルゴリズムもある。ベクターの中で値を探し、見つかるまで走査する探索は、値が最初の位置にあれば比較を一回だけ行い、ない場合は nn 回行う。そのコストを語るには二つの状況のどちらかを選ぶ。ふつう選ぶのは最悪の場合、つまりサイズ nn のすべての入力のうちで演算の回数が最大のものである。理由は、契約が事前条件を満たすすべての入力に対して書かれるのと同じである。最悪の場合は保証であり、最良の場合は期待にすぎない。だから線形探索のコストは最悪の場合 nn 回の比較であり、このレッスンが単に「コスト」と言うときは、最悪の場合のコストを指す。

入れ子のループ

レッスン ループ では、入れ子になった二つのループの周回を数えることを学んだ。内側がいつも mm 周し、それが外側の nn 周のそれぞれについて起こるなら、内側の本体は n⋅mn \cdot m 回実行される。内側が外側に依存するなら、行ごとに足し合わせる。コレクションを扱うときに最もよく現れるのはすべての組の場合である。各要素をその後ろにある要素の一つ一つと比べるもので、ベクターに重複があるかどうかを調べるときがそうである。

C++ のプログラム
#include <print>​int main(){    for (int n{10}; n <= 10'000; n *= 10) {        long long comparisons{0};        for (int i{0}; i < n; ++i) {            for (int j{i + 1}; j < n; ++j) {                ++comparisons;            }        }        std::println("n = {:>6}：比較 {:>10} 回、n(n - 1)/2 = {}",                     n, comparisons, static_cast<long long>(n) * (n - 1) / 2);    }}
出力
n =     10：比較         45 回、n(n - 1)/2 = 45n =    100：比較       4950 回、n(n - 1)/2 = 4950n =   1000：比較     499500 回、n(n - 1)/2 = 499500n =  10000：比較   49995000 回、n(n - 1)/2 = 49995000

カウンタは、本物のアルゴリズムが行うはずの比較の代わりをしている。外側の第 ii 周では、内側は i+1i + 1 から n−1n - 1 まで進み、n−1−in - 1 - i 周する。したがって合計は (n−1)+(n−2)+⋯+1+0(n - 1) + (n - 2) + \cdots + 1 + 0 であり、レッスン ループ の和になる：

∑i=0n−1(n−1−i)=n(n−1)2\sum_{i=0}^{n-1} (n - 1 - i) = \frac{n(n - 1)}{2}

出力は、どのサイズでもこの公式を確かめている。カウンタが long long なのは、nn がおよそ六万五千を超えると組の数が int（このプラットフォームでは 32 ビット）の最大値を上回るからであり、公式が変換してから掛けるのも同じ理由による。2 乗のアルゴリズムのカウンタは、データよりはるかに早くオーバーフローする。

第 3 節で一般化することを、ここで先に見ておこう。nn を 10 倍すると、比較の回数は約 100 倍になる。データが十個なら比較は 45 回、一万個なら五千万回近くになる。