查找表
維基百科,自由的 encyclopedia
在計算機科學中,查找表(Lookup Table)是用簡單的查詢操作替換運行時計算的數組或者關聯數組這樣的數據結構。由於從內存中提取數值經常要比複雜的計算速度快很多,所以這樣得到的速度提升是很顯著的。
此條目沒有列出任何參考或來源。 (2016年4月21日) |
一個經典的例子就是三角函數表。每次計算所需的正弦值在一些應用中可能會慢得無法忍受,為了避免這種情況,應用程序可以在剛開始的一段時間計算一定數量的角度的正弦值,譬如計算每個整數角度的正弦值,在後面的程序需要正弦值的時候,使用查找表從內存中提取臨近角度的正弦值而不是使用數學公式進行計算。
在計算機出現之前,人們使用類似的表格來加快手工計算的速度。非常流行的表格有三角、對數、統計density函數。另外一種用來加快手工計算的工具是計算尺。
一些折衷的方法是同時使用查找表和插值這樣需要少許計算量的方法,這種方法對於兩個預計算的值之間的部分能夠提供更高的精度,這樣稍微地增加了計算量但是大幅度地提高了應用程序所需的精度。根據預先計算的數值,這種方法在保持同樣精度的前提下也減小了查找表的尺寸。
在圖像處理中,查找表將索引號與輸出值建立聯繫。顏色表作為一種普通的 LUT 是用來確定特定圖像中每一像素所要顯示的顏色和強度。
另外需要注意的一個問題是,儘管查找表經常效率很高,但是如果所替換的計算相當簡單的話就會得不償失,這不僅僅因為從內存中提取結果需要更多的時間,而且因為它增大了所需的內存並且破壞了高速緩存。如果查找表太大,那麼幾乎每次訪問查找表都會導致高速緩存缺失,這在處理器速度超過內存速度的時候愈發成為一個問題。在編譯器優化的再實例化(英語:rematerialization)(rematerialization)過程中也會出現類似的問題。在一些環境如Java編程語言中,由於強制性的邊界檢查帶來的每次查找的附加比較和分支過程,所以查找表可能開銷更大。
如何構建查找表有兩個基本的約束條件,一個是可用內存的數量;不能構建一個超過能用內存空間的表格,儘管可以構建一個以查找速度為代價的基於磁盤的查找表。另外一個約束條件是初始計算查找表的時間——儘管這項工作不需要經常做,但是如果耗費的時間不可接受,那麼也不適合使用查找表。