查找表

例子

计算正弦值

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

sin⁡ ⁡ -->(x)≈ ≈ -->x− − -->x36+x5120− − -->x75040{\displaystyle \operatorname {sin} (x)\approx x-{\frac {x^{3}}{6}}+{\frac {x^{5}}{120}}-{\frac {x^{7}}{5040}}}（x接近0）然而，这样的计算费用可能是非常大的，尤其是在低速的处理器上。有许多的应用程序，尤其是传统的计算机图形每秒需要几千次的正弦值计算。一个常用的解决方案就是在刚开始计算许多均匀分布数值的正弦值，然后在表中查找最接近所需x的正弦值，这个值非常接近于正确的数值，这是因为正连续函数一个有限变化率的连续函数。例如：

File:Interpolation example linear.png 部分正弦函数的线性插值

不幸的是，查找表需要一定的空间：如果使用IEEE双精度浮点数的话，将会需要16,000字节。如果使用较少的采样点，那么精度将会大幅度地下降。一个较好的解决方案是线性插值，在表中待计算点左右两侧两个点的值之间连直线，这个点对应的直线上的值就是所计算点的正弦值。这种方法计算速度也很快，对于如正弦函数这样的平滑函数来说也有更高的精度。这里是使用线性插值的一个例子：

当使用插值的时候，可以得益于不均匀采样，也就是说在接近直线的地方，使用较少的采样点，在变化较快的地方使用较多的采样点以最大限度地接近实际的曲线。更多的信息请参考插值。

计算1的位数

population function。例如，数字37的二进制形式是100101，所以它包含有三个设置成1的位。一个计算32位整数中1的位数的简单c语言程序是：

intcount_ones(unsignedintx){intresult=0;while(x>0){result+=x&1;x=x>>1;}returnresult;}

不幸的是，这个简单的算法在现代的架构上将需要数以百计的时钟周期才能完成，这是因为它造成了许多分支和循环，而分支的速度是很慢的。这可以使用循环展开和其它一些聪明的技巧进行改进，但是最简单快捷的解决方案是查找表：简单地构建一个 包含每个字节可能值包含的1的个数的256个条目的表。然后使用这个表查找整数中每个字节包含的1的个数，并且将结果相加。没有分支、四次内存访问、几乎没有算术运算，这样与上面的算法相比就可以大幅度地提升速度。

intcount_ones(unsignedintx){returnbits_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的主要组件。

免责声明：以上内容版权归原作者所有，如有侵犯您的原创版权请告知，我们将尽快删除相关内容。感谢每一位辛勤著写的作者，感谢每一位的分享。