空間換時(shí)間，查表法的經(jīng)典例子
前言
上一篇分享了：C語言精華知識：表驅(qū)動法編程實(shí)踐
這一篇再分享一個(gè)查表法經(jīng)典的例子。
我們怎么衡量一個(gè)函數(shù)/代碼塊/算法的優(yōu)劣呢？這需要從多個(gè)角度看待。本篇筆記我們先不考慮代碼可讀性、規(guī)范性、可移植性那些角度。
在我們嵌入式中，我們需要根據(jù)實(shí)際資源的情況來設(shè)計(jì)我們的代碼。
比如當(dāng)我們能用的存儲器空間極其有限的情況，我之前就有遇到這樣子的情況，我能用的flash空間只有4KB，但是要實(shí)現(xiàn)的功能很多，稍微不注意就超了，這種情況下我們就得多考慮程序占用方面的問題。
如果我們的存儲器空間很足，有時(shí)候可以犧牲一些存儲器空間來換取我們程序的運(yùn)行速度。查表法就是以空間換取時(shí)間的典型例子。下面看一個(gè)經(jīng)典的例子：
基礎(chǔ)例子
編寫程序統(tǒng)計(jì)一個(gè)4bit數(shù)據(jù)（0x0~0x0F）中1的個(gè)數(shù)。這里提供兩種方法：
1、方法一：常規(guī)法
常規(guī)法就是依次判斷這個(gè)4bit的數(shù)據(jù)的每一位是否為1，并用一個(gè)計(jì)數(shù)變量把1的個(gè)數(shù)記錄下來：
左右滑動查看全部代碼>>>
#include?
/*?測試結(jié)果?*/
struct?test_res
{
?unsigned?int?data;??/*?數(shù)據(jù)?????????*/
?unsigned?int?count;?/*?數(shù)據(jù)中1的個(gè)數(shù)?*/
};
struct?test_res?get_test_res(unsigned?int?data)
{
?/*?保存測試結(jié)果?*/
?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中二進(jìn)制位為1的個(gè)數(shù)有%d\n",?res.data,?res.count);
?}
?return?0;
}
運(yùn)行結(jié)果：
unsigned int temp = data & 0xf; 語句就是為了保證數(shù)據(jù)都是在0x0~0xf之間，即0~15為一個(gè)周期，如果輸入的數(shù)據(jù)為16，則當(dāng)做0來看待，輸入的數(shù)據(jù)為17，則當(dāng)做1來看待……
2、方法二：查表法
這個(gè)例子也可以用查表法來做，把0x0~0xF中的所有數(shù)據(jù)中每個(gè)數(shù)據(jù)的1的個(gè)數(shù)都記錄下來，存放到一個(gè)表中。
這樣一來，數(shù)據(jù)與數(shù)據(jù)中1的個(gè)數(shù)就建立起了一一對應(yīng)關(guān)系，我們就可以通過數(shù)組索引來獲取我們想要的結(jié)果：
左右滑動查看全部代碼>>>
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)
{
?/*?保存測試結(jié)果?*/
?struct?test_res?res;
?
?/*?保證數(shù)據(jù)總會在0~0xf之間?*/
?unsigned?int?temp?=?data?&?0xf;??
?
?/*?獲取結(jié)果?*/
?res.data?=?temp;
?res.count?=?table[temp];
?
?return?res;
}
常規(guī)法使用for循環(huán)的方式來實(shí)現(xiàn)，缺點(diǎn)是占用了不少處理器的時(shí)間；查表法的優(yōu)點(diǎn)彌補(bǔ)了常規(guī)法的不足，但是額外占用了一些靜態(tài)空間。
這里針對這個(gè)應(yīng)用而言處理的數(shù)據(jù)還是比較簡單的，數(shù)據(jù)范圍只是0x0~0xF之間，所以這兩種方式可能也都差不多。
那如果以上題目稍微改一下：編寫程序統(tǒng)計(jì)一個(gè)8bit、16bit數(shù)據(jù)中1的個(gè)數(shù)。查表法換取的時(shí)間就比較明顯了。
延伸例子
下面我們先來看一下編寫程序統(tǒng)計(jì)一個(gè)8bit（0x0~0xFF）數(shù)據(jù)中1的個(gè)數(shù)的情況。
1、常規(guī)法
把以上代碼稍微改一下就可以：
左右滑動查看全部代碼>>>
struct?test_res?get_test_res(unsigned?int?data)
{
?/*?保存測試結(jié)果?*/
?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;
}
運(yùn)行結(jié)果：
2、查表法
上面的數(shù)據(jù)范圍僅僅是0x0~0xF，數(shù)據(jù)量比較少，建立數(shù)據(jù)表也比較容易。
這里的數(shù)據(jù)量范圍變成了0x0~0xFF，比原來多了兩百多個(gè)數(shù)據(jù)，這也還可以接受，也還可以全都列出來。
但是針對這里的這個(gè)問題有更好的方法：
在這個(gè)問題中，8bit的數(shù)據(jù)可以看做兩個(gè)4bit數(shù)據(jù)，這樣就可以共用上面4bit數(shù)據(jù)的數(shù)據(jù)表。所以我們只要把2個(gè)4bit數(shù)據(jù)的1的個(gè)數(shù)相加，就是最后的結(jié)果。
獲取8bit數(shù)據(jù)1的個(gè)數(shù)：
左右滑動查看全部代碼>>>
struct?test_res?get_test_res(unsigned?int?data)
{
?/*?保存測試結(jié)果?*/
?struct?test_res?res;
?
?/*?保證數(shù)據(jù)總會在0~0xf之間?*/
?unsigned?int?temp?=?data?&?0xff;??
?
?/*?獲取低4位中1的個(gè)數(shù)?*/
?unsigned?int?low_data?=?temp?&?0xf;
?unsigned?int?low_cnt?=?table[low_data];
?
?/*?獲取高4位中1的個(gè)數(shù)?*/
?unsigned?int?high_data?=?(temp?>>?4)?&?0xf;
?unsigned?int?high_cnt?=?table[high_data];
?
?/*?結(jié)果?*/
?res.count?=?low_cnt?+?high_cnt;
?res.data?=?temp;
?
?return?res;
}
同樣的，獲取16bit數(shù)據(jù)也是類似的，把16bit數(shù)據(jù)當(dāng)做4個(gè)4bit數(shù)據(jù)。
針對以上這個(gè)查表法的例子我們可以總結(jié)出：
1、數(shù)據(jù)表的確定要合適。像上面8bit的情況再重新創(chuàng)建一個(gè)數(shù)據(jù)表把表元素列出來也還可以接受。但是如果是16bit這樣子大數(shù)據(jù)的情況，建立這么大的數(shù)據(jù)表也不太現(xiàn)實(shí)。所以需要考慮如何建立一個(gè)合適的數(shù)據(jù)表。
2、需要權(quán)衡空間換取時(shí)間是否值得。像16bit這樣子大數(shù)據(jù)的情況，全部列出來的話會大幅度的增加我們的存儲開銷，這種以空間換時(shí)間的情況可能會得不償失。
