程序的灵魂——算法

同样的事情，使用不一样的方法去完成，虽然最终的结果一样，但是完成的效率往往不一样。假如你离家一千公里路程，过年要回家过春节，你可以走路回家，可以骑自行车回家，可以骑摩托车回家，可以坐汽车回家，可以坐火车回家，当然也可以坐飞机回家，虽然最终目的都是到达一千公里的家乡，但是乘坐不同的交通工具，回家的时间各异。在程序中，这些不同的“交通工具”我们称之为算法。

代码的运算速度取决于以下几个方面：

（1）处理器的主频和设计架构；

（2）处理器的总线带宽；

（3）程序代码的设计编写；

（4）程序中所使用算法本身的复杂度，比如MPEG比JPEG复杂，JPEG比BMP图片的编码复杂。

比如在一个图像转换的项目中，需要将RGB格式的彩色图像先转换成黑白图像。图像转换的公式如下：

Y = 0.299 * R + 0.587 * G + 0.114 * B;

图像尺寸640*480*24 bits，RGB图像已经按照RGBRGB顺序排列的格式，放在内存里面了。

例如，将这个喷火的战斗机引擎，转换为右边的黑白图片。

 

图片输入和输出的定义如下：

#define XSIZE (640)
#define YSIZE (480)
#define IMGSIZE XSIZE*YSIZE
typedef struct rgb
{
 uint8_t r;
 uint8_t g;
 uint8_t b;
}RGB;
RGB in[IMGSIZE]; /* 未转换的图片数据 */
uint8_t out[IMGSIZE]; /* 转换后的图片数据 */

优化原则：

图像是一个二维数组，我用一个一维数组来存储。编译器处理一维数组的效率要高于二维数组。

第一个程序：

void convert_rgb_image(void)
{
 int i = 0;
 for(i = 0; i < IMGSIZE; i++)
 { 
 uint8_t r = in[i].r; 
 uint8_t g = in[i].g; 
 uint8_t b = in[i].b;
 double temp_out = 0.299 * r + 0.587 * g + 0.114 * b;
 out[i] = temp_out;
 }
}

分别用VC6.0和交叉编译工具，生成2个版本，分别在PC和嵌入式开发板上面运行。

A、在PC上，由于存在硬件浮点处理器，CPU频率也够高，运行时间为20秒。

B、在嵌入式开发板 ，主频时钟比较低，也没有浮点处理器，浮点操作被编译器分解成了整数运算，运行时间为120秒左右。

第一次优化

优化原则：

去掉浮点数运算。

在公式Y = 0.299 * R + 0.587 * G + 0.114 * B中，由于RGB的取值范围都是0~255，只是系数都是浮点数，将RGB的系数转换为：

R的系数：0.299 = 299 / 1000

G的系数：0.587 = 587 / 1000

B的系数：0.114 = 114 / 1000

所以图片转换公式可表示成：Y = （299 * R + 587 * G + 114 * B）/ 1000

即转换图片的程序变为：

void convert_rgb_image(void)
{
 int i = 0;
 for(i = 0; i < IMGSIZE; i++)
 { 
 uint8_t r = in[i].r; 
 uint8_t g = in[i].g; 
 uint8_t b = in[i].b;
 double temp_out = (299 * r + 587 * g + 114 * b) / 1000;
 out[i] = temp_out;
 }
}

再次编译生成两个平台的应用程序运行，发现：

A、在PC上运行的时间为2秒

B、在嵌入式开发板上运行的时间为45秒

第二次优化

优化原则：

处理器在进行除法运算时，处理速度比较慢，去除除法操作

将公式Y = （299 * R + 587 * G + 114 * B）/ 1000的RGB的系数优化如下：

R的系数：0.299 = 299 / 1000 = 1224 / 4096

G的系数：0.587 = 587 / 1000 = 2404 / 4096

B的系数：0.114 = 114 / 1000 = 467 / 4096

由于4096是2的倍数，除法可用效率更高的移位操作进行优化，所以图片转换公式为：

Y = (1224 * R + 2404 * G + 467 * G) >> 12

所以图片转换程序为：

void convert_rgb_image(void)
{
 int i = 0;
 for(i = 0; i < IMGSIZE; i++)
 { 
 int r = 1224 * in[i].r; 
 int g = 2404 * in[i].g; 
 int b = 467 * in[i].b;
 int temp_out = (r + g + b) >> 12;
 out[i] = temp_out;
 }
}

再次编译运行，发现在嵌入式开发板上运行时间为30秒。

第三次优化

优化原则：

由于每一次转换的RGB系数都要经过计算得到，减少各个系数的计算次数。

优化代码如下：

#define RGB_SIZE (256)
int R[RGB_SIZE];
int G[RGB_SIZE];
int B[RGB_SIZE];
void rgb_table_init(void)
{
 int i = 0;
 for(i = 0; i < RGB_SIZE; i++)
 {
 R[i] = 1224 * i;
 R[i] = R[i] >> 12;
 G[i] = 2404 * i;
 G[i] = G[i] >> 12;
 B[i] = 467 * i;
 B[i] = B[i] >> 12;
 }
}
void convert_rgb_image(void)
{
 int i = 0;
 for(i = 0; i < IMGSIZE; i++)
 { 
 int r = R[in[i].r]; 
 int g = G[in[i].g]; 
 int b = B[in[i].b];
 int temp_out = r + g + b;
 out[i] = temp_out;
 }
}

再次编译运行，发现在嵌入式开发板上运行时间为2秒。

第四次优化

优化原则：

32位的嵌入式CPU，都至少有2个算术逻辑单元(ALU)，让2个ALU一起运行

优化代码如下：

#define RGB_SIZE (256)
int R[RGB_SIZE];
int G[RGB_SIZE];
int B[RGB_SIZE];
void rgb_table_init(void)
{
 int i = 0;
 for(i = 0; i < RGB_SIZE; i++)
 {
 R[i] = 1224 * i;
 R[i] = R[i] >> 12;
 G[i] = 2404 * i;
 G[i] = G[i] >> 12;
 B[i] = 467 * i;
 B[i] = B[i] >> 12;
 }
}
void convert_rgb_image(void)
{
 int i = 0;
 for(i=0; i < IMGSIZE; i += 2)
 { 
 /* 给第一个算术逻辑单元执行 */
 int r0 = R[in[i].r]; 
 int g0 = G[in[i].g]; 
 int b0 = B[in[i].b];
 int temp_out_0 = r0 + g0 + b0;
 out[i] = temp_out_0;
 /* 给第二个算术逻辑单元执行 */
 int r1 = R[in[i+1].r]; 
 int g1 = G[in[i+1].g]; 
 int b1 = B[in[i+1].b];
 int temp_out_1 = r1 + g1 + b1;
 out[i+1] = temp_out_1;
 /* 如果有更多算术逻辑单元，可以类似的处理代码 */
 }
}

再次编译运行，发现在嵌入式开发板上运行时间为1秒。

第五次优化

优化原则：

由于各个数据类型大小不一样，处理速度也不一样，因此可以对数据类型优化

优化代码如下：

#define RGB_SIZE (256)
uint16_t R[RGB_SIZE];
uint16_t G[RGB_SIZE];
uint16_t B[RGB_SIZE];
void rgb_table_init(void)
{
 uint8_t i = 0;
 for(i = 0; i <= RGB_SIZE; i++)
 {
 R[i] = 1224 * i;
 R[i] = R[i] >> 12;
 G[i] = 2404 * i;
 G[i] = G[i] >> 12;
 B[i] = 467 * i;
 B[i] = B[i] >> 12;
 }
}
inline void convert_rgb_image(void)
{
 uint32_t i = 0;
 for(i=0; i < IMGSIZE; i += 2)
 { 
 /* 给第一个算术逻辑单元执行 */
 uint16_t r0 = R[in[i].r]; 
 uint16_t g0 = G[in[i].g]; 
 uint16_t b0 = B[in[i].b];
 uint32_t temp_out_0 = r0 + g0 + b0;
 out[i] = temp_out_0;
 /* 给第二个算术逻辑单元执行 */
 uint16_t r1 = R[in[i+1].r]; 
 uint16_t g1 = G[in[i+1].g]; 
 uint16_t b1 = B[in[i+1].b];
 uint32_t temp_out_1 = r1 + g1 + b1;
 out[i+1] = temp_out_1;
 }
}

将函数声明为inline,这样编译器就会将其嵌入到母函数中，可以减少CPU调用子函数所产生的开销。

再次编译运行，发现在嵌入式开发板上运行时间为0.5秒。

后续可优化的方向：

（1）将RGB查表的数据放入CPU的高速缓冲存储器（Cache）中，从而提升程序运行时的加载速度。

（2）代码使用汇编语言进行编写

说明：本文来源于网络，我仅仅是对文章进行了一定的整理，删繁就简，如有侵权，请及时联系我删除！