国家集训队2009论文集论程序底层优化的一些

《国家集训队2009论文集论程序底层优化的一些》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、2009年全国信息学奥林匹克冬令营论文成都七中骆可强论程序底层优化的一些方法与技巧成都七中骆可强摘要：本文以优化程序运行的时间效率为目地，从编译器、汇编代码、CPU特性等较为底层的概念着眼，对程序优化进行了全方位的探讨，总结了在优化中实用的思想、原则、方法和技巧，并对它们在竞赛中的应用价值做出了一些尝试。关键字：优化CPU汇编语言编译器目录序言第１页引例第３页CPU指令的运行效率第１２页数值运算的优化第１３页除法第１３页乘法第１８页高精度运算第２０页CPU优化特性第２０页高速缓存第２１页分支预测第２５页乱序执行第２７页

2、位运算技巧第２９页高维数组使用的注意事项第３１页应用举例第３４页总结第３５页参考文献第３６页特别感谢第３７页序言信息学奥林匹克竞赛（OlympiadinInformatics）是研究怎样编写计算机程序来解决特定问题的竞赛。考察的关键点，在于怎样利用有限的系统资源（CPU时间片与系统内存）来求解规模庞大的数学模型。在“正确”这一前提下，“效率”自然是考虑问题的第一要素。效率，分为时间效率与空间效率，如何对时间效率进行优化是本文将要研究的主题。算法是决定时间效率的关键优化程序的时间效率，简单地讲，就是用尽一切手段，在保证正确的前提下让程

3、序的运行时间更短。那么，有些什么手段呢？最重要的自然是：使用尽可能高效的算法。算法（Algorithm），是一系列解决问题的机械步骤，它采用明确定义的语义，描述了求解特定数学模型的一般方法。算法的好坏，直接决定了程序的运行效率。采用低效的算法或高效的算法，其差别就好像选择走路或是坐飞机，完全不在一个数量级。时间复杂度的概念及其局限性第1页2009年全国信息学奥林匹克冬令营论文成都七中骆可强为了衡量一个算法时间效率上的优劣，计算机科学中引入了时间复杂度的概念。回忆我们习惯使用的大O表示法，我们说一个算法运行时间的界是O(f(n))，所表示的意义

4、是，假设这个算法的实际运行时间关于输入规模n的函数是T(n)，那么存在正常数n0、c，使得对于n≣n0，有0≢T(n)≢c×f(n)。有了这样一个上界，我们就能知道T(n)的增长速度，从而能够大致判断对于给定的n，我们的算法能不能在一个合理的时间内出解。然而另一方面不可否认的是，这样一个工具是极其粗略的。我们注意到刚才的定义式中存在一个常数c，它在渐进意义上是无关紧要的，但回到现实世界中，它却不可忽视。同样是O(n)阶的算法，有些可以快到只消耗2×n个CPU时钟周期，而另一些甚至需要1000×n个时钟周期还要多。就好像同样是乘坐飞机，也有快慢

5、的极大差别。使用相同时间复杂度的算法，因为这个常数c的不同，实际运行所需要的时间，也可能有天壤之别。算法并不是时间效率的全部那么，这个常数受哪些因素的影响呢？无疑，它同样受制于算法：不同的算法，可能有着相同的复杂度，但是实际效果截然不同。相同的算法，可能有着不同的实现方式，一些逻辑上的简化也能大大降低运行所需花费的时间。那么，算法就是程序运行效率的全部了么？答案是否定的，有些东西是隐藏在逻辑层面之下的，它们同样显著地影响着程序的运行效率，而我们却很难看到。举例来说，你能想象当我们在C语言中书写a/=7这一语句时，实际上处理器并没有做缓慢的除法

6、，而使用了乘法和位移取而代之么？因为这样，我喜欢把大O定义式中的常数c一分为二的来看待：c＝c1×c2，c1代表逻辑层面（算法）的消耗，而c2表示每一句程序语句在底层运行的消耗，那么程序的实际运行时间，约为c2×[c1×f(n)]，方括号中的部分c1×f(n)就完全由算法来决定，而c2则取决于程序的底层实现。前者固然重要，后者也同样不可忽视。本文将要研究的，就是怎样在程序运行的底层对细节做出优化，以提升程序的运行效率。为什么要学习底层优化在OI竞赛中，算法是考察的重点。底层实现看起来并不重要，确实提升空间也相对较小，但当我们设计的算法有一些先

7、天缺陷时，或许对底层做细致的优化能对我们有很大的帮助，在后文中会展示一些实际的例子。在竞赛之外，学习底层的东西，能让我们更深入地认识眼前的机器，即使在使用高级语言书写程序时，脑海中也会自然投射出底层发生的事情，从而能够写出质量更高的代码。在这篇论文前期准备、实验研究、总结规律到最终成文的过程中，我学到了太多的东西，这些东西在我们平时为OI竞赛编程的过程中是很难看到的，而我也相信，这些东西在为大家所广泛认识之后，同样能够服务于竞赛，实际地提升成绩。说了这么多，或许是该展现一个实例的时候了。下面我们从一个极其简化的编程任务入手，来看看什么是底层优

8、化，有些什么样的工具，能做到什么程度。第2页2009年全国信息学奥林匹克冬令营论文成都七中骆可强平台简介条件所限，本文中的所有研究、编码、测量工作均在一台Think