Loading article…
アルゴリズムにおいて、事前計算とは、実行前に初期計算を行い、アルゴリズムが実行されるたびに繰り返される計算を回避するために使用できるルックアップテーブルを生成する行為です。事前計算は、アルゴリズムの入力に依存しない高コストな計算結果に依存するアルゴリズムでよく使用されます。事前計算の簡単な例としては、πやeなどの数学定数をハードコードして使用し、実行時に必要な精度で近似値を計算するのではなく、そのまま使用することが挙げられます。
データベースでは、マテリアライゼーションという用語は、事前計算の結果を格納することを指すのに使用されます。[ 1 ] [ 2 ]例えば、マテリアライズド ビューなどです。[ 3 ] [ 4 ]
アルゴリズムの実行開始時に中間結果のセットを事前に計算しておくと、アルゴリズムの効率を大幅に向上させることができる場合が多い。これは、1つ以上の入力が十分に狭い範囲に制限され、結果を適切なサイズのメモリブロックに格納できる場合に特に有利となる。メモリへのアクセスは（キャッシュ遅延を除けば）時間計算量がほぼ一定であるため、入力範囲が狭い場合に効率が一定を下回るコンポーネントを持つアルゴリズムは、値を事前に計算することで改善できる。補間も線形演算であるため、場合によっては、値の離散的なサブセットを計算し、中間入力値を補間することで、効率的な近似アルゴリズムが得られる。
コンピュータが登場する以前は、三角関数表、対数表、統計密度関数表などの複雑な関数の手計算を高速化するために、印刷された値の参照表が人々に使用されていました。[ 5 ] 学校の子供たちは、最もよく使用される数 (9 x 9 または 12 x 12 まで) の計算を避けるために、 「九九」を暗記するように教えられることがよくあります。西暦 493 年という早い時期に、アキテーヌのヴィクトリウスは、2 から 50 までのすべての数の積を (ローマ数字で) 示し、行は「千から始まり、百ずつ減って 100 まで、次に十ずつ減って 10 まで、次に一ずつ減って 1 まで、そして分数で 1/144 まで減った数のリスト」である 98 列の乗算表を作成しました。[ 6 ]
現代のコンピュータによるデジタル三角関数の実装においても、補間アルゴリズムの係数を提供したり、逐次近似アルゴリズムを初期化したりするために、事前に計算されたルックアップテーブルがよく使用されます。
暗号システムに対する攻撃の多くは、事前計算を伴う。
現代の効率的なアルゴリズムの一部としての大規模な事前計算の例としては、以下のようなものがある。
コンパイラは、生成されるコードの実行速度を向上させる手段として、事前計算を多用します。この事前計算は、実質的にプログラムコード自体の部分的な評価とみなすことができます。このような事前計算の例としては、データフロー解析や強度低減処理などが挙げられます。