如何优化代码(代码调优的6大法则)

seoxin 04-30 14:51 13次浏览

数学家高斯在小学的时候,老师要求从1+2+3开始一直加到100,得出的和是多少?其他同学都费劲地一个数一个数的加,只有小高斯注意到了这些数可以两两配对,相加和为101,所以想到一共有50对101,求和可以用乘法:50X101=5050。

有没有感受到数学思维的强大?其实,编程中的代码优化,就与数学公式有着异曲同工之妙。

小白与大神写同一个程序,小白跑200万条数据,需要8小时,而大神在进行代码优化后,只需要40分钟,效率提高了1200%!

要成为金字塔尖的程序员,不仅要关注程序能不能运行,更要关注程序的运行效率,在每一个字符,每一段语句下功夫,这就是代码调优。为了帮助大家成为一个注重细节的程序员,来看看以下6大代码调优法则!

代码调优6大法则

空间换时间法则

修改数据结构。为了减少数据上的常见运算所需要的时间,我们通常可以在数据结构中增加额外的信息,或者修改数据结构中的信息使之更易访问。

存储预先计算好的结果。对于开销较大的函数,可以只计算一次,然后将计算结果存储起来以减少开销。以后再需要该函数时,可以直接查表而不需要重新计算。

高速缓存。最经常访问的数据,其访问开销应该是最小的。

懒惰求值。除非需要,否则不对任何一项求值。这一策略可以避免对不必要的项求值。

时间换空间法则

堆积。密集存储表示可以通过增加存储和检索数据所需的时间来减少存储开销。尽管堆积有时通过牺牲时间来获取空间,但是这种较小的表示方式处理起来通常更快。

解释程序。使用解释程序通常可以减少表示程序所需的空间,在解释程序中常见的操作序列以一种紧凑的方式表示。

代码空间技术。有时候空间的瓶颈不在于数据,而在于程序本身的规模。在过去的艰苦年代,我见到的图形程序通篇都是类似下面的代码:

格式 1 ( 15px, 粗体, #3E3E3E )

for i = [17, 43] set(i, 68)
for i = [18, 42] set(i, 69)
for j = [81, 91] set(30, j)
for j = [82, 92] set(31, j)

其中set(i, j)“点亮”屏幕位置(i, j)处的图形元素。使用适当的函数,例如用于绘制水平线的hor函数和绘制垂直线的ver函数,就可以使用如下所示的代码替换上面的代码:

hor(17, 43, 68)

hor(18, 42, 69)
vert(81, 91, 30)
vert(82, 92, 31)

上述代码又可以用一个解释程序来替换,这个解释程序从类似下面的数组中读取命令:

h 17 43 68
h 18 42 69
v 81 91 30
v 82 92 31

如果上面的代码仍然占用太多的空间,那么可以为命令(h、v或两个其他命令)分配两个位,并为后面的三个数(这些数是范围0~1023内的整数)各分配10个位。于是,上面的每一行都可以用一个32位的字来表示(当然,这种转换应该由程序来进行)。这种假设的情况揭示了用于节省代码空间的几种通用技术。

函数定义。通过用函数替换代码中的常见模式可以简化上述程序,相应地也就减少了它的空间需求,并增加了其清晰性。这是一个“自底向上”设计的普通例子。

尽管我们不能忽视自顶向下的方法,但是由良好的原始对象、组件和函数所给出的均一的视图可以使系统维护起来更加简单,同时也节省了空间。微软删除了很少使用的函数,将它的整个Windows系统压缩为更加紧凑的Windows CE,使其能在具有更小内存的“移动计算平台”上运行。

更小的用户界面(UI)在窄屏幕的小型机器(范围从嵌入式系统到掌上电脑)上运行得很好,熟悉的界面对用户来说非常方便。更小的应用编程接口(API)使得系统对于Windows API程序员来说很熟悉(并且对于许多程序来说,即使不兼容,也非常接近)。

解释程序。在图形程序中,我们用4字节的解释程序命令替换了一长行的程序文本。描述了一个用于格式信函编程的解释程序,尽管它的主要目的是使编程和维护更加简单,但是它同时也减少了程序的空间。

Kernighan和Pike在他们Practice of Programming一书介绍了“解释程序、编译器和虚拟机”。他们列举了许多例子来支撑他们的结论:

“虚拟机是以前的一个有趣想法,最近借助于Java和Java虚拟机(Java Virtual Machine, JVM)又重新流行起来了;对于高级语言编写的程序来说,它们很容易提供可移植的、高效的表示。”

翻译成机器语言。在节省空间方面,大多数程序员都较少控制的是将源语言转换成机器语言。对编译器进行一些微小更改可以将Unix系统早期版本的代码空间减少5个百分点。

作为最后的手段,程序员可能会考虑到将大型系统中的关键部分用汇编语言进行手工编码。这个高开销、易出错的过程仅能带来一点点好处;不过,该方法还是常常用于一些内存宝贵的系统,比如数字信号处理器。

Apple Macintosh于1984年诞生,当时是一款令人称奇的机器。这款小小的计算机(128 KB RAM)具有令人震惊的用户界面和功能强大的软件集。设计小组预期将制造好几百万台这样的机器,并且只提供64 KB的ROM。

通过谨慎的函数定义(包括泛化运算符、归并函数和删除功能特性)并使用汇编语言手工编码整个ROM程序,该小组将令人难以置信的众多系统功能集成到了一个极微小的ROM上。

他们估计那些经过极度调优的代码(具有谨慎的寄存器分配和指令选择)的规模只有从高级语言编译过来的等价代码的一半(尽管那时编译器已经有了很大的改进)。紧凑的汇编代码运行起来也非常快。

循环法则

将代码移出循环。与其在循环的每次迭代时都执行一次某种计算,不如将其移到循环体外,只计算一次。

合并测试条件。高效的内循环应该包含尽量少的测试条件,最好只有一个。因此,程序员应尽量用一些退出条件来模拟循环的其他退出条件。

循环展开。循环展开可以减少修改循环下标的开销,对于避免管道延迟、减少分支以及增加指令级的并行性也都很有帮助。

删除赋值。如果内循环中很多开销来自普通的赋值,通常可以通过重复代码并修改变量的使用来删除这些赋值。具体说来,删除赋值i = j后,后续的代码必须将j视为i。

消除无条件分支。快速的循环中不应该包含无条件分支。通过“旋转”循环,在底部加上一个条件分支,能够消除循环结束处的无条件分支。该操作通常由优化的编译器完成。

循环合并。如果两个相邻的循环作用在同一组元素上,那么可以合并其运算部分,仅使用一组循环控制操作。

逻辑法则

利用等价的代数表达式。如果逻辑表达式的求值开销太大,就将其替换为开销较小的等价代数表达式。

短路单调函数。如果我们想测试几个变量的单调非递减函数是否超过了某个特定的阈值,那么一旦达到这个阈值就不再需要计算任何变量了。该法则的一个更成熟的应用就是,一旦达到了循环的目的就退出循环。

对测试条件重新排序。在组织逻辑测试的时候,应该将低开销的、经常成功的测试放在高开销的、很少成功的测试前面。

预先计算逻辑函数。在比较小的有限域上,可以用查表来取代逻辑函数。

消除布尔变量。我们可以用if – else语句来取代对布尔变量v的赋值,从而消除程序中的布尔变量。在该if – else语句中,一个分支表示v为真的情况,另一个分支表示v为假的情况。

过程法则

打破函数层次。对于(非递归地)调用自身的函数,通常可以通过将其改写为内联版本并固定传入的变量来缩短其运行时间。

递归函数转换。递归函数的运行时间往往可以通过下面的转换来缩短。将递归重写为迭代,通过使用一个显式的程序栈将递归转化为迭代。(如果函数仅包含一个对其自身的递归调用,那么就没有必要将返回地址存储在栈中)。

如果函数的最后一步是递归调用其自身,那么使用一个到其第一条语句的分支来替换该调用,这通常称为消除尾递归。解决小的子问题时,使用辅助过程通常比把问题的规模变为0或1更有效。

并行性。在底层硬件条件下,我们构建的程序应该尽可能多地挖掘并行性。

表达式法则

编译时初始化。在程序执行之前,应该对尽可能多的变量初始化。

利用等价的代数表达式。如果表达式的求值开销太大,就将其替换为开销较小的等价代数表达式。用加法替代乘法,降低数组元素上的循环强度。很多编译器进行了这一优化。这种方法可以推广为一大类增量算法。

消除公共子表达式。如果两次对同一个表达式求值时,其所有变量都没有任何改动,那么我们可以用下面的方法避免第二次求值:存储第一次的计算结果并用其取代第二次求值。

成对计算。如果经常需要对两个类似的表达式一起求值,那么就应该建立一个新的过程,将它们成对求值。如果insert函数的参数已经在集合中,C++代码就使用不完成任何操作的insert替代这两个函数。

利用计算机字的并行性。用底层计算机体系结构的全部数据路径宽度来对高开销的表达式求值。

看完这6大代码调优法则,是不是恍然大明白的?有时候,你不是不够努力,而是用错了方法,学好《编程珠玑》中的方法论,更有效率地攀登程序员进阶之路!

编程珠玑 第2版

作者:[美]乔恩·本特利(Jon,Bentley)

京东

本书是计算机科学方面的经典名著。书的内容围绕程序设计人员面对的一系列实际问题展开。作者以其独有的洞察力和创造力,引导读者理解这些问题并学会解决方法,而这些正是程序员实际编程生涯中至关重要的。

本书的特色是通过一些精心设计的有趣而又颇具指导意义的程序,对实用程序设计技巧及基本设计原则进行了透彻而睿智的描述,为复杂的编程问题提供了清晰而完备的解决思路。本书对各个层次的程序员都具有很高的阅读价值。

  • 暂无推荐