
248
|
第九章
使用既有演算法
現在讀著對快速計算有些感覺了(加法、位移及可能再加上乘法),接下來要分享的是
以最少資源實作特定演算法時最重要的事情:搜尋。如果是標準演算法,試試線上搜尋
或找找數值方法的書。只要找到前人花了時間與精力解釋了如何減少處理循環或 RAM
的使用量,就使用這些成果。但要小心處理版權問題,大多數介紹性說明都能供大眾使
用。網路上能找到許多最佳化演算法的資料,271 頁的「延伸閱讀」中也提供了些可靠
的資料來源,值得放在書架上以備不時之需。
每個演算法大多有許多不同的實作方式,但只有少數能節省目標資源,例如,看看
標準
差
(
standard deviation
)好了。
標準差代表特定集合樣本中各樣本與平均時間的距離,計算過程需要使用每個樣本的值
(x
i
)、平均值(x-bar)及樣本數(N),如同圖 9-3 顯示的方程式(雖然不太直覺,但兩
者等價。)
圖 9-3 計算標準差的兩個等價方程式
如何將這些方式程改為對嵌入式系統友善的形式?先考慮平方根的部分,簡單的答案是
不要計算平方根,雖然平方根會改變答案的數值,但不會改變對樣本差異所提供的資
訊,由於許多人都這麼做,未開方根的標準差值被稱為
變異數
(
variance
)
1
。
(想想只是重新定義目標,我們省下了多少處理器循環!)
接著可以用與方程式相同的作法實作變異數:
uint16 GetVariance(int16_t* samples, uint16_t numSamples, int16_t mean) {
uint32_t sumSquares ...