如何优化算法设计？

发布时间：2024-04-29 03:32:45 人气：作者：佚名

参考《大话数据结构》一书第2.6节算法设计的要求，可知好的算法应具有正确性、可读性、健壮性、高效率和低存储量的特征，具体介绍如下：

正确性
算法的正确性是指算法至少应该具有输入、输出和加工处理无歧义性、能正确反映问题的需求、能够得到问题的正确答案，具体可分以下四个层次：
（1）算法程序没有语法错误。
（2）算法程序对于合法的输入数据能够产生满足要求的输出结果。
（3）算法程序对于非法的输入数据能够得出满足规格说明的结果。
（4）算法程序对于精心选择的，甚至刁难的测试数据都有满足要求的输出结果。
通常把层次3作为一个算法是否正确的标准。
可读性
算法设计的一大目的是为了便于阅读、理解和交流。
健壮性
当输入数据不合法时，算法也能做出相关处理，而不是产生异常或莫名其妙的结果。
时间效率高和存储率低
通俗的说，就是用最少的资源，花最少的时间，把事情做到最好。这也是实际算法优化中主要考虑的内容。

实际运用中的算法优化举例如下，内容摘自
https://blog.csdn.net/liuchen1206/article/details/79351137 （《x264性能优化》）

1、算法结构优化

实现同样的应用功能可采用多种不同的算法和方法。
以H.264中的运动估计算法为例，全搜索算法和快速运动估计算法实现的编码效率基本一致，但是后者的处理时间可以节省10~20倍，时间代价小得多。（注：优化第4点，提高时间效率）
递归算法非递归化，虽然递归算法使得程序结构清晰，可读性高，但却需要执行大量的过程调用，堆栈保存等，运行效率低下。（注：优化第4点，在第2点和第4点中取舍）

2、编译优化（注：结合硬件优化第4点）

现在很多编译器都实现了较强的代码优化功能，多数编译器都基于数据流分析以实现别名分析（通过变量重命名来消除数据相关，提高流水线的执行效率），常数折叠，公共子表达式消除、冗余代码删除，循环逆转和循环展开等与体系结构无关的优化，例如GNU gcc就是个很好的编译工具。
还有借用并行程序设计技术，进行相关性分析，并通过相应技术是程序具有更好的局部性以提高Cashe命中率。对于GCC中采用-O -O2 -O3 -O4等选项选择针对速度/面积等性能优化,另外debug版本由于程序中加入较多的debug参数,影响程序效率,上面x264的debug和 release运行效率的对比可见一斑.编译优化属于静态优化，由编译器自动完成，但是编译器很难得到程序的语义信息，算法流程等信息。所以需要我们手工编程优化以最大程度提高程序运行效率。

3、程序优化（注：结合软件平台优化第4点）

a)使用inline函数，很多编译器支持inline关键字，减少函数调用开销却增加了代码量。
b)针对程序运行平台，如 x86(Intel)，Xscale，ARM，DSP等不同构架，可采用相应的汇编优化，将主要时耗部分/循环调用等，进行汇编指令优化 MMX,SSE,WiMMX,ARM/Thumb指令,DSP汇编等，或者采用专用的库函数,如针对Intel CPU/Xscale构架的嵌入式系统（PXA255,PXA270等）可使用IPP/GPP库，提高程序效率。
c)对于DSP系统，由于有多个并行处理单元，编译器会并行优化，所以需要尽量减少频繁小循环跳转，将循环展开，同时减少循环或内层循环也可以提高CPU的流线效率，尽量不断流。
d)在 Switch语句中根据发生频率排序case语句，编译器对于switch语句将生成if-else-if的嵌套代码，按概率排序可提高效率（FPGA/CPLD等逻辑器件中，采用VHDL语言描述的switch是生成多个逻辑器件，并且完全并行的）。
e)减少函数调用参数.
f)减少耗时的浮点数操作，除法操作等降低CPI。
以上内容摘自 https://blog.csdn.net/liuchen1206/article/details/79351137 （《x264性能优化》）

未完待续……