尋找表

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

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

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

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

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

另外需要注意的一個問題是，儘管尋找表經常效率很高，但是如果所替換的計算相當簡單的話就會得不償失，這不僅僅因為從主記憶體中提取結果需要更多的時間，而且因為它增大了所需的主記憶體並且破壞了高速緩衝記憶體。如果尋找表太大，那麼幾乎每次訪問尋找表都會導致高速緩衝記憶體缺失，這在處理器速度超過主記憶體速度的時候愈發成為一個問題。在編譯器最佳化的再實例化（英語：rematerialization）（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的主要元件。