アルゴリズムにおいて、事前計算とは、実行前に初期計算を実行し、アルゴリズムが実行するたびに繰り返し計算を回避するために使用できる参照テーブルを生成する行為です。事前計算は、アルゴリズムの入力に依存しない高価な計算の結果に依存するアルゴリズムでよく使用されます。事前計算の単純な例としては、πやeなどのハードコードされた数学定数を、実行時に必要な精度で近似値を計算する代わりに使用することが挙げられます。
データベースにおいて、マテリアライゼーションという用語は、事前計算の結果をマテリアライズドビューなどに格納することを指すために使用される。[ 1 ] [ 2 ] [ 3 ] [ 4 ]
概要
アルゴリズム実行の開始時に中間結果のセットを事前計算すると、アルゴリズムの効率が大幅に向上することがよくあります。これは、1つまたは複数の入力が、結果を適切なサイズのメモリブロックに格納できるほど狭い範囲に制限されている場合に有利になります。メモリアクセスの時間計算量は基本的に一定であるため（キャッシュ遅延を除く）、狭い入力範囲で効率が一定よりも悪いコンポーネントを持つアルゴリズムは、値を事前計算することで改善できます。補間も線形演算であるため、離散的な値のサブセットを計算し、中間入力値を 補間することで、効率的な近似アルゴリズムを取得できる場合があります
歴史
コンピュータが登場する以前は、三角関数表、対数表、統計密度関数表など、複雑な関数の手計算を高速化するために、印刷された値の参照表が使用されていました。[ 5 ] 学校では、最もよく使われる数（9×9または12×12まで）の計算を避けるために、 「掛け算表」を暗記するように教えられることがよくあります。西暦493年には、アキテーヌのヴィクトリアスが98列の掛け算表を記しており、これは（ローマ数字で）2から50までのあらゆる数の積を示しており、各行は「1000から始まり、100ずつ下がって100になり、10ずつ下がって10になり、1ずつ下がって144分の1までの分数のリスト」でした。[ 6 ]
例
現代のコンピュータによるデジタル三角関数の実装でも、補間アルゴリズムの係数を提供したり、逐次近似アルゴリズムを初期化したりするために、事前に計算されたルックアップテーブルを使用することがよくあります
暗号システムに対する攻撃の多くは事前計算を伴います。
現代の効率的なアルゴリズムの一部としての大規模な事前計算の例には次のものがあります。
- レインボーテーブル
- パーフェクトハッシュ
- キューブアタック
- 3Dグラフィックスの可視性計算のための事前計算されたBSPツリー
- 3Dグラフィックスにおける照明のためのラジオシティ事前計算
コンパイラは、結果のコードの実行速度を向上させる手段として、事前計算を広範に利用します。この事前計算は、実質的にプログラムコード自体の部分評価の一種と見なすことができます。この種の事前計算の例としては、データフロー解析や強度削減ステップなどが挙げられます。
参照
参考文献
- ^ Jiawei Han、Micheline Kamber（2011年6月9日）。『データマイニング：概念と手法』 Elsevier、159ページ。ISBN 978-0-12-381480-7。
- ^スヴェン・グロッペ（2011年4月29日）『セマンティックウェブデータベースにおけるデータ管理とクエリ処理』 Springer Science & Business Media、178ページ。ISBN 978-3-642-19357-6。
- ^カレン・モートン、ケリー・オズボーン、ロビン・サンズ、リヤジ・シャムスディーン、ジャレッド・スティル（2013年10月28日）。Pro Oracle SQL。Apress。48ページ。ISBN 978-1-4302-6220-6。
- ^ Marie-Aude Aufaure、Esteban Zimányi (2012年1月16日).ビジネスインテリジェンス：第1回ヨーロッパサマースクール、EBISS 2011、パリ、フランス、2011年7月3日～8日、チュートリアル講義. Springer Science & Business Media. 43ページ. ISBN 978-3-642-27357-5。
- ^キャンベル＝ケリー、マーティン、クローケン、メアリー、フラッド、レイモンド他編 (2003). 『数学表の歴史：シュメールからスプレッドシートまで』オックスフォード大学出版局. ISBN 978-0-19-850841-0。
- ^デイビッド・マーハー、WJ、ジョン・F・マコウスキー「分数を用いたローマ算術の文学的証拠」『古典文献学』（2001年）第96巻第4号（2001年）376～399ページ。（383ページ参照）
