查找表

在計算機科學中，查找表（Lookup Table）是用簡單的查詢操作替換運行時計算的數組或者關聯數組這樣的數據結構。由於從內存中提取數值經常要比複雜的計算速度快很多，所以這樣得到的速度提升是很顯著的。

一個經典的例子就是三角函數表。每次計算所需的正弦值在一些應用中可能會慢得無法忍受，為了避免這種情況，應用程序可以在剛開始的一段時間計算一定數量的角度的正弦值，譬如計算每個整數角度的正弦值，在後面的程序需要正弦值的時候，使用查找表從內存中提取臨近角度的正弦值而不是使用數學公式進行計算。

在計算機出現之前，人們使用類似的表格來加快手工計算的速度。非常流行的表格有三角、對數、統計density函數。另外一種用來加快手工計算的工具是計算尺。

一些折衷的方法是同時使用查找表和插值這樣需要少許計算量的方法，這種方法對於兩個預計算的值之間的部分能夠提供更高的精度，這樣稍微地增加了計算量但是大幅度地提高了應用程序所需的精度。根據預先計算的數值，這種方法在保持同樣精度的前提下也減小了查找表的尺寸。

在圖像處理中，查找表將索引號與輸出值建立聯繫。顏色表作為一種普通的 LUT 是用來確定特定圖像中每一像素所要顯示的顏色和強度。

另外需要注意的一個問題是，儘管查找表經常效率很高，但是如果所替換的計算相當簡單的話就會得不償失，這不僅僅因為從內存中提取結果需要更多的時間，而且因為它增大了所需的內存並且破壞了高速緩存。如果查找表太大，那麼幾乎每次訪問查找表都會導致高速緩存缺失，這在處理器速度超過內存速度的時候愈發成為一個問題。在編譯器優化的再實例化（rematerialization）過程中也會出現類似的問題。在一些環境如Java編程語言中，由於強制性的邊界檢查帶來的每次查找的附加比較和分支過程，所以查找表可能開銷更大。

如何構建查找表有兩個基本的約束條件，一個是可用內存的數量；不能構建一個超過能用內存空間的表格，儘管可以構建一個以查找速度為代價的基於磁盤的查找表。另外一個約束條件是初始計算查找表的時間——儘管這項工作不需要經常做，但是如果耗費的時間不可接受，那麼也不適合使用查找表。

例子

計算正弦值

許多計算機只能執行基本的算術運算，而不能直接計算給定值的正弦值，它們使用如下面泰勒級數這樣的複雜公式計算相當高精度的正弦值：

$\operatorname {sin} (x)\approx x-{\frac {x^{3}}{6}}+{\frac {x^{5}}{120}}-{\frac {x^{7}}{5040}}$（x接近0）然而，這樣的計算費用可能是非常大的，尤其是在低速的處理器上。有許多的應用程序，尤其是傳統的計算機圖形每秒需要幾千次的正弦值計算。一個常用的解決方案就是在剛開始計算許多均勻分布數值的正弦值，然後在表中查找最接近所需x的正弦值，這個值非常接近於正確的數值，這是因為正弦函數是一個有限變化率的連續函數。例如：

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

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

不幸的是，查找表需要一定的空間：如果使用IEEE雙精度浮點數的話，將會需要16,000字節。如果使用較少的採樣點，那麼精度將會大幅度地下降。一個較好的解決方案是線性插值，在表中待計算點左右兩側兩個點的值之間連直線，這個點對應的直線上的值就是所計算點的正弦值。這種方法計算速度也很快，對於如正弦函數這樣的平滑函數來說也有更高的精度。這裡是使用線性插值的一個例子：

 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的位數

population function。例如，數字37的二進制形式是100101，所以它包含有三個設置成1的位。一個計算32位整數中1的位數的簡單c語言程序是：

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

不幸的是，這個簡單的算法在現代的架構上將需要數以百計的時鐘周期才能完成，這是因為它造成了許多分支和循環，而分支的速度是很慢的。這可以使用循環展開和其它一些聰明的技巧進行改進，但是最簡單快捷的解決方案是查找表：簡單地構建一個 包含每個字節可能值包含的1的個數的256個條目的表。然後使用這個表查找整數中每個字節包含的1的個數，並且將結果相加。沒有分支、四次內存訪問、幾乎沒有算術運算，這樣與上面的算法相比就可以大幅度地提升速度。

  int count_ones(unsigned int x){
      return bits_set[x & 255] + bits_set[(x >> 8)& 255]
           + bits_set[(x >> 16)& 255] + bits_set[(x >> 24)& 255];
  }

查找表的其他用途

緩存

主條目：緩存

存儲緩存（包括存儲文件的磁盤緩存，或是存儲代碼或數據的處理器緩存），工作原理也類似查找表。表格被存儲在非常快速的內存上，而不是慢速的外部存儲。

硬件查找表

在數字電路中，n位查找表可以使用多路復用器甚至 ROM 來實現。使用多路復用實現時，選擇線是LUT的輸入而輸入是常數；使用 ROM 實現時，只需將輸入連到地址線上即可直接從數據線讀取結果。n位LUT通過將布爾邏輯函數建模為真值表從而可以編碼任意n位輸入，這是編碼布爾邏輯函數的一個有效途徑，4位LUT實際上是現代FPGA的主要元件。