「ルックアップテーブル」の版間の差分

削除された内容追加された内容

インライン

2020年7月5日 (日) 22:48時点における版

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

歴史

Handbook of Mathematical Functions with Formulas, Graphs, and Mathematical Tables（通称Abramowitz and Stegun）に掲載されている常用対数表の一部

コンピュータ誕生以前には、三角法、対数、統計学における密度関数など、複雑な関数の手計算の効率化のために数表が使用されていた^[2] 。

मखि भखि फखि धखि णखि ञखि ङखि हस्झ स्ककि किष्ग श्घकि किघ्व |
घ्लकि किग्र हक्य धकि किच स्ग झश ङ्व क्ल प्त फ छ कला-अर्ध-ज्यास् ||
- アリヤバータの正弦表

古代インドにおいては、アリヤバータが最も古い正弦表の一つであるアリヤバータの正弦表を作成している（これはサンスクリット語ベースの数体系で記述されている）。西暦493年には、アキテーヌのビクトリウスがローマ数字の98列の掛け算表を作成している。これには、2から50までの各数と、1000から100まで100刻みの数・100から10まで10刻みの数・10から1までの1刻みの数・1/144までの分数のそれぞれの積が載っている^[3]。現代の学校では、子供に九九表のような表を暗記させ、よく使う数字の積は計算しなくても分かるようにすることがしばしば行われる。この表は、1から9まで、または1から12までの数字の積が載っているものが使われることが多い。

コンピュータが誕生して間もない頃は、入出力処理は当時のプロセッサの処理速度と比較しても非常に低速だった。そのため、読み込み処理を減らすため、プログラム中に埋め込まれた静的なルックアップテーブルや、動的に確保したプリフェッチ用の配列に、よく使われるデータ項目だけを格納するといったことが行われた。現在ではシステム全体でキャッシュが導入され、こういった処理の一部は自動的に行われるようになっている。それでもなお、変更頻度の低いデータをアプリケーションレベルでルックアップテーブルに格納することにより、パフォーマンスの向上を図ることができる。

例

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

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

連結リストと配列の比較

→詳細は「連結リスト」を参照

連結リストには配列と比較して以下のような利点がある。

連結リストに特有の性質として、要素の挿入と削除を定数時間で行える（なお、削除された要素を「この要素は空である」とマーキングする方式であれば配列でも削除は定数時間で行える。ただし、配列を走査する際に空の要素をスキップする必要がある）。

要素の挿入を、メモリ容量の許す限り連続して行える。配列の場合は、内容がいっぱいになったらリサイズする必要があるが、これは高価な処理である上に、メモリが断片化していた場合はリサイズ自体が行えないこともある。同様に、配列から要素を大量に削除した場合、使用メモリの無駄をなくすには配列のリサイズを行う必要がある。

一方、配列には以下のような利点がある。

連結リストはシーケンシャルアクセスしか行えないが、配列はランダムアクセスが行える。また、単方向の連結リストの場合、一方向にしか走査が行えない。このため、ヒープソートのようにインデックスを使って要素を高速に参照する必要がある処理には連結リストは向いていない。

多くのマシンでは、連結リストよりも配列のほうが順次アクセスが高速に行える。これは、配列の方が参照の局所性が高くプロセッサのキャッシュの恩恵を受けやすいためである。

連結リストは配列と比較してメモリを多く消費する。これは、次の要素への参照を保持しているためであるが、格納するデータ自体が小さい場合（キャラクタやブール値などの場合）はこのオーバーヘッドが原因で実用性がなくなってしまうこともある。また、新しい要素を格納する際の動的メモリ確保にネイティブアロケータを使用する場合、メモリ確保による速度の低下や使用メモリ量の無駄が発生する場合もあるが、これはメモリプールを使用すれば概ね解決できる。

2つの手法を組み合わせて両方の利点を得ようとする手法もある。Unrolled linked listでは一つの連結リストのノード中に複数の要素を格納することでキャッシュパフォーマンスを向上させるとともに、参照を保持するためのメモリのオーバーヘッドを削減している。同様の目的で使用されるCDRコーディングでは、参照元レコードの終端を伸ばし、参照を実際に参照されるデータで置き換えている。

配列上での二分探索

分割統治法の一つである二分探索法は、配列を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に対して $x^{y}$ を求めるのであれば、power[x][y]という二次元配列を使うことになる。また、複数の値を持つ関数の場合はルックアップテーブルを構造体の配列として実装する。

前述のように、ルックアップテーブルと少量の計算処理（例えば内挿）を組み合わせて使う方法もある。予め計算しておいた値と内挿を組み合わせることで、比較的精度の高い値を求めることができる。この手法は単純なテーブルルックアップよりも多少時間がかかるが、処理結果の精度を高めるのには非常に効果的である。またこの手法には、予め計算しておく値の数と求める値の精度とを調整し、ルックアップテーブルのサイズを削減するといった使い方もある。

画像処理の分野では、ルックアップテーブルはLUTとも呼ばれる。よくあるLUTの使用法としてはカラーマップ（あるいはパレット）があり、これは画像を表示する際の色や輝度を決めるのに使われる。コンピュータ断層撮影においては、これと同様の概念をウィンドウと呼び、計測された放射線の強度をどのように表示するか決めるのに使われる。

LUTは高い効果が得られる場合がある一方で、置き換え対象の処理が比較的シンプルだと、ひどいペナルティが発生する場合もある。計算結果として求める内容によっては、メモリからの値の取得処理やメモリの要求処理の複雑性が原因で、アプリケーションの処理時間や複雑性が逆に増加することがある。また、キャッシュ汚染が原因で問題が発生する場合もある。大きなテーブルへのアクセスは、ほぼ確実にキャッシュミスを誘発してしまう。この現象は、プロセッサとメモリの速度差が大きくなればなるほど大きな問題となる。似たような問題はコンパイラ最適化の際の再実体化においても発生する。他にもJavaなど一部の環境では境界チェックが必須となっているため、ルックアップの度に追加の比較・分岐処理が発生してしまう。

ルックアップテーブルの構築を行うタイミングによっては、以下の2つの制約が発生する。一つは使用可能なメモリ量で、それよりも大きなルックアップテーブルを作ることはできない（ディスク上にテーブルを作ることも可能だが、ルックアップが非常に高価になってしまう）。もう一つは、テーブル作成の際にかかる時間で、通常この処理は一回しか行われないが、それでも法外に長い時間がかかるとしたら、そのルックアップテーブルの使用法は不適切だと言えるだろう。ただし前述したように、多くの場合テーブルは静的に定義しておくことができる。

正弦の計算

四則演算しか行えないようなコンピュータの多くでは、与えられた値の正弦を直接求めることはできないため、高い精度の正弦を求める際には、代わりにCORDICアルゴリズムを使用するか、または以下のようなテイラー展開を行う。

\operatorname {sin} (x)\approx x-{\frac {x^{3}}{6}}+{\frac {x^{5}}{120}}-{\frac {x^{7}}{5040}}

（xが0に近い場合）

しかし、この処理は（特に低速なコンピュータでは）計算に時間がかかる。また、コンピュータグラフィックス作成用のソフトウェアなどでは正弦値を求める処理が毎秒何千回も行われる。一般的な解決方法としては、予めある範囲の値の正弦を一定間隔で計算しておき、xの正弦を求める際はxに最も近い値の正弦を使用するという方法がある。正弦は連続関数であり、また値も一定範囲に収まるため、このような方法でもある程度正確な結果に近い値が得られる。処理は例えば以下のようになる。

 real array sine_table[-1000..1000]
 for x from -1000 to 1000
     sine_table[x] := sine(pi * x / 1000)

 function lookup_sine(x)
     return sine_table[round(1000 * x / pi)]

ただし、このテーブルは相当の大きさになる。IEEE倍精度浮動小数点数を使用する場合なら、テーブルのサイズは16,000バイト以上にもなる。サンプル数を減らす方法もあるが、これは代わりに精度が著しく悪化する。この問題の一つの解決方法としては線形補間がある。これは、テーブル中でxと隣り合っている2つの値の間に直線を引き、この直線上の値を求めるという方法である。これは計算も速く、滑らかな関数においてもかなり正確な値を求められる。線形補間を利用した例は以下のようになる。

 function lookup_sine(x)
     x1 := floor(x*1000/pi)
     y1 := sine_table[x1]
     y2 := sine_table[x1+1]
     return y1 + (y2-y1)*(x*1000/pi-x1)

その他には、正弦と余弦の関係、および対称性を利用して、少しの計算時間を引き換えにテーブルのサイズを1/4にする方法がある。この場合、ルックアップテーブルを作成する際に、第一象限だけを対象とする（つまり、 $0\leqq x\leqq {\frac {\pi }{2}}$ の範囲のみ正弦の計算を行う）。値を求める際は、変数を第一象限に当てはめなおす。角度を $0\leqq x\leqq 2\pi$ の範囲に直した後（元々 $0\leqq x\leqq 2\pi$ の範囲しか考慮しないのであればこれは不要）、正しい値に変換して返す。つまり、第一象限ならテーブルの値をそのまま返し、第二象限なら ${\frac {\pi }{2}}-x$ の値を返し、第三象限と第四象限の場合はそれぞれ第一象限と第二象限の値をマイナスにして返す。余弦を求める場合は、 ${\frac {\pi }{2}}$ だけずらした値（つまり $x+{\frac {\pi }{2}}$ で求めた値）を返せばよい。正接を求める場合は、余弦で正弦を割ればよい（実装によってはゼロ除算の処置が必要になる）。

 function init_sine()
     for x from 0 to (360/4)+1
         sine_table[x] := sine(2*pi * x / 360)

 function lookup_sine(x)
     x  = wrap x from 0 to 360
     y := mod (x, 90)

     if (x <  90) return  sine_table[   y]
     if (x < 180) return  sine_table[90-y]
     if (x < 270) return -sine_table[   y]
                  return -sine_table[90-y]

 function lookup_cosine(x)
     return lookup_sine(x + 90)

 function lookup_tan(x)
     return (lookup_sine(x) / lookup_cosine(x))

内挿を行う場合、不均一サンプリングを利用することでルックアップテーブルのサイズを削減できる。これは、関数の値が直線状にしか変化しない部分ではサンプリング点を減らし、そうでない部分ではサンプリング点を増やして近似値を実際の関数のカーブに近づけるという方法である。詳細については内挿を参照すること。

ハードウェアLUT

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

外部リンク

Fast table lookup using input character as index for branch table
Art of Assembly: Calculation via Table Lookups
Color Presentation of Astronomical Images
"Bit Twiddling Hacks" (includes lookup tables) スタンフォード大学のSean Eron Andersonによる
Memoization in C++ ジョンズ・ホプキンス大学のPaul McNameeによる測定結果
"The Quest for an Accelerated Population Count" by Henry S. Warren, Jr.

参考文献

^ http://apl.jhu.edu/~paulmac/c++-memoization.html
^ Martin Campbell-Kelly; Mary Croarken; Raymond Flood; Eleanor Robson, ed. (October 2, 2003) [2003], The History of Mathematical Tables From Sumer to Spreadsheets (1st ed.), New York, USA: Oxford University Press, ISBN 978-0-19-850841-0
^ Maher, David. W. J. and John F. Makowski. "Literary Evidence for Roman Arithmetic With Fractions", 'Classical Philology' (2001) Vol. 96 No. 4 (2001) pp. 376-399. （p.383を見よ）

[1] ttp://apl.jhu.edu/~paulmac/c++-memoization.html

[2] Martin Campbell-Kelly; Mary Croarken; Raymond Flood; Eleanor Robson, ed. (October 2, 2003) [2003], The History of Mathematical Tables From Sumer to Spreadsheets (1st ed.), New York, USA: Oxford University Press, ISBN 978-0-19-850841-0

[3] Maher, David. W. J. and John F. Makowski. "Literary Evidence for Roman Arithmetic With Fractions", 'Classical Philology' (2001) Vol. 96 No. 4 (2001) pp. 376-399. （p.383を見よ）

[1]

[2]

[3]

@@ 64行目: / 64行目: @@
 この処理を[[C言語]]で記述した簡単な例を以下に示す。この例では、<code {{lang属性|en}}>int</code>型の引数を対象に「1」である桁を数えている。
-<source lang="c">
+<syntaxhighlight lang="c">
 int count_ones(unsigned int x) {
     int result = 0;
@@ 71行目: / 71行目: @@
     return result;
 }
+</syntaxhighlight>
-</source>
 この一見シンプルなアルゴリズムは、実際に実行すると、近代的なアーキテクチャのプロセッサでも数百サイクルを要する場合がある。これは、ループ中で繰り返し分岐処理が実行されるためである（分岐処理は遅いことが多い）。コンパイラによっては、最適化の際にこの処理を[[ループ展開]]することで性能がいくらか改善される場合もある。しかし、自明なハッシュ関数を利用したアルゴリズムであればよりシンプルかつ高速に処理が行える。
@@ 77行目: / 77行目: @@
 個の要素を持つ静的なテーブル（名前は<code {{lang属性|en}}>bit_set</code>とする）を用意し、各要素には0から255までの数の「1」の桁数を格納する。<code {{lang属性|en}}>int</code>型変数の各バイトの値を自明なハッシュ関数としてこのテーブルをルックアップし、それを足し合わせる。この方法であれば分岐は発生せずメモリアクセスが4回発生するだけのため、上記のコードよりもずっと高速である。
-<source lang="c">
+<syntaxhighlight lang="c">
 /* ('int'は32ビット幅と仮定) */
 int count_ones(unsigned int x) {
@@ 83行目: / 83行目: @@
          + bits_set[(x >> 16) & 0xFF] + bits_set[(x >> 24) & 0xFF] ;
 }
+</syntaxhighlight>
-</source>
 上記のコードは、<code {{lang属性|en}}>x</code>を4バイトの <code {{lang属性|en}}>unsigned char</code> 配列にキャストすれば、ビット積（<code {{lang属性|en}}>&amp;</code>）とシフトが取り除けるのでさらに高速化できる。また、関数化せずインラインで実装してもよい。