查找表
维基百科,自由的 encyclopedia
在电脑科学中,查找表(Lookup Table)是用简单的查询操作替换运行时计算的数组或者关联数组这样的数据结构。由于从内存中提取数值经常要比复杂的计算速度快很多,所以这样得到的速度提升是很显著的。
此条目没有列出任何参考或来源。 (2016年4月21日) |
一个经典的例子就是三角函数表。每次计算所需的正弦值在一些应用中可能会慢得无法忍受,为了避免这种情况,应用程式可以在刚开始的一段时间计算一定数量的角度的正弦值,譬如计算每个整数角度的正弦值,在后面的程序需要正弦值的时候,使用查找表从内存中提取临近角度的正弦值而不是使用数学公式进行计算。
在电脑出现之前,人们使用类似的表格来加快手工计算的速度。非常流行的表格有三角、对数、统计density函数。另外一种用来加快手工计算的工具是计算尺。
一些折衷的方法是同时使用查找表和插值这样需要少许计算量的方法,这种方法对于两个预计算的值之间的部分能够提供更高的精度,这样稍微地增加了计算量但是大幅度地提高了应用程式所需的精度。根据预先计算的数值,这种方法在保持同样精度的前提下也减小了查找表的尺寸。
在图像处理中,查找表将索引号与输出值建立联络。颜色表作为一种普通的 LUT 是用来确定特定图像中每一像素所要显示的颜色和强度。
另外需要注意的一个问题是,尽管查找表经常效率很高,但是如果所替换的计算相当简单的话就会得不偿失,这不仅仅因为从内存中提取结果需要更多的时间,而且因为它增大了所需的内存并且破坏了高速缓存。如果查找表太大,那么几乎每次访问查找表都会导致高速缓存缺失,这在处理器速度超过内存速度的时候愈发成为一个问题。在编译器优化的再实例化(英语:rematerialization)(rematerialization)过程中也会出现类似的问题。在一些环境如Java编程语言中,由于强制性的边界检查带来的每次查找的附加比较和分支过程,所以查找表可能开销更大。
如何构建查找表有两个基本的约束条件,一个是可用内存的数量;不能构建一个超过能用内存空间的表格,尽管可以构建一个以查找速度为代价的基于磁碟的查找表。另外一个约束条件是初始计算查找表的时间——尽管这项工作不需要经常做,但是如果耗费的时间不可接受,那么也不适合使用查找表。