多年以前,我在开发一个C++的应用程序。我的同伴Jim Newkirk(当时的)过来告诉说,我们的一个公用函数运行得非常的缓慢。这个函数是用来转换二进制的树结构数据为普通文本,并存储到文件中的。(这是在XML出现之前,但概念类似于XML)
我审视了这个函数一会儿,发现了一个线性查找算法,于是毫无疑问的将这个线性查找算法替换为二分查找法(译注:binary search),然后就把这个函数交回给了Jim。Jim几小时后就回来了,问我是否有做过任何的改进,因为这个函数还是迟缓如初。
看来是我没找到关键,于是就一遍又一遍的研究了这个函数,然后发现并改进了一些其它很明显的算法问题,可是性能依然没有丝毫改进。函数依然缓慢,看到我对这个函数的无计可施,Jim也越来越沮丧。
最后,Jim终于找到了一个能够去分析这个函数性能的办法,就发现这个问题出自一个底层的叫strstream的C++库(译注1)。这个库函数随着文本数据的不断增加,它不停的一次又一次的申请内存块。这个函数单纯根据即将读入的文本数据大小来预先申请内存块,速度也迅速的随之以数量级的趋势降低。
很久以前,曾有一次我要写一个计算任意多边形面积的算法。我想出了一个不断的把这个任意多边形细分为三角形的主意。每次细分一个三角形,多边形就会减少一个顶点,而它的面积就可以由此累加起来。由于不得不处理很多不规则的形状,好久我才把这个功能写好。一、两天后,我就完成了这个厉害的算法,它能计算任意的多边形的面积。
几天后,我的一个同事过来找我,说:“我新画了多边形的一条边,可它花了45分钟才计算出面积。所以,我要是重新绘制这条线断或是调整它,面积都显示不出。”45分钟啊,很长的时间了,所以我就问她这个多边形有多少个顶点,她告诉我有超过1,000个的。
看了看算法,我认识到这个算法的复杂度是O(N^3)的(译注2),所以对于小多边形来说很快,但对于大型的来说速度就慢得无法忍受了。我一遍又一遍的思考着这个问题,但却找不到一个更好的算法。(现今我们只要用google搜索就好了,可那是现在而这是那时...)于是我们就把这个自动显示面积的功能去掉,然后告诉客户这太耗时了。
两周之后,纯属偶然机会,我正翻阅一本关于prolog编程语言的书(一个可爱又另类的编程语言,我建议你也学习学习它),然后就发现了一个计算多边形面积的算法。它优雅,简单,而且是线性阶(译注2)的,我是从来都没写出过这么漂亮的算法。我用了几分钟时间就实现了它,哇!即使拖动多边形一个顶点绕着屏幕乱转,面积竟然也可以及时更新。
昨天晚上,我坐在一辆豪华轿车里,从O'Hare驶向我在芝加哥北部郊区的家。I-294公路正在施工,而我们凑好赶上交通阻塞。于是我拿出我的Macbook Pro,然后开始即兴的编写Ruby程序。为了好玩,我开始编写埃拉托色尼质数过滤算法(译注:Sieve of Eratosthenes)。我想让程序一跑起来就能看到Ruby有多快,所以就在程序中增加了benchmark模块来度量速度。它相当快!能在两秒钟内算出所有在百万以内的素数!对于一个解释型语言来说还不错。
我想知道这个算法的复杂度O(x)是什么样的。坐在车里不好算出来,于是我决定通过一些设定点采样的方法来测出它。我从100,000开始到5,000,000,每间隔100,000运行一次这个算法采样,然后把这些采样点绘在了一个图上。竟然是线性阶!
这个算法怎能是线性阶呢?它有一个嵌套的循环!难道不应该是复杂度类似于O(N^2),或者至少也应该是O(N log N)啊?这里就是代码,你自己来看看:
require 'benchmark'
def sievePerformance(n)
r = Benchmark.realtime() do
sieve = Array.new(n,true)
sieve[0..1] = [false,false]
2.upto(n) do |i|
if sieve[i]
(2*i).step(n,i) do |j|
sieve[j] = false
end
end
end
end
r
end
我的儿子Micah就坐在我旁边,他看了看然后说:“这个循环最多只应做到n平方根。”我惭愧的意识到这一定是导致线性阶的原因。这个循环本应该在它刚到n平方根的时候就结束了的,可却陷入了无用的线性迭代之中一直到n。
这个简单的改变应该不仅仅能在采样图表上展现出原本的曲线形状,算法的性能也应能提高不少。如下:
require 'benchmark'
def sievePerformance(n)
r = Benchmark.realtime() do
sieve = Array.new(n,true)
sieve[0..1] = [false,false]
2.upto(Integer(Math.sqrt(n)) do |i|
if sieve[i]
(2*i).step(n,i) do |j|
sieve[j] = false
end
end
end
end
r
我把这两幅采样图表拼接在了一起,如下:
真令人失望。首先,在图上的sqrt(n)没有展现出曲线来;其次,sqrt(n)的性能仅仅是原先的两倍!一个函数的外循环上限在指数级别上变为的一半(即原来的平方根),可是速度的提升却怎能只有2倍?
随着我对这个算法理解的加深,我认识到外层循环的迭代次数的增加,内层循环所耗用时间会因为两个因素而减少。首先,步长增大了;其次,在筛选过程中出现了更多的'false'值,因此判断语句会更少频率的被执行。这两个导致时间耗用降低的因素一定是导致算法保持线性阶的某种平衡因素。
我不是计算机科学家,而且对鉴别这个算法到底是线性与否的数学问题我也不是非常感兴趣。谁能猜出当外部循环的范围缩小到原来上限值的平方根而性能却只有2倍增长的原因?谁能猜到算法本身竟然是线性阶的?!
六年前,当大家刚开始沉迷于XP的时候,Kent Beck(译注3)要在一组学生(大概30个左右)前示意一个算法,我就为他写了这个埃拉托色尼质数过滤算法的Java例程。我惊讶的看到他从函数中把n的平方根删掉,并替换成了n。他说“我不知道这是不是真的能让算法加快,不管如何,把上限设为n使得可读性更好。”于是,他删掉了这个特别的注释,那是我在平方根周围注释来解释为何不把上限设为n的聪明之处。
那时我眼珠子乱转而且还在一旁偷偷傻笑。我确信,如果n很大的时候,上限是n平方根会让算法的效率在数量级上大于n的,我还深信n每扩大一百倍,它所耗费的时间只会随之增加大概十倍。六年后(昨晚),我终于知道了程序的结果,而且知道了增幅是2倍线性阶的,而对此Kent一直都是对的。
译注:
1,strstream,标准C/C++的字符串流类,派生自iostream。因性能问题,C++标准委员会做了修补,用stringstream替换之,因此也不建议再使用strstream。
2,复杂度(本文指时间复杂度),以算法中基本运算的重复执行次数作为算法时间复杂度的时间量度,并以符号O(x)来表示。通常,时间复杂度由小到大分为几个等级,a)常量阶 O(c),b)对数阶 O(log2n),c)线性阶 O(n),d)多项式阶 O(nm)等。
3,Kent Beck,是软件开发方法学的泰斗、XP的创始人,长期致力于软件工程的理论研究和实践,并具有讲授XP的丰富经验。作为软件业内最富创造,哇和最有口碑的领导人之一,KentBeck极力推崇模式、极限编程和测试驱动开发。他现在加盟于ThreeRivers研究所,是多部畅销书如《Smalltalk Best PracticePatterns》、《解析极限编程——拥抱变化》和《规划极限编程》(和Martin Fowler合著)的作者,并且是超级畅销书《重构——改善既有代码的设计》(中国电力出版社出版中英文版)的特约撰稿人。
(原文链接网址:http://www.butunclebob.com/ArticleS.UncleBob.PerformanceTuning; Robert C. Martin的英文blog网址:http://www.butunclebob.com/ArticleS.UncleBob)
作者简介:Robert C. Martin是Object Mentor公司总裁,面向对象设计、模式、UML、敏捷方法学和极限编程领域内的资深顾问。他不仅是Jolt获奖图书《敏捷软件开发:原则、模式与实践》(中文版)(《敏捷软件开发》(英文影印版))的作者,还是畅销书Designing Object-Oriented C++ Applications Using the Booch Method的作者。Martin是Pattern Languages of Program Design 3和More C++ Gems的主编,并与James Newkirk合著了XP in Practice。他是国际程序员大会上著名的发言人,并在C++ Report杂志担任过4年的编辑。
分享到:
相关推荐
介绍 3个超乎想象的创意营销 给您震撼的体验
远超乎您想象的易用的强大照片编辑器 for Android
医疗科技案例 阿里的医疗帝国,超乎你想象 .rar
模块化电动汽车,自由定制的程度超乎你想象.pdf
一个帮助你在微信抢红包时战无不胜的Android应用。自动检测并且拆开红包,速度超乎你的想象。
人工智能的定义可以分为两部分,即“人工”和“智能”。“人工”比较好理解,争议性也不大。有时我们会要考虑什么是人力所能及制造的,或者人自身的智能程度有没有高到可以创造人工智能的地步,等等。...
宝德“四子星” PR2760T服务器是一款特殊优化设计、性能卓越、安全可靠的高密度机架式服务器产品。完美支持Intel最新5500/5600系列QPI处理器、采用Intel 5520芯片组、高速DDR3内存及SATA硬盘热插拔技术,提供超越...
react native 腾讯云通讯插件云通信(Instant Messaging)承载亿级 QQ 用户即时通信技术,数十年技术积累,腾讯云为您提供超乎寻常即时通信聊天服务。一、安装android暂无ios 添加以下依赖库CoreTelephony....
在你学习js的过程中,这里可以找到你所有想要的笔记,这是我在学习js的时候,纯手打的笔记,真的是超详细,有需要的朋友可以下载
起因是装Android studio的时候需要gradle,编译器自己下载的话,不挂外网是绝不可能下载...倒是能下载了,但是速度非常慢,还常常断网需要重新下载,这时,你可以复制下载网址链接到迅雷里面,速度将会超乎你的想象哦~
Uni 并预留20只多功能脚位,设计弹性超乎想象。考虑物联网产品对低功耗的设计,Uni采用极省电架构设计,在省电模式下工作电流低于1微安,亦即使用3.7V锂电池供电时,待机时间长达30万小时。 ICE 板: Nu-Link Mini ...
5G发展演进 5G发展的驱动力 5G 协议标准的最新进展 5G产业链及生态圈 5G全球商用计划 ...5G的发展速度将超乎想象 5G芯片 19Q2 18Q4 19Q1 18Q3 19Q4 19Q3 18Q2 XMM-8160 NSA/SA Exynos 5100 NSA Exynos 51X0
腾讯业务产品线众多,拥有海量的活跃用户,每天线上产生的数据超乎想象,必然会成为数据大户,为了保证公司各业务产品能够使用更丰富优质的数据服务,腾讯的大数据平台做了那些工作?具备哪些能力?大数据,这个词...
SpringCloud + Docker 的便利和强大真的超乎想象,我已经入坑了…好了,不说废话,记录一个简单的 Demo 供其他同学排坑。 前言 惯例不能丢,先上源代码:docker-demo 这个项目的代码是我执行在Docker上部署...
我们分析了超级僵尸网络的可能性,超级僵尸可以超乎想象的大规模攻击。为了竞争生存,超级僵尸将会使用多种策略手段来对付防御手段。因此,超级僵尸必须被研究机构研究,只有这样,防御这个威胁的防御手段才会有效...
quickLayout.css - 超乎想象的快速布局页面! 通过使用这个 CSS,构建网页将像火箭一样快! 介绍 实际上,CSS 库的名称是quick-layout.css或quick_layout.css 。 这个CSS基于和项目。 风俗 点击。 您可以选择您...
“制作和分享视频更轻松,超乎您的想象!” “太喜欢了!Magisto棒极了,能够制作一些有趣的视频!” “我的家人和朋友们喜欢看我制作和分享的视频” “比Vine能够创建更长、更漂亮的视频... ” “使用现有的视频和...
一个工程,从原始状态迅速膨胀到天猫现在的体量的,依赖关系之复杂,超乎想象。 耦合三类: 界面耦合,就是用户操作流程里,不同界面间的跳转,这些界面的跳转是硬编码 依赖耦合,顾名思义,两个模块之间的...
绝对想你所想,超乎想象!够详细,够给力! 目录 1. Jvm内存空间结构是什么样的? 1 程序计数器 1 Java栈 1 本地方法栈 2 堆 2 方法区 3 2. Jvm堆内存的划分结构和优化 3 2.1. 原理 6 2.1.1. 年轻代 6 2.1.2. 年老代...