查找表
查找表
查找表，計算機術語，是用簡單的查詢操作替換運行時計算的數組或者 associative array 這樣的數據結構。由於從內存中提取數值經常要比複雜的計算速度快很多，所以這樣得到的速度提升是很顯著的。
在計算機科學中，查找表是用簡單的查詢操作替換運行時計算的數組或者 associative array 這樣的數據結構。由於從內存中提取數值經常要比複雜的計算速度快很多，所以這樣得到的速度提升是很顯著的。
一個經典的例子就是三角表。每次計算所需的正弦值在一些應用中可能會慢得無法忍受，為了避免這種情況，應用程序可以在剛開始的一段時間計算一定數量的角度的正弦值，譬如計算每個整數角度的正弦值，在後面的程序需要正弦值的時候，使用查找表從內存中提取臨近角度的正弦值而不是使用數學公式進行計算。
一些折衷的方法是同時使用查找表和插值這樣需要少許計算量的方法，這種方法對於兩個預計算的值之間的部分能夠提供更高的精度，這樣稍微地增加了計算量但是大幅度地提高了應用程序所需的精度。根據預先計算的數值，這種方法在保持同樣精度的前提下也減小了查找表的尺寸/
在圖像處理中，查找表經常稱為LUT，它們將索引號與輸出值建立聯繫。顏色表作為一種普通的 LUT 是用來確定特定圖像所要顯示的顏色和強度。
另外需要注意的一個問題是，儘管查找表經常效率很高，但是如果所替換的計算相當簡單的話就會得不償失，這不僅僅因為從內存中提取結果需要更多的時間，而且因為它增大了所需的內存並且破壞了高速緩存。如果查找表太大，那麼幾乎每次訪問查找表都回倒置 cache miss，這在處理器速度超過內存速度的時候愈發成為一個問題。在編譯器優化的 rematerialization 過程中也會出現類似的問題。在一些環境如Java 編程語言中，由於強制性的邊界檢查帶來的每次查找的附加比較和分支過程，所以查找表可能開銷更大。
何時構建查找表有兩個基本的約束條件，一個是可用內存的數量；不能構建一個超過能用內存空間的表格，儘管可以構建一個以查找速度為代價的基於磁碟的查找表。另外一個約束條件是初始計算查找表的時間——儘管這項工作不需要經常做，但是如果耗費的時間不可接受，那麼也不適合使用查找表。
查找表
無內容
許多計算機只能執行基本的算術運算，而不能直接計算給定值的正弦值，它們使用如下面泰勒級數（en:Taylor series）這樣的複雜公式計算相當高精度的正弦值：
(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)]
Image:Interpolation example linear.png
部分正弦函數的線性插值不幸的是，查找表需要一定的空間：如果使用 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)
當使用插值的時候，可以得益於不均勻採樣，也就是說在接近直線的地方，使用較少的採樣點，在變化較快的地方使用較多的採樣點以最大限度地接近實際的曲線。更多的信息請參考插值。
population function。例如，數字 37 的二進位形式是 100101，所以它包含有三個設置成 1 的位。一個計算 32 位整數中 1 的位數的簡單c語言程序是：
int count_ones(unsigned int x) {
int i, result = 0;
for(i=0; i<32; i++) {
result += x & 1;
x = x >> 1;
}
return result;
}
不幸的是，這個簡單的演演算法在現代的架構上將需要數以百計的時鐘周期才能完成，這是因為它造成了許多分支和循環，而分支的速度是很慢的。這可以使用 loop unrolling 和其它一些聰明的技巧進行改進，但是最簡單快捷的解決方案是查找表：簡單地構建一個 包含每個位元組可能值包含的 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];
}
#define BYTE unsigned char
BYTE numTable[256] =
{
0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3,
3, 4, 3, 4, 4, 5, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3,
4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4,
3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 2, 3, 3, 4, 3,
4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6,
6, 7, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4,
5, 3, 4, 4, 5, 4, 5, 5, 6, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 2, 3, 3, 4, 3, 4, 4, 5, 3,
4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 3, 4,
4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6,
7, 6, 7, 7, 8
};
int main(int argc, char *argv[])
{
int i, num = 0;
BYTE a = 0;
printf("\nPlease Input a BYTE(0~255):");
scanf("%d", &a);
printf("\nthe num of 1 in the BYTE is %d", checknum[a]);
return 0;
}