ルックアップテーブル
計算機科学におけるルックアップテーブル(英: Lookup table)とは、複雑な計算処理を単純な配列の参照処理で置き換えて効率化を図るために作られた、配列や連想配列などのデータ構造のことをいう。例えば大きな負担がかかる処理をコンピュータに行わせる場合、あらかじめ先に計算できるデータは計算しておき、その値を配列(ルックアップテーブル)に保存しておく。コンピュータはその都度計算を行う代わりに配列から目的のデータを取り出すことによって、計算の負担を軽減し効率よく処理を行うことができる。高価な計算処理や入出力処理をテーブルルックアップで置き換えた場合、処理時間を大きく削減することができる。他にも、あるキーワードを基にあるデータを取り出すとき、その対応を表としてまとめたものもルックアップテーブルといえる。テーブルの作成方法には、コンパイル前に計算したものを静的に確保したメモリに格納しておく方法や、プログラムの初期化処理中に計算(メモ化)やプリフェッチを行っておく方法がある。また、入力された値がルックアップテーブルにあるか調べることで入力値のチェックを行ったり、プログラミング言語によっては、ルックアップテーブルに関数ポインタ(あるいはラベルへのオフセット)を格納しておいて入力に応じた処理を行ったりするといった応用的な使い方をされることもある。
計算結果として求める内容によっては、メモリからの値の取得処理やメモリの要求処理の複雑性が原因で、アプリケーションの処理時間や複雑性が逆に増加することがある。また、キャッシュ汚染が原因で問題が発生する場合もある。大きなテーブルへのアクセスは、ほぼ確実にキャッシュミスを誘発してしまう。この現象は、プロセッサとメモリの速度差が大きくなればなるほど大きな問題となる。似たような問題はコンパイラ最適化の際の再実体化においても発生する。他にもJavaなど一部の環境では境界チェックが必須となっているため、ルックアップの度に追加の比較・分岐処理が発生してしまう。
ルックアップテーブルの構築を行うタイミングによっては、以下の2つの制約が発生する。一つは使用可能なメモリ量で、それよりも大きなルックアップテーブルを作ることはできない(ディスク上にテーブルを作ることも可能だが、ルックアップが非常に高価になってしまう)。もう一つは、テーブル作成の際にかかる時間で、通常この処理は一回しか行われないが、それでも法外に長い時間がかかるとしたら、そのルックアップテーブルの使用法は不適切だと言えるだろう。ただし前述したように、多くの場合テーブルは静的に定義しておくことができる。