空間換時間，查表法的經(jīng)典例子

前言

上一篇分享了：C語言精華知識：表驅動法編程實踐

這一篇再分享一個查表法經(jīng)典的例子。

我們怎么衡量一個函數(shù)/代碼塊/算法的優(yōu)劣呢？這需要從多個角度看待。本篇筆記我們先不考慮代碼可讀性、規(guī)范性、可移植性那些角度。

在我們嵌入式中，我們需要根據(jù)實際資源的情況來設計我們的代碼。

比如當我們能用的存儲器空間極其有限的情況，我之前就有遇到這樣子的情況，我能用的flash空間只有4KB，但是要實現(xiàn)的功能很多，稍微不注意就超了，這種情況下我們就得多考慮程序占用方面的問題。

如果我們的存儲器空間很足，有時候可以犧牲一些存儲器空間來換取我們程序的運行速度。查表法就是以空間換取時間的典型例子。下面看一個經(jīng)典的例子：

基礎例子

編寫程序統(tǒng)計一個4bit數(shù)據(jù)（0x0~0x0F）中1的個數(shù)。這里提供兩種方法：

1、方法一：常規(guī)法

常規(guī)法就是依次判斷這個4bit的數(shù)據(jù)的每一位是否為1，并用一個計數(shù)變量把1的個數(shù)記錄下來：

左右滑動查看全部代碼>>>

#include <stdio.h>

/* 測試結果 */
struct test_res
{
 unsigned int data;  /* 數(shù)據(jù)         */
 unsigned int count; /* 數(shù)據(jù)中1的個數(shù) */
};

struct test_res get_test_res(unsigned int data)
{
 /* 保存測試結果 */
 struct test_res res;
 
 /* 保證數(shù)據(jù)總會在0~0xf之間 */
 unsigned int temp = data & 0xf;  
 
 res.count = 0;
 res.data = temp;
 
 /* 循環(huán)判斷每一位 */
 for (int i = 0; i < 4; i++)
 {
  if (temp & 0x01)
  {
   res.count++;
  }
  temp >>= 1;
 }
 
 return res;
}

int main(void)
{
 struct test_res res = {0};
 
 for (int i = 0; i < 32; i++)
 {
  res = get_test_res(i);
  printf("%2d中二進制位為1的個數(shù)有%d\n", res.data, res.count);
 }

 return 0;
}

運行結果：

unsigned int temp = data & 0xf; 語句就是為了保證數(shù)據(jù)都是在0x0~0xf之間，即0~15為一個周期，如果輸入的數(shù)據(jù)為16，則當做0來看待，輸入的數(shù)據(jù)為17，則當做1來看待……

2、方法二：查表法

這個例子也可以用查表法來做，把0x0~0xF中的所有數(shù)據(jù)中每個數(shù)據(jù)的1的個數(shù)都記錄下來，存放到一個表中。

這樣一來，數(shù)據(jù)與數(shù)據(jù)中1的個數(shù)就建立起了一一對應關系，我們就可以通過數(shù)組索引來獲取我們想要的結果：

左右滑動查看全部代碼>>>

int table[16] = {0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4};

struct test_res get_test_res(unsigned int data)
{
 /* 保存測試結果 */
 struct test_res res;
 
 /* 保證數(shù)據(jù)總會在0~0xf之間 */
 unsigned int temp = data & 0xf;  
 
 /* 獲取結果 */
 res.data = temp;
 res.count = table[temp];
 
 return res;
}

常規(guī)法使用for循環(huán)的方式來實現(xiàn)，缺點是占用了不少處理器的時間；查表法的優(yōu)點彌補了常規(guī)法的不足，但是額外占用了一些靜態(tài)空間。

這里針對這個應用而言處理的數(shù)據(jù)還是比較簡單的，數(shù)據(jù)范圍只是0x0~0xF之間，所以這兩種方式可能也都差不多。

那如果以上題目稍微改一下：編寫程序統(tǒng)計一個8bit、16bit數(shù)據(jù)中1的個數(shù)。查表法換取的時間就比較明顯了。

延伸例子

下面我們先來看一下編寫程序統(tǒng)計一個8bit（0x0~0xFF）數(shù)據(jù)中1的個數(shù)的情況。

1、常規(guī)法

把以上代碼稍微改一下就可以：

左右滑動查看全部代碼>>>

struct test_res get_test_res(unsigned int data)
{
 /* 保存測試結果 */
 struct test_res res;
 
 /* 保證數(shù)據(jù)總會在0~0xf之間 */ 
 unsigned int temp = data & 0xff;  
 
 res.count = 0;
 res.data = temp;
 
 /* 循環(huán)判斷每一位 */
 for (int i = 0; i < 16; i++)
 {
  if (temp & 0x01)
  {
   res.count++;
  }
  temp >>= 1;
 }
 
 return res;
}

運行結果：

2、查表法

上面的數(shù)據(jù)范圍僅僅是0x0~0xF，數(shù)據(jù)量比較少，建立數(shù)據(jù)表也比較容易。

這里的數(shù)據(jù)量范圍變成了0x0~0xFF，比原來多了兩百多個數(shù)據(jù)，這也還可以接受，也還可以全都列出來。

但是針對這里的這個問題有更好的方法：

在這個問題中，8bit的數(shù)據(jù)可以看做兩個4bit數(shù)據(jù)，這樣就可以共用上面4bit數(shù)據(jù)的數(shù)據(jù)表。所以我們只要把2個4bit數(shù)據(jù)的1的個數(shù)相加，就是最后的結果。

獲取8bit數(shù)據(jù)1的個數(shù)：

左右滑動查看全部代碼>>>

struct test_res get_test_res(unsigned int data)
{
 /* 保存測試結果 */
 struct test_res res;
 
 /* 保證數(shù)據(jù)總會在0~0xf之間 */
 unsigned int temp = data & 0xff;  
 
 /* 獲取低4位中1的個數(shù) */
 unsigned int low_data = temp & 0xf;
 unsigned int low_cnt = table[low_data];
 
 /* 獲取高4位中1的個數(shù) */
 unsigned int high_data = (temp >> 4) & 0xf;
 unsigned int high_cnt = table[high_data];
 
 /* 結果 */
 res.count = low_cnt + high_cnt;
 res.data = temp;
 
 return res;
}

同樣的，獲取16bit數(shù)據(jù)也是類似的，把16bit數(shù)據(jù)當做4個4bit數(shù)據(jù)。

針對以上這個查表法的例子我們可以總結出：

1、數(shù)據(jù)表的確定要合適。像上面8bit的情況再重新創(chuàng)建一個數(shù)據(jù)表把表元素列出來也還可以接受。但是如果是16bit這樣子大數(shù)據(jù)的情況，建立這么大的數(shù)據(jù)表也不太現(xiàn)實。所以需要考慮如何建立一個合適的數(shù)據(jù)表。

2、需要權衡空間換取時間是否值得。像16bit這樣子大數(shù)據(jù)的情況，全部列出來的話會大幅度的增加我們的存儲開銷，這種以空間換時間的情況可能會得不償失。