Loading article…
コンピュータサイエンスにおいて、実行時アルゴリズムの特殊化とは、特定の種類の高コストな計算タスクに対して効率的なアルゴリズムを作成するための手法である。この手法は、自動定理証明の分野、より具体的には、ヴァンパイア定理証明器プロジェクトに端を発する。
このアイデアは、プログラム変換の最適化における部分評価の利用に触発されたものです。定理証明器の多くのコア操作は、次のパターンを示します。あるアルゴリズムを実行する必要があるとします。値がは、潜在的に多くの異なる値に対して固定されます。これを効率的に行うために、すべての固定値に対してつまり、そのようなアルゴリズム実行中実行することと同等。
特殊なアルゴリズムは、固定値の特定の特性を利用できるため、汎用アルゴリズムよりも効率的である可能性がある。。 通常、いくつかの操作を回避できます特定のパラメータに対して冗長であることがわかっている場合、実行する必要がある特に、次のようなテストを真偽判定できる場合がよくあります。ループ展開や再帰など。
実行時特殊化と部分評価の主な違いは、で特殊化は静的にはわからないため、特殊化は実行時に行われます。
また、重要な技術的な違いもあります。部分評価は、何らかのプログラミング言語でコードとして明示的に表現されたアルゴリズムに適用されます。実行時には、具体的な表現は必要ありません。想像するだけでいい特殊化手順をプログラムする際には、特殊化されたバージョンの具体的な表現のみが必要です。これはまた、部分評価の場合によく見られるような、アルゴリズムを特殊化するための普遍的な方法を使用できないことを意味します。その代わりに、個々のアルゴリズムごとに特殊化手順をプログラムする必要があります。そうすることの重要な利点は、特性を利用した強力なアドホックなトリックを使用できることです。そして表現そしてこれらは、いかなる普遍的な専門化手法でも対応できないものである。
特殊なアルゴリズムは、解釈可能な形式で表現されなければならない。
多くの状況では、通常はは多くの値で計算される連続して、は、特別な抽象機械の機械語命令として記述することができ、一般的には次のように言われています。コンパイルされたコード自体を、抽象機械の命令の意味論のみに依存する、解答を保持する変換によってさらに最適化することができる。
抽象マシンの命令は通常、レコードとして表現できます。このようなレコードのフィールドの1つである命令識別子（または命令タグ）は、命令の種類を識別します。たとえば、特定の命令に対応する特定の整数値を持つ整数フィールドを使用できます。他のフィールドは、命令の追加パラメータを格納するために使用できます。たとえば、命令の意味論でジャンプが必要な場合、ポインタフィールドはラベルを表す別の命令を指すことができます。コードのすべての命令は、配列、リンクリスト、ツリーなどの走査可能なデータ構造に格納できます。
解釈（または実行）は、命令をある順序で取得し、その型を識別し、その型に関連付けられたアクションを実行することによって進行する。
CやC++などの多くのプログラミング言語では、単純なswitchステートメントを使用して、異なる命令識別子にアクションを関連付けることができます。現代のコンパイラは通常、switch狭い範囲の定数（例えば整数）ラベルを持つステートメントをコンパイルし、値に対応するステートメントのアドレスを保存します。で特殊な配列の 番目のセルを効率的な最適化手段として使用します。これは、命令識別子の値を小さな範囲の値から選択することで活用できます。
多くの事例がある状況では長期保管および呼び出しを目的としています異なる予測不可能な順序で。たとえば、チェックする必要があるかもしれません。まず、それから、 それからなど。このような状況では、コンパイルを伴う本格的な特殊化はメモリ使用量が過剰になるため適さない場合があります。しかし、時にはコンパクトな特殊化表現が見つかることもあります。 すべての一緒に、または代わりに保存できます。また、バリアントも定義します。この表現で機能し、呼び出しもに置き換えられます同じ仕事をより速く行うことを目的としていた。
