ルックアップテーブル

計算機科学におけるルックアップテーブル(英: Lookup table)とは、複雑な計算処理を単純な配列の参照処理で置き換えて効率化を図るために作られた、配列や連想配列などのデータ構造のことをいう。例えば大きな負担がかかる処理をコンピュータに行わせる場合、あらかじめ先に計算できるデータは計算しておき、その値を配列（ルックアップテーブル）に保存しておく。コンピュータはその都度計算を行う代わりに配列から目的のデータを取り出すことによって、計算の負担を軽減し効率よく処理を行うことができる。高価な計算処理や入出力処理をテーブルルックアップで置き換えた場合、処理時間を大きく削減することができる。他にも、あるキーワードを基にあるデータを取り出すとき、その対応を表としてまとめたものもルックアップテーブルといえる。テーブルの作成方法には、コンパイル前に計算したものを静的に確保したメモリに格納しておく方法や、プログラムの初期化処理中に計算（メモ化）やプリフェッチを行っておく方法がある。また、入力された値がルックアップテーブルにあるか調べることで入力値のチェックを行ったり、プログラミング言語によっては、ルックアップテーブルに関数ポインタ（あるいはラベルへのオフセット）を格納しておいて入力に応じた処理を行ったりするといった応用的な使い方をされることもある。

配列、連想配列、連結リストでのルックアップ

線形探索や力まかせ探索では、リストの各要素との比較を次々に行い、対応する値が見つかったらその値が検索結果となる。このような検索方法では、対応する値がリスト中になかったり、あるいはリストの後ろの方にあったりといった原因で簡単に性能が悪化してしまう。一次元の配列や連結リストでは通常、このようなルックアップは入力値に合致する要素があるか判断するために行われる。

配列上での二分探索

分割統治法の一つである二分探索法は、配列を2つに分割し、配列のどちらの側に対象の要素が存在するか判断するという処理を、検索対象の要素が見つかるまで繰り返す方法である。配列がソートされている場合のみ利用できる方法だが、大きな配列に対しても良好なパフォーマンスを示す。

自明なハッシュ関数

自明なハッシュ関数（trivial hash function）を利用する方法（インデックスマッピング）では、データを符号なしの値としてそのまま一次元配列のインデックスに使用する。値の範囲が小さければ、これが最も高速なルックアップ方法となる。

ビット列中で「1」の桁数を求める

例えば、（二進数の）数字の中で「1」である桁数（ハミング重み）を求める処理を考える。例えば、十進数の「37」は二進数では「100101」であり、「1」である桁は3つある。
この処理をC言語で記述した簡単な例を以下に示す。この例では、int型の引数を対象に「1」である桁を数えている。
int count_ones(unsigned int x) {
    int result = 0;
    while (x != 0)
        result++, x = x & (x-1);
    return result;}
この一見シンプルなアルゴリズムは、実際に実行すると、近代的なアーキテクチャのプロセッサでも数百サイクルを要する場合がある。これは、ループ中で繰り返し分岐処理が実行されるためである（分岐処理は遅いことが多い）。コンパイラによっては、最適化の際にこの処理をループ展開することで性能がいくらか改善される場合もある。しかし、自明なハッシュ関数を利用したアルゴリズムであればよりシンプルかつ高速に処理が行える。
256個の要素を持つ静的なテーブル（名前はbit_setとする）を用意し、各要素には0から255までの数の「1」の桁数を格納する。int型変数の各バイトの値を自明なハッシュ関数としてこのテーブルをルックアップし、それを足し合わせる。この方法であれば分岐は発生せずメモリアクセスが4回発生するだけのため、上記のコードよりもずっと高速である。
/* ('int'は32ビット幅と仮定) */int count_ones(unsigned int x) {
    return bits_set[ x        & 0xFF] + bits_set[(x >>  8) & 0xFF]
         + bits_set[(x >> 16) & 0xFF] + bits_set[(x >> 24) & 0xFF] ;}
上記のコードは、xを4バイトの unsigned char 配列にキャストすれば、ビット積（&）とシフトが取り除けるのでさらに高速化できる。また、関数化せずインラインで実装してもよい。
なお、現在のプロセッサではこのようなテーブルルックアップは逆に速度の低下を起こす可能性がある。これは、改善前のコードはおそらく全てキャッシュ上から実行されるが、一方でルックアップテーブルがキャッシュに載りきらなかった場合は、低速なメモリへのアクセスが発生するためである（さらに、上記の例では、4回のルックアップそれぞれにおいてテーブル中の要素のアドレスを計算する必要がある）。

画像処理におけるルックアップテーブル(LUT)

画像処理などデータ解析系の処理において、ルックアップテーブル(LUT)は入力データを処理に適した形に変換するのに使われる。例えば、グレイスケールの土星の映像をカラー画像へ変換し、土星の輪のそれぞれを強調するといった処理が行われる。
ルックアップテーブルを使用した計算量削減の代名詞として、正弦などの三角関数の計算が挙げられる。三角関数の計算のために処理が遅くなっている場合は、例えば正弦の値を1度ずつ360度すべてに対して予め計算しておくことで、処理の高速化を図ることができる（この際、コンパイル時に静的変数としてテーブルを定義しておけば、実行時に毎回計算を行うコストも省くことができる）。
プログラム中で正弦の値を使う際には、最も近い正弦の値をメモリから取得する。この際、求める値がテーブルにない場合は、公式を用いて求め直すこともできるが、テーブル中の最も近い値をもとに内挿することもできる。このようなルックアップテーブルは数値演算コプロセッサの内部でも使用されている。例えば、Intelの悪名高い浮動小数点除算バグはルックアップテーブルの誤りが原因であった。
変数が1つしかない関数（例えば正弦や余弦）は単純な一次元配列として実装できるが、複数の変数を持つ関数の場合は多次元配列を使用する必要がある。例えば、ある範囲のxとyに対してを求めるのであれば、power[x][y]という二次元配列を使うことになる。また、複数の値を持つ関数の場合はルックアップテーブルを構造体の配列として実装する。
前述のように、ルックアップテーブルと少量の計算処理（例えば内挿）を組み合わせて使う方法もある。予め計算しておいた値と内挿を組み合わせることで、比較的精度の高い値を求めることができる。この手法は単純なテーブルルックアップよりも多少時間がかかるが、処理結果の精度を高めるのには非常に効果的である。またこの手法には、予め計算しておく値の数と求める値の精度とを調整し、ルックアップテーブルのサイズを削減するといった使い方もある。
画像処理の分野では、ルックアップテーブルはLUTとも呼ばれる。よくあるLUTの使用法としてはカラーマップ（あるいはパレット）があり、これは画像を表示する際の色や輝度を決めるのに使われる。コンピュータ断層撮影においては、これと同様の概念をウィンドウと呼び、計測された放射線の強度をどのように表示するか決めるのに使われる。
LUTは高い効果が得られる場合がある一方で、置き換え対象の処理が比較的シンプルだと、ひどいペナルティが発生する場合もある。計算結果として求める内容によっては、メモリからの値の取得処理やメモリの要求処理の複雑性が原因で、アプリケーションの処理時間や複雑性が逆に増加することがある。また、キャッシュ汚染が原因で問題が発生する場合もある。大きなテーブルへのアクセスは、ほぼ確実にキャッシュミスを誘発してしまう。この現象は、プロセッサとメモリの速度差が大きくなればなるほど大きな問題となる。似たような問題はコンパイラ最適化の際の再実体化においても発生する。他にもJavaなど一部の環境では境界チェックが必須となっているため、ルックアップの度に追加の比較・分岐処理が発生してしまう。
ルックアップテーブルの構築を行うタイミングによっては、以下の2つの制約が発生する。一つは使用可能なメモリ量で、それよりも大きなルックアップテーブルを作ることはできない（ディスク上にテーブルを作ることも可能だが、ルックアップが非常に高価になってしまう）。もう一つは、テーブル作成の際にかかる時間で、通常この処理は一回しか行われないが、それでも法外に長い時間がかかるとしたら、そのルックアップテーブルの使用法は不適切だと言えるだろう。ただし前述したように、多くの場合テーブルは静的に定義しておくことができる。

ハードウェアLUT

デジタル回路では、nビットのルックアップテーブルはマルチプレクサで実装できる（マルチプレクサのセレクトラインをLUTの入力として、アウトプットを定数値とすればよい）。また、nビットのLUTを関数の真理値表として使えば、任意のn入力のブール関数を表すことができる。実際、最近のFPGAでは4〜6ビット入力のLUTがキー要素となっている。