查看“︁查找表”︁的源代码

{{unreferenced|time=2016-04-21T06:41:12+00:00}}
{{noteTA|G1=IT}}
在[[计算机科学]]中，'''查找表'''（'''L'''ook'''u'''p '''T'''able）是用简单的查询操作替换运行时计算的[[数组]]或者[[关联数组]]这样的[[数据结构]]。由于从内存中提取数值经常要比复杂的计算速度快很多，所以这样得到的速度提升是很显著的。

一个经典的例子就是[[三角函數]]表。每次计算所需的[[正弦]]值在一些应用中可能会慢得无法忍受，为了避免这种情况，应用程序可以在刚开始的一段时间计算一定数量的角度的[[正弦]]值，譬如计算每个整数角度的正弦值，在后面的程序需要正弦值的时候，使用查找表从内存中提取临近角度的正弦值而不是使用数学公式进行计算。

在计算机出现之前，人们使用类似的表格来加快手工计算的速度。非常流行的表格有三角、对数、统计density函数。另外一种用来加快手工计算的工具是[[计算尺]]。

一些折衷的方法是同时使用查找表和[[插值]]这样需要少许计算量的方法，这种方法对于两个预计算的值之间的部分能够提供更高的精度，这样稍微地增加了计算量但是大幅度地提高了应用程序所需的精度。根据预先计算的数值，这种方法在保持同样精度的前提下也减小了查找表的尺寸。

在[[图像处理]]中，查找表将索引号与输出值建立联系。[[调色盘 (电脑图形学)|'''颜色表''']]作为一种普通的 LUT 是用来确定特定图像中每一[[像素]]所要显示的颜色和强度。

另外需要注意的一个问题是，尽管查找表经常效率很高，但是如果所替换的计算相当简单的话就会得不偿失，这不仅仅因为从内存中提取结果需要更多的时间，而且因为它增大了所需的内存并且破坏了[[高速缓存]]。如果查找表太大，那么几乎每次访问查找表都会导致[[高速缓存缺失]]，这在处理器速度超过内存速度的时候愈发成为一个问题。在[[编译器优化]]的{{le|再实例化|rematerialization}}（rematerialization）过程中也会出现类似的问题。在一些环境如[[java|Java编程语言]]中，由于强制性的边界检查带来的每次查找的附加比较和分支过程，所以查找表可能开销更大。

如何构建查找表有两个基本的约束条件，一个是可用内存的数量；不能构建一个超过能用内存空间的表格，尽管可以构建一个以查找速度为代价的基于磁盘的查找表。另外一个约束条件是初始计算查找表的时间——尽管这项工作不需要经常做，但是如果耗费的时间不可接受，那么也不适合使用查找表。

==例子==

===计算正弦值===

许多计算机只能执行基本的算术运算，而不能直接计算给定值的[[正弦]]值，它们使用如下面[[泰勒级数]]这样的复杂公式计算相当高精度的正弦值：

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

<!-- 檔案不存在 [[File:Interpolation example linear.png|部分正弦函数的线性插值|frame|right]] -->
不幸的是，查找表需要一定的空间：如果使用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语言]]程序是：
<syntaxhighlight lang="c">
  int count_ones(unsigned int x){
      int result = 0;
      while(x > 0){
          result += x & 1;
          x = x >> 1;
      }
      return result;
  }
</syntaxhighlight>
不幸的是，这个简单的算法在现代的架构上将需要数以百计的时钟周期才能完成，这是因为它造成了许多分支和循环，而分支的速度是很慢的。这可以使用[[循环展开]]和其它一些聪明的技巧进行改进，但是最简单快捷的解决方案是查找表：简单地构建一个 包含每个字节可能值包含的1的个数的256个条目的表。然后使用这个表查找整数中每个字节包含的1的个数，并且将结果相加。没有分支、四次内存访问、几乎没有算术运算，这样与上面的算法相比就可以大幅度地提升速度。
<syntaxhighlight lang="c">
  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];
  }
</syntaxhighlight>
== 查找表的其他用途 ==

=== 缓存 ===
{{main|缓存}}
存储缓存（包括存储文件的磁盘缓存，或是存储代码或数据的处理器缓存），工作原理也类似查找表。表格被存储在非常快速的内存上，而不是慢速的外部存储。

===硬件查找表===
在[[数字电路]]中，''n''位查找表可以使用[[多路复用器]]甚至 [[ROM]] 来实现。使用多路复用实现时，选择线是LUT的输入而输入是常数；使用 ROM 实现时，只需将输入连到地址线上即可直接从数据线读取结果。''n''位LUT通过将[[布尔逻辑]]函数建模为[[真值表]]从而可以编码任意''n''位输入，这是编码[[布尔逻辑]]函数的一个有效途径，4位LUT实际上是现代[[现场可编程逻辑门阵列|FPGA]]的主要元件。

[[Category:数据结构|C]]
[[Category:数组]]
[[Category:图像处理]]