ルックアップテーブル

コンピュータサイエンスにおいて、ルックアップテーブル（LUT）は、実行時の計算をより単純な配列インデックス操作に置き換える配列であり、ダイレクトアドレッシングと呼ばれるプロセスです。メモリから値を取得する方が「高価な」計算や入出力操作を実行するよりも速いことが多いため、処理時間の節約は大幅になる可能性があります。^[1]テーブルは事前に計算されて静的プログラムストレージに格納されることもあれば、プログラムの初期化フェーズ（メモ化）の一部として計算（または「プリフェッチ」 ）されることもあれば、アプリケーション固有のプラットフォームのハードウェアに格納されることもあります。ルックアップテーブルは、配列内の有効な（または無効な）項目のリストと照合することによって入力値を検証するためにも広く使用され、一部のプログラミング言語では、一致する入力を処理するためのポインタ関数（またはラベルへのオフセット）が含まれる場合があります。FPGAでは、再構成可能なハードウェア実装のルックアップテーブルも広範に使用して、プログラム可能なハードウェア機能を提供します。 LUTはハッシュテーブルと異なり、キー で値を取得するために、ハッシュテーブルではスロット に値を格納するが、はハッシュ関数、つまり はスロットの計算に使用される。一方、LUTの場合は、値はスロット に格納されるため、直接アドレス指定可能である。^{[2] : 466}${\displaystyle v}$${\displaystyle k}$${\displaystyle v}$${\displaystyle h(k)}$${\displaystyle h}$${\displaystyle k}$${\displaystyle v}$${\displaystyle k}$

コンピュータが登場する前は、三角法、対数、統計密度関数などの複雑な関数の手計算を高速化するために値の参照テーブルが使用されていました。 ^[3]

古代（499年）のインドでは、アーリヤバータがサンスクリット文字をベースとした記数法でコード化した最初の正弦表の1つを作成した。493年、アキテーヌのヴィクトリウスは、2から50までのあらゆる数の積を（ローマ数字で）示す98列の掛け算表を記し、各行は「1000から始まり、100ずつ下がって100になり、10ずつ下がって10になり、1ずつ下がって1/144までの分数が続く数のリスト」であった^{[4]。現代の学校では、最もよく使用される数（9 x 9または12 x 12まで）の計算を避けるために、「}掛け算表」を暗記するように教えられることが多い。

コンピュータの歴史の初期には、入出力操作は、当時のプロセッサ速度と比較しても特に遅いものでした。静的ルックアップ テーブル (プログラムに埋め込まれている) または最も頻繁に発生するデータ項目のみを含む動的プリフェッチ配列を作成することにより、手動キャッシュの形式でコストのかかる読み取り操作を削減することは理にかなっています。現在ではこのプロセスが自動化されるシステム全体のキャッシュが導入されていますが、アプリケーション レベルのルックアップ テーブルは、ほとんど変更されないデータ項目のパフォーマンスを依然として向上させることができます。

ルックアップテーブルは、コンピュータのスプレッドシートに実装された最も初期の機能の1つであり、 VisiCalcの初期バージョン（1979年）にはLOOKUP、元々の20個の関数の中に関数が含まれていました。^[5]これに続いて、Microsoft ExcelVLOOKUPなどの後続のスプレッドシートでは、垂直または水平の表でのルックアップを簡素化するための特殊な関数と関数が追加されましたHLOOKUP。Microsoft Excelでは、このXLOOKUP機能は2019年8月28日から展開されています。

LUT の性能は検索操作では保証されていますが、2 つのエンティティまたは値が同じキーを持つことはできません。キーが描画される領域のサイズが大きい場合、メモリに格納するのは非現実的または不可能になる可能性があります。したがって、この場合はハッシュ テーブルが望ましい代替手段となります。^{[2] : 468}${\displaystyle O(1)}$${\displaystyle k}$ ${\displaystyle \cup}$

単純なハッシュ関数の検索では、符号なしの生データ値が1次元テーブルへのインデックスとして直接使用され、結果が抽出されます。範囲が小さい場合、これは最も高速な検索の1つであり、分岐なしのバイナリ検索速度を超えて、定数時間で実行されます。^[6]

多くのコンピュータで解くのにコストがかかる離散問題の 1 つは、(2 進) 数で 1 に設定されているビットの数を数える問題であり、人口関数と呼ばれることもあります。たとえば、10 進数「37」は 2 進数では「00100101」なので、2 進数で「1」に設定されているビットが 3 つあります。^{[7] : 282}

intの1ビットをカウントするように設計されたCコードの簡単な例は、次のようになります。^{[7] : 283}

int count_ones ( unsigned int x ) { int result = 0 ; while ( x != 0 ) { x = x & ( x - 1 ); result ++ ; } return result ; }    
     
      
          
    
  
   

上記の実装では、32ビット値の評価に32回の演算が必要であり、分岐により数クロックサイクルかかる可能性があります。これは、ルックアップテーブルに「展開」することができ、ルックアップテーブルでは、パフォーマンスを向上させるために、単純なハッシュ関数を使用します。 ^{[7] ：282-283}

256 エントリのビット配列bits_setは、各可能なバイト値に 1 ビットが設定されている数 (例: 0x00 = 0、0x01 = 1、0x02 = 1 など) を指定して構築されます。実行時アルゴリズムを使用してbits_set配列を生成することもできますが、サイズを考慮するとクロック サイクルの使用効率が悪くなるため、事前に計算されたテーブルが使用されます。ただし、コンパイル時スクリプトを使用してテーブルを動的に生成し、ソース ファイルにテーブルを追加することもできます。整数の各バイトの 1 の合計は、各バイトの簡単なハッシュ関数検索によって計算できます。したがって、分岐を効果的に回避して、パフォーマンスを大幅に向上できます。^{[7] : 284}

int count_ones ( int input_value ) { union four_bytes { int big_int ; char each_byte [ 4 ]; }オペランド= input_value ; const int bits_set [ 256 ] = { 0 、1 、1 、2 、1 、2 、2 、3 、1 、2 、 2 、 3 、2 、3 、3 、4 、1 、2 、2 、3 、2 、3 、3 、 4 、 2 、 3 、 3 、3 、4 、3 、4 、4 、 5 、 1 、 2 、2 、 3 、 2 、 3 、 3 、 4 、2 、 3 、3 、4 、3 、4 、4 、5 、1 、2 、 2 、 3 、 2 、 3 、3 、4 、2 、3 、 3 、 4 、3 、4 、 4 、 5 、 2 、 3 、 3 、 4 、 3 、 4 、 4 、5 、2 、3 、3 、4 、3 、 4 、 4 、 5 、 3 、 3 、 4 、4 、5 、3 、4、4、5、4、5、5、6、1、2、2、3、2、3、3、4、2、3、3、4、3、4、4、5、2、3、3、4、3、4、4 、5、3​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​   
    
     
     
     
      
                             
                             
                             
                      、4、4、5、4、5、5、6、2、3、3、4、3、4、4、5、3、4、4、5、4、5、5、6、3、4​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​ 、4、5、4、5、5、6、4、5、5、6、5、6、6、7、1、2、2、3、2、3、3、4、2、3、3​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​ 、4 、3 、4 、4 、5 、2 、3 、3 、4 、3 、4、4、5、3、4、4、5、4、5、5、6、2、3、3、4、3、4、4、5、3、4、4、5、4、5 、​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​5、6、3、4、4、5、4、5、5、6、4、5、5、6、5、6、6、7、2、3、3、4​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​       
                             
                             
                             
                             
         、3、4、4、5、3、4、4、5、4、5、5、6、3、4、4、5、4、5、5、6、4、5、5、6、5​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​ 、6、6、7、3、4、4、5、4、5、5、6、4、5、5、6、5、6、6、7、4、5、5、6、5、6​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​ 、6 、7 、5 、6 、6 、7 、6 、7 、7 、8 };戻り値( bits_set [オペランド.各バイト[ 0 ]] + bits_set [オペランド.各バイト[ 1 ]] + bits_set [オペランド.各バイト[ 2 ]] + bits_set [オペランド.各バイト[ 3 ]]); }}                    
                             
                     
      
            

「ルックアップテーブル（LUT）は、計算コストが高く、キャッシュコストが低い関数の評価を最適化するための優れた手法です。...テーブルのサンプル間に含まれるデータ要求については、補間アルゴリズムにより、近くのサンプルを平均化することで適切な近似値を生成できます。」^[8]

画像処理などのデータ分析アプリケーションでは、ルックアップ テーブル (LUT) を使用して、入力データをより望ましい出力形式に変換できます。たとえば、土星のグレースケール画像をカラー画像に変換して、土星の環の違いを強調することができます。

画像処理では、ルックアップ テーブルはLUT (または 3DLUT)と呼ばれることが多く、インデックス値の範囲ごとに出力値を提供します。カラーマップまたはパレットと呼ばれる一般的な LUT は、特定の画像を表示する色と強度値を決定するために使用されます。コンピューター断層撮影では、「ウィンドウ処理」は、測定された放射線の強度をどのように表示するかを決定するための関連概念を指します。

ルックアップテーブルを使用して実行時の計算を減らす典型的な例は、値の正弦などの三角法の計算結果を取得することです。 ^[9]三角関数の計算は、コンピューティングアプリケーションの速度を大幅に低下させる可能性があります。同じアプリケーションでも、最初に複数の値の正弦を、たとえば各度の整数に対して事前に計算しておくと、はるかに早く終了できます (テーブルはコンパイル時に静的変数として定義できるため、繰り返し実行時のコストが削減されます)。プログラムで値の正弦が必要な場合、数式で計算する代わりに、ルックアップテーブルを使用してメモリアドレスから最も近い正弦値を取得したり、目的の値の正弦を補間したりすることもできます。ルックアップテーブルは、このようにコンピュータシステムの数値演算コプロセッサで使用できます。ルックアップテーブルのエラーは、Intel の悪名高い浮動小数点除算のバグの原因でした。

単一変数の関数 (正弦や余弦など) は、単純な配列で実装できます。2 つ以上の変数を含む関数には、多次元配列のインデックス作成技術が必要です。後者の場合、限られた範囲のx 値と y 値に対してx ^{y を}計算する関数の代わりに、 power[x][y]の 2 次元配列を使用できます。複数の結果を持つ関数は、構造体の配列であるルックアップ テーブルを使用して実装できます。

前述のように、テーブルと少量の計算 (多くの場合、補間を使用) を組み合わせて使用​​する中間的なソリューションがあります。補間と組み合わせた事前計算により、事前計算された 2 つの値の間にある値に対してより高い精度を実現できます。この手法は実行に少し時間がかかりますが、精度を必要とするアプリケーションでは精度を大幅に向上できます。事前計算される値によっては、補間を使用した事前計算を使用して、精度を維持しながらルックアップ テーブルのサイズを縮小することもできます。

ルックアップ テーブルは効果的であることが多いものの、LUT が置き換える計算が比較的単純な場合は、ルックアップ テーブルを使用すると、それでもなお重大なペナルティが発生する可能性があります。メモリ検索時間とメモリ要件の複雑さにより、単純な数式計算で必要となるものと比較して、アプリケーションの動作時間とシステムの複雑さが増加する可能性があります。キャッシュを汚染する可能性も問題になる可能性があります。大きなテーブルに対するテーブル アクセスは、ほぼ確実にキャッシュ ミスを引き起こします。この現象は、プロセッサがメモリを上回るにつれて、ますます問題になりつつあります。同様の問題は、コンパイラの最適化である再マテリアライゼーションでも発生します。Javaプログラミング言語などの一部の環境では、テーブル ルックアップは、ルックアップごとに追加の比較と分岐を伴う必須の境界チェックのために、さらにコストがかかる可能性があります。

必要な操作のためのルックアップ テーブルを作成できる場合、2 つの基本的な制限があります。1 つは、使用可能なメモリの量です。テーブルに使用可能なスペースよりも大きいルックアップ テーブルを作成することはできませんが、ルックアップ時間を犠牲にしてディスク ベースのルックアップ テーブルを作成することは可能です。もう 1 つは、最初にテーブル値を計算するために必要な時間です。これは通常 1 回だけ実行する必要がありますが、非常に長い時間がかかる場合は、ルックアップ テーブルの使用が不適切なソリューションになる可能性があります。ただし、前述のように、多くの場合、テーブルは静的に定義できます。

ほとんどのコンピュータは基本的な算術演算しか実行できず、与えられた値の正弦を直接計算することはできません。代わりに、CORDICアルゴリズムまたは次のテイラー級数などの複雑な式を使用して、正弦の値を高精度で計算します。^{[10] : 5}

${\displaystyle \operatorname {sin} (x)\approx x-{\frac {x^{3}}{6}}+{\frac {x^{5}}{120}}-{\frac {x^{7}}{5040}}}$（xが0に近い場合）

しかし、これは計算コストが高く、特に低速プロセッサでは計算コストが高く、特に従来のコンピュータグラフィックスでは、毎秒何千もの正弦値を計算する必要のあるアプリケーションが多数あります。一般的な解決策は、最初に均等に分布した多数の値の正弦を計算し、次に配列のインデックス操作によってxに最も近い値の正弦を選択してxの正弦を見つけることです。正弦は変化率が制限された連続関数であるため、これは正しい値に近くなります。 ^{[10] : 6}たとえば、次のようになります。^{[11] : 545–548}

実数配列sine_table [ - 1000 .. 1000 ] xが- 1000から1000の場合sine_table [ x ] = sine ( pi * x / 1000 )  
     
          

関数lookup_sine ( x )はsine_table [ round ( 1000 * x / pi )]を返します。 
         

残念ながら、テーブルにはかなりのスペースが必要です。IEEE 倍精度浮動小数点数を使用する場合、16,000 バイト以上が必要になります。サンプル数を減らすこともできますが、精度は大幅に低下します。1 つの良い解決策は線形補間です。線形補間では、テーブルの値の両側の 2 つのポイント間に線を引き、その線上に答えを配置します。この方法でも計算は高速で、正弦関数などの 滑らかな関数の場合ははるかに正確です。線形補間を使用した例を次に示します。

関数lookup_sine ( x ) x1 = floor ( x * 1000 / pi ) y1 = sine_table [ x1 ] y2 = sine_table [ x1 + 1 ]戻り値y1 + ( y2 - y1 ) * ( x * 1000 / pi - x1 ) 
      
      
      
       

線形補間は連続的な補間関数を提供しますが、一般に連続的な導関数を持ちません。連続的で連続的な1 次導関数を持つテーブル参照のより滑らかな補間には、 3 次エルミート スプラインを使用する必要があります。

補間を使用する場合、非均一サンプリングを使用することでルックアップ テーブルのサイズを縮小できます。つまり、関数が直線に近い場合はサンプル ポイントを少なくし、値が急激に変化する場合はサンプル ポイントを多く使用して、近似値を実際の曲線に近づけます。詳細については、補間を参照してください。

ストレージ キャッシュ (ファイル用のディスク キャッシュ、またはコードまたはデータ用のプロセッサ キャッシュを含む) も、ルックアップ テーブルのように機能します。テーブルは、低速の外部メモリに保存されるのではなく、非常に高速なメモリを使用して構築され、外部メモリ (またはディスク) アドレス (特に、考えられるすべての外部アドレスの最下位ビット) を構成するビットのサブ範囲に対して 2 つのデータを保持します。

• 1 つの部分 (タグ) には、アドレスの残りのビットの値が含まれます。これらのビットが読み取りまたは書き込みのメモリ アドレスのビットと一致する場合、もう 1 つの部分にはこのアドレスのキャッシュされた値が含まれます。
• もう一方の部分は、そのアドレスに関連付けられたデータを管理します。

単一の (高速) ルックアップが実行され、目的の外部ストレージ アドレスの最下位ビットで指定されたインデックスにあるルックアップ テーブル内のタグが読み取られ、メモリ アドレスがキャッシュによってヒットするかどうかが判断されます。ヒットが見つかった場合、外部メモリへのアクセスは必要ありません (書き込み操作の場合は、キャッシュされた値をしばらくしてから低速メモリに非同期で更新する必要がある場合や、キャッシュ内の位置を置き換えて別のアドレスをキャッシュする必要がある場合を除く)。

デジタル ロジックでは、ルックアップ テーブルは、選択ラインがアドレス信号によって駆動され、入力が配列に含まれる要素の値であるマルチプレクサを使用して実装できます。これらの値は、目的が特定の機能であるASICのようにハードワイヤードにすることも、設定可能な値を可能にするD ラッチによって提供することもできます。( ROM、EPROM、EEPROM、またはRAM )

nビット LUT は、関数の真理値表をLUT に格納することで、任意のn入力ブール関数をエンコードできます。これはブール論理関数をエンコードする効率的な方法であり、 4～ 6 ビットの入力を持つ LUT は、再構成可能なハードウェア ロジック機能を提供する最新のフィールド プログラマブル ゲート アレイ(FPGA) の重要なコンポーネントです。

データ収集および制御システムでは、ルックアップ テーブルは次のような操作を実行するためによく使用されます。

• 校正データの適用により、校正されていない測定値または設定値に補正を適用します。
• 測定単位の変換を行うこと。
• 一般的なユーザー定義の計算を実行します。

一部のシステムでは、これらの計算のためにルックアップ テーブルの代わりに 多項式が定義されることもあります。

• 連想配列
• ブランチテーブル
• ギャルの正確な表
• メモ化
• メモリバウンド関数
• 最近傍補間
• シフトレジスタルックアップテーブル
• パレット、別名カラールックアップテーブルまたはCLUT – コンピュータグラフィックスでの使用
• 3Dルックアップテーブル– 映画業界での使用

• 入力文字をブランチテーブルのインデックスとして使用する高速テーブル検索
• 組み立ての技術: テーブル参照による計算
• 「ビット操作ハック」（ルックアップテーブルを含む）スタンフォード大学のショーン・エロン・アンダーソン著
• ジョンズ・ホプキンス大学のポール・マクネーミーによるC++でのメモ化による節約効果
• 「人口カウントの加速化の探求」ヘンリー・S・ウォーレン・ジュニア著