江苏龙网

  1. 主页 > 生活百科 > >

程序的灵魂——算法

算法

同样的事情，使用不一样的方法去完成，虽然最终的结果一样，但是完成的效率往往不一样 。假如你离家一千公里路程，过年要回家过春节，你可以走路回家，可以骑自行车回家，可以骑摩托车回家，可以坐汽车回家，可以坐火车回家，当然也可以坐飞机回家，虽然最终目的都是到达一千公里的家乡，但是乘坐不同的交通工具，回家的时间各异 。在程序中，这些不同的“交通工具”我们称之为算法 。
代码的运算速度取决于以下几个方面：
（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*YSIZEtypedef 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; /* 如果有更多算术逻辑单元，可以类似的处理代码 */ }}


推荐阅读


上一篇：淘宝店铺退保证金在哪里 淘宝网店的保证金怎么退

下一篇：瑞派宠物医院和瑞鹏宠物医院哪个好 新瑞鹏旗下宠物医院有哪些