ルックアップテーブルのソースを表示

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

== 歴史 ==
[[Image:Abramowitz&Stegun.page97.agr.jpg|thumb|Handbook of Mathematical Functions with Formulas, Graphs, and Mathematical Tables（通称[[Abramowitz and Stegun]]）に掲載されている[[常用対数]]表の一部]]

コンピュータ誕生以前には、[[三角法]]、[[常用対数|対数]]、[[統計学]]における[[確率分布|密度関数]]など、複雑な関数の手計算の効率化のために[[数表]]が使用されていた<ref>{{citation
|editors= Martin Campbell-Kelly; Mary Croarken; Raymond Flood; Eleanor Robson
|title=  The History of Mathematical Tables From Sumer to Spreadsheets
|edition= 1st
|date= October 2,  2003
|origyear= 2003
|publisher= Oxford University Press
|location= New York, USA
|isbn= 978-0-19-850841-0
}}
</ref> 。

{{side_box|text=मखि भखि फखि धखि णखि ञखि ङखि हस्झ स्ककि किष्ग श्घकि किघ्व <nowiki>|</nowiki><br> घ्लकि किग्र हक्य धकि किच स्ग झश ङ्व क्ल प्त फ छ कला-अर्ध-ज्यास् <nowiki>||</nowiki><br> - [[アリヤバータの正弦表]]}}

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

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

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

=== 連結リストと配列の比較 ===
{{Main|連結リスト}}

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

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

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

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

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

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

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

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

=== 配列上での二分探索 ===
<!-- 原文では「配列または連想配列上での……」となっていたが連想配列は関係ないので除外した -->

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

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

====ビット列中で「1」の桁数を求める ====
<!-- 原文では「多くのコンピュータではこの処理が高価」とされているが、POWERやAlphaにはpopulation count用の命令があるためこれはあまり適当ではないと思われる。そのため除外した -->
<!-- また、population count命令がない場合でも、多くの場合テーブルを使用せずビット演算のみを使用したほうが速いので、このサンプル自体が適切かどうかは疑問 -->
例えば、（二進数の）数字の中で「1」である桁数（[[ハミング重み]]）を求める処理を考える。例えば、十進数の「37」は二進数では「100101」であり、「1」である桁は3つある。

この処理を[[C言語]]で記述した簡単な例を以下に示す。この例では、<code {{lang属性|en}}>int</code>型の引数を対象に「1」である桁を数えている。

<syntaxhighlight lang="c">
int count_ones(unsigned int x) {
    int result = 0;
    while (x != 0)
        result++, x = x & (x-1);
    return result;
}
</syntaxhighlight>

この一見シンプルなアルゴリズムは、実際に実行すると、近代的なアーキテクチャのプロセッサでも数百サイクルを要する場合がある。これは、ループ中で繰り返し分岐処理が実行されるためである（分岐処理は遅いことが多い）。コンパイラによっては、最適化の際にこの処理を[[ループ展開]]することで性能がいくらか改善される場合もある。しかし、自明なハッシュ関数を利用したアルゴリズムであればよりシンプルかつ高速に処理が行える。

256個の要素を持つ静的なテーブル（名前は<code {{lang属性|en}}>bit_set</code>とする）を用意し、各要素には0から255までの数の「1」の桁数を格納する。<code {{lang属性|en}}>int</code>型変数の各バイトの値を自明なハッシュ関数としてこのテーブルをルックアップし、それを足し合わせる。この方法であれば分岐は発生せずメモリアクセスが4回発生するだけのため、上記のコードよりもずっと高速である。

<syntaxhighlight lang="c">
/* ('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] ;
}
</syntaxhighlight>

上記のコードは、<code {{lang属性|en}}>x</code>を4バイトの <code {{lang属性|en}}>unsigned char</code> 配列にキャストすれば、ビット積（<code {{lang属性|en}}>&amp;</code>）とシフトが取り除けるのでさらに高速化できる。また、関数化せずインラインで実装してもよい。

なお、現在のプロセッサではこのようなテーブルルックアップは逆に速度の低下を起こす可能性がある。これは、改善前のコードはおそらく全てキャッシュ上から実行されるが、一方でルックアップテーブルがキャッシュに載りきらなかった場合は、低速なメモリへのアクセスが発生するためである（さらに、上記の例では、4回のルックアップそれぞれにおいてテーブル中の要素のアドレスを計算する必要がある）。

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

[[画像処理]]などデータ解析系の処理において、ルックアップテーブル(LUT)は入力データを処理に適した形に変換するのに使われる。例えば、グレイスケールの土星の映像をカラー画像へ変換し、[[土星の輪]]のそれぞれを強調するといった処理が行われる。

ルックアップテーブルを使用した計算量削減の代名詞として、[[正弦]]などの三角関数の計算が挙げられる。三角関数の計算のために処理が遅くなっている場合は、例えば正弦の値を1度ずつ360度すべてに対して予め計算しておくことで、処理の高速化を図ることができる（この際、コンパイル時に静的変数としてテーブルを定義しておけば、実行時に毎回計算を行うコストも省くことができる）。

プログラム中で正弦の値を使う際には、最も近い正弦の値をメモリから取得する。この際、求める値がテーブルにない場合は、公式を用いて求め直すこともできるが、テーブル中の最も近い値をもとに[[内挿]]することもできる。このようなルックアップテーブルは数値演算コプロセッサの内部でも使用されている。例えば、Intelの悪名高い[[Pentium FDIV バグ|浮動小数点除算バグ]]はルックアップテーブルの誤りが原因であった。

変数が1つしかない関数（例えば正弦や余弦）は単純な一次元配列として実装できるが、複数の変数を持つ関数の場合は多次元配列を使用する必要がある。例えば、ある範囲のxとyに対して<math>x^y</math>を求めるのであれば、<code>power[x][y]</code>という二次元配列を使うことになる。また、複数の値を持つ関数の場合はルックアップテーブルを構造体の配列として実装する。

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

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

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

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

=== 正弦の計算 ===

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

:<math>\operatorname{sin}(x) \approx x - \frac{x^3}{6} + \frac{x^5}{120} - \frac{x^7}{5040}</math>（''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)]

[[Image:Interpolation example linear.svg|thumb|正弦関数の一部を線形補間した例|right]]

ただし、このテーブルは相当の大きさになる。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にする方法がある。この場合、ルックアップテーブルを作成する際に、第一象限だけを対象とする（つまり、<math>0 \leqq x \leqq \frac{\pi}{2}</math>の範囲のみ正弦の計算を行う）。値を求める際は、変数を第一象限に当てはめなおす。角度を<math>0 \leqq x \leqq 2\pi</math>の範囲に直した後（元々<math>0 \leqq x \leqq 2\pi</math>の範囲しか考慮しないのであればこれは不要）、正しい値に変換して返す。つまり、第一象限ならテーブルの値をそのまま返し、第二象限なら<math>\frac{\pi}{2}-x</math>の値を返し、第三象限と第四象限の場合はそれぞれ第一象限と第二象限の値をマイナスにして返す。余弦を求める場合は、<math>\frac{\pi}{2}</math>だけずらした値（つまり<math>x+\frac{\pi}{2}</math>で求めた値）を返せばよい。正接を求める場合は、余弦で正弦を割ればよい（実装によってはゼロ除算の処置が必要になる）。

  '''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))

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

<!-- == ルックアップテーブルのその他の用途 == -->
<!-- == キャッシュ == -->
<!-- {{main|キャッシュ (コンピュータシステム)}} -->
<!--
すみません、ここの記載は
http://news.mynavi.jp/column/architecture/137/
などの記事を参考に内容を理解しようとしたのですが、無理でした……どなたか続きをお願いします
  -->
<!--
Storage caches (including disk caches for files, or processor caches for either code or data) work also like a lookup table. The table is built with very fast memory instead of being stored on slower external memory, and maintains two pieces of data for a subrange of bits composing an external memory (or disk) address (notably the lowest bits of any possible external address):
* one piece (the tag) contains the value of the remaining bits of the address; if these bits match with those from the memory address to read or write, then the other piece contains the cached value for this address.
* the other piece maintains the data associated to that address.
A single (fast) lookup is performed to read the tag in the lookup table at the index specified by the lowest bits of the desired external storage address, and to determine if the memory address is hit by the cache. When a hit is found, no access to external memory is needed (except for write operations, where the cached value may need to be updated asynchronously to the slower memory after some time, or if the position in the cache must be replaced to cache another address).
 -->

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

== 学習 ==
LUT構築法の1つにLUTの[[機械学習|学習]]がある。

LUTは離散値 <math>i \in \{ i \in \mathbb{Z}| 0 \leq i < K \}</math> を入力<ref>有限個の要素をもつ ''Table'' であるため、入力も有限個に制限される。連続値は無限個存在するため、離散値に限られる。</ref>にとり、ベクトル <math>\boldsymbol{x} \in \mathbb{R}^N</math> を出力する関数と見なせる。このとき <math>i</math> をone-hotベクトル <math>\boldsymbol{i} \in \{0, 1\}^K</math> へ変換することで、LUT関数は次の式で表される。

<math>\boldsymbol{x} = W \boldsymbol{i}</math>

パラメータ行列 <math>W \in \mathbb{R}^{N \times K}</math> は出力ベクトルを列方向にconcatした形に対応しており、LUTそのものになっている。

ここでLUT関数が組み込まれたネットワーク <math>\widehat{\boldsymbol{o}} = f(LUT(\boldsymbol{i})) </math> を考えると、LUT行列 <math>W</math> を変化させれば <math>\widehat{\boldsymbol{o}} </math> が変化する。よって学習データ <math>(\boldsymbol{i}, \boldsymbol{o})</math> を用いて <math>\widehat{\boldsymbol{o}} </math> を <math>\boldsymbol{o} </math> に近づけるようネットワークのパラメータを更新する（[[機械学習|学習]]する）と、パラメータの一部である <math>W</math> も更新される。これはすなわちLUTを[[機械学習|学習]]させることに相当する。結果としてLUTはそのタスクとネットワークに適した表現を得る。

[[ニューラルネットワーク]]の分野ではLUTを ''Embedding''（埋め込み）と呼び<ref>"<code>torch.nn.Embedding</code> ... A simple lookup table that stores embeddings of a fixed dictionary and size." [https://pytorch.org/docs/stable/generated/torch.nn.Embedding.html torch.nn - PyTorch docs]. 2022-06-22閲覧.</ref>、[[誤差逆伝播法]]を用いてLUTを含むネットワークの学習をおこなう。

== 参考文献 ==
{{脚注ヘルプ}}
{{reflist}}

== 関連項目 ==
* [[テーブルジャンプ]]
* [[メモ化]]
* [[メモリバウンド]]
* [[シフトレジスタルックアップテーブル]]
* [[パレット (コンピューティング)|パレット]]および[[CLUT]]（コンピュータグラフィックスでの使用法）
* [[3D LUT]]（映画などでの使用法）

== 外部リンク ==
* [http://en.wikibooks.org/wiki/360_Assembly/Branch_Instructions Fast table lookup using input character as index for branch table]
* [http://webster.cs.ucr.edu/AoA/Windows/HTML/TableLookups.html Art of Assembly: Calculation via Table Lookups]
* [http://www.allthesky.com/articles/imagecolor.html Color Presentation of Astronomical Images]
* [http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetTable "Bit Twiddling Hacks" (includes lookup tables)] [[スタンフォード大学]]のSean Eron Andersonによる
* [http://apl.jhu.edu/~paulmac/c++-memoization.html Memoization in C++] [[ジョンズ・ホプキンス大学]]のPaul McNameeによる測定結果
* [https://books.google.co.uk/books?id=gJrmszNHQV4C&lpg=PT169&dq=beautiful+code+%22population+count%22&pg=PT169&hl=en#v=onepage&q=beautiful%20code%20%22population%20count%22&f=false "The Quest for an Accelerated Population Count" ] by  Henry S. Warren, Jr.

{{DEFAULTSORT:るつくあつふてえふる}}
[[Category:データ構造]]
[[Category:コンピューターのパフォーマンス]]
[[Category:ソフトウェア最適化]]