加入VIP
  • 专属下载特权
  • 现金文档折扣购买
  • VIP免费专区
  • 千万文档免费下载

上传资料

关闭

关闭

关闭

封号提示

内容

首页 代码之美中文版

代码之美中文版.pdf

代码之美中文版

绝影
2011-06-27 0人阅读 举报 0 0 暂无简介

简介:本文档为《代码之美中文版pdf》,可适用于IT/计算机领域

免费在线版本(非印刷免费在线版)登录ChinaPub网站购买此书完整版了解本书更多信息请登录本书的官方网站InfoQ中文站出品本书由InfoQ中文站免费发放如果您从其他渠道获取本书请注册InfoQ中文站以支持作者和出版商并免费下载更多InfoQ企业软件开发系列图书。本书主页为http:infoqcomcnminibooksbeautifulcode©CMediaInc版权所有CMedia是InfoQcom这一企业软件开发社区的出版商本书属于InfoQ企业软件开发丛书如果您打算订购InfoQ的图书请联系bookscmediacom未经出版者预先的书面许可不得以任何方式复制或者抄袭本书的任何部分本书任何部分不得用于再印刷存储于可重复使用的系统或者以任何方式进行电子、机械、复印和录制等形式传播。本书提到的公司产品或者使用到的商标为产品公司所有。如果读者要了解具体的商标和注册信息应该联系相应的公司。本书在征得华章出版公司许可下制作以电子文档形式发布。欢迎共同参与InfoQ中文站的内容建设工作包括原创投稿和翻译等请联系editorscninfoqcom。序GregWilson我在年夏天获得了第一份程序员工作。在我工作了两个星期后一位系统管理员借给了我两本书:Kernighan和Plauger编写的《TheElementsofProgrammingStyle》(McGrawHill出版社)和Wirth编写的《AlgorithmsDataStructures=Programs》(PrenticeHall出版社)。这两本书让我大开眼界我第一次发现程序并不仅仅只是一组计算机执行的指令。它们可以像做工优良的橱柜一样精致像悬索吊桥一样漂亮或者像GeorgeOrwell的散文一样优美。自从那个夏天以来我经常听到人们感叹我们的教育并没有教会学生看到这一点。建筑师们需要观摩建筑物作曲家们需要研习他人的作品而程序员他们只有在需要修改bug时才会去阅读其他人的代码即使在这个时候他们也会尽可能减少阅读量。我们曾告诉学生使用有意义的变量名曾向他们介绍过一些基本的设计模式但很奇怪为什么他们编写的大多数代码都是很难看的呢!本书将试图改变这种状况。年月我邀请了一些著名的(以及不太著名的)软件设计师来分析和讨论他们所知道的漂亮代码。正如在本书中将要介绍的他们在许多不同的地方发现了代码的漂亮性。有些漂亮性存在于手工精心打造软件的细微之处而有些漂亮性是蕴涵在大局之中那些使程序能够持续发展的架构或者用来构造程序的技术。无论他们是在什么地方发现的这些漂亮性我都非常感谢我们的投稿人抽出时间为我们奉献了这样的一次学习旅程。我希望你能够享受阅读此书的乐趣就像Andy和我非常享受编辑这本书的过程此外我还希望这本书能激发你创建出一些漂亮的作品。i前言《BeautifulCode》是由GregWilson在年构思的本书的初衷是希望从优秀的软件开发人员和计算机科学家中提炼出一些有价值的思想。他与助理编辑AndyOram一起走访了世界各地不同技术背景的专家。本《代码之美》精选版是从原书中精选出其中的章。本书章节内容的组织第章正则表达式匹配器作者BrianKernighan介绍了对一种语言和一个问题的深入分析以及由此产生的简洁而优雅的解决方案。第章我编写过的最漂亮代码作者JonBentley介绍了如何在无需执行函数的情况下测试函数的性能。第章美丽的测试作者AlbertoSavoia介绍了一种全新的测试方法不仅能够消除bug还可以使你成为一个更优秀的程序员。第章NASA火星漫步者任务中的高可靠企业系统作者RonaldMak介绍了如何使用工业标准最佳实践和Java技术来满足NASA探险任务的高可靠性需求。第章美丽的并发作者SimonPeytonJones通过软件事务内存(SoftwareTransactionalMemory)来消除大多数并发程序中的困难在本章中使用Haskell语言来说明。第章以REST方式集成业务伙伴作者AndrewPatzer通过根据需求来设计一个BBWebService从而表现出设计者对程序开发人员的尊重。ii目录序i前言ii第章正则表达式匹配器编程实践实现讨论其他的方法构建小结第章我编写过的最漂亮代码我编写过的最漂亮代码事倍功半观点本章的中心思想是什么?结论致谢第章美丽测试讨厌的二分查找JUnit简介将二分查找进行到底结论第章NASA火星漫步者任务中的高可靠企业系统任务与CIP任务需求系统架构案例分析:流服务可靠性iii稳定性结束语第章美丽的并发一个简单的例子软件事务内存圣诞老人问题对Haskell的一些思考结论致谢第章以REST方式集成业务伙伴项目背景把服务开放给外部客户使用工厂模式转发服务用电子商务协议来交换数据结束语后记iv第章正则表达式匹配器BrianKernighan正则表达式是描述文本模式的表示法它可以有效地构造一种用于模式匹配的专用语言。虽然正则表达式可以有多种不同的形式但它们都有着共同的特点:模式中的大多数字符都是匹配字符串中的字符本身但有些元字符(metacharacter)却有着特定的含义例如*表示某种重复而表示方括号中字符集合的任何一个字符。实际上在文本编辑器之类的程序中所执行的查找操作都是查找文字因此正则表达式通常是像“print”之类的字符串而这类字符串将与文档中所有的“printf”或者“sprintf”或者“printerpaper”相匹配。在Unix和Windows中可以使用所谓的通配符来指定文件名其中字符*可以用来匹配任意数量的字符因此匹配模式*c就将匹配所有以c结尾的文件。此外还有许许多多不同形式的正则表达式甚至在有些情况下这些正则表达式会被认为都是相同的。JeffreyFriedl编著的《MasteringRegularExpressions》一书对这一方面问题进行了广泛的研究。StephenKleene在世纪年代的中期发明了正则表达式用来作为有限自动机的表示法事实上正则表达式与其所表示的有限自动机是等价的。世纪年代年代中期正则表达式最初出现在KenThompson版本的QED文本编辑器的程序设置中。年Thompson申请了一项基于正则表达式的快速文本匹配机制的专利。这项专利在年获得了批准它是最早的软件专利之一USPatent,,,TextMatchingAlgorithm,March,后来正则表达式技术从QED移植到了Unix的编辑器ed中然后又被移植到经典的Unix工具grep中而grpe正是由于Thompson对ed进行了彻底地修改而形成的。这些广为应用的程序使得正则表达式为早期的Unix社群所熟知。Thompson最初编写的匹配器是非常快的因为它结合了两种独立的思想。一种思想是在匹配过程中动态地生成机器指令这样就可以以机器指令执行的速度而不是解释执行的速度来运行。另一种思想是在每个阶段中都尽可能地执行匹配操作这样无需回朔(backtrack)就可以查找可能的匹配。在Thompson后来编写的文本编辑器程序中例如ed匹配代码使用了一种更为简单的算法这种算法将会在必要的时候进行回朔。从理论上来看这种方法的运行速度要更慢但在实际情况中这种模式很少需要进行回朔因此ed和grep中的算法和代码足以应付大多数的情况。在后来的正则表达式匹配器中例如egrep和fgrep等都增加了更为丰富的正则表达式类型并且重点是要使得匹配器无论在什么模式下都能够快速执行。功能更为强大的正则表达式正在被越来越多地使用它们不仅被包含在用C语言开发的库中而且还被作为脚本语言如Awk和Perl的语法的一部分。编程实践在年RobPike和我还在编写《ThePracticeofProgramming》(AddisonWesley)一书。书中的最后一章是“记法”在这一章中收录了许多示例代码这些示例都很好地说明了良好的记法将会带来更好的程序以及更好的设计。其中包括使用简单的数据规范(例如printf)以及从表中生成代码。由于我们有着深厚的Unix技术背景以及在使用基于正则表达式记法的工具上有着近年的经验我们很自然地希望在本书中包含一个对正则表达式的讨论当然包含一个实现也是必须的。由于我们强调了工具软件的使用因此似乎最好应该把重点放在grep中的正则表达式类型上而不是比方说在shell的通配符正则表达式上这样我们还可以在随后再讨论grep本身的设计。然而问题是现有的正则表达式软件包都太庞大了。grep中的代码长度超过行(大约页书的长度)并且在代码的周围还有复杂的上下文环境。开源的正则表达式软件包则更为庞大代码的长度几乎布满整本书因为这些代码需要考虑通用性灵活性以及运行速度因此所有这些正则表达式都不适合用来教学。我向Rob建议我们需要一个最小的正则表达式软件包它可以很好地诠释正则表达式的基本思想并且能够识别出一组有用的并且重要类的模式。理想的情况是所需代码长度只有一页就够了。Rob听了我的提议后就离开了他的办公室。我现在还记得一两个小时后他回来了并且给了我一段大约行的C代码在《ThePracticeofProgramming》一书的第章中包含了这段代码。在这段代码实现了一个正则表达式匹配器用来处理以下的模型。字符含义c匹配任意的字母c(句点)匹配任意的单个字符^匹配输入字符串的开头$匹配输入字符串的结尾*匹配前一个字符的零个或者多个出现这是一个非常有用的匹配器根据我在日常工作中使用正则表达式的经验它可以轻松解决%的问题。在许多情况下解决正确的问题就等于朝着创建漂亮的程序迈进了一大步。Rob值得好好地表扬因为他从大量可选功能集中选出了一组非常小但却重要的并且是明确的以及可扩展的功能。Rob的实现本身就是漂亮代码的一个极佳示例:紧凑优雅高效并且实用。这是我所见过的最好的递归示例之一在这段代码中还展示了C指针的强大功能。虽然当时我们最关心的是通过使程序更易于使用(同时也更易于编写)来体现良好记法的重要性但正则表达式代码同样也是阐述算法数据结构测试性能增强以及其他重要主题的最好方式。实现在《ThePracticeofProgramming》一书中正则表达式匹配器是一个模拟grep程序中的一部分但正则表达式的代码完全可以从编写环境中独立出来。这里我们并不关心主程序像许多Unix工具一样这个程序将读取其标准输入或者一组文件然后输出包含与正则表达式匹配的文本行。以下是匹配算法的代码:*match:searchforregexpanywhereintext*intmatch(char*regexp,char*text){if(regexp=='^')returnmatchhere(regexp,text)do{*mustlookevenifstringisempty*if(matchhere(regexp,text))return}while(*text!='')return}*matchhere:searchforregexpatbeginningoftext*intmatchhere(char*regexp,char*text){if(regexp=='')returnif(regexp=='*')returnmatchstar(regexp,regexp,text)if(regexp=='$'regexp=='')return*text==''if(*text!=''(regexp==''||regexp==*text))returnmatchhere(regexp,text)return}*matchstar:searchforc*regexpatbeginningoftext*intmatchstar(intc,char*regexp,char*text){do{*a*matcheszeroormoreinstances*if(matchhere(regexp,text))return}while(*text!=''(*text==c||c==''))return}讨论函数match(regexptext)用来判断文本中是否出现正则表达式如果找到了一个匹配的正则表达式则返回否则返回。如果有多个匹配的正则表达式那么函数将找到文本中最左边的并且最短的那个。match函数中的基本操作简单明了。如果正则表达式中的第一个字符是(^固定位置的匹配)那么匹配就一定要出现在字符串的开头。也就是说如果正则表达式是^xyz那么仅当xyz出现在文本的开头而不是中间的某个位置时才会匹配成功。在代码中通过把正则表达式的剩余部分与文本的起始位置而不是其他地方进行匹配来判断。如果第一个字符不是^那么正则表达式就可以在字符串中的任意位置上进行匹配。在代码中通过把模式依次与文本中的每个字符位置进行匹配来判断。如果存在多个匹配那么代码只会识别第一个(最左边的)匹配。也就是说如果则在表达式是xyz那么将会匹配第一次出现的xyz而且不考虑这个匹配出现在什么位置上。注意对输入字符串的推进操作是在一个dowhile循环中进行的这种结构在C程序中使用相对较少。在代码中使用dowhile而不是while通常会带来疑问:为什么不在循环的起始处判断循环条件而是在循环末尾当执行完了某个操作之后才进行判断呢?不过这里的判断是正确的:由于*运算符允许零长度的匹配因此我们首先需要判断是否存在一个空的匹配。大部分的匹配工作是在matchhere(regexptext)函数中完成的这个函数将判断正则表达式与文本的开头部分是否匹配。函数matchhere把正则表达式的第一个字符与文本的第一个字符进行匹配。如果匹配失败那么在这个文本位置上就不存在匹配因此matchhere将返回。然而如果匹配成功了函数将推进到正则表达式的下一个字符和文本的下一个字符继续进行匹配。这是通过递归地调用matchhere函数来实现的。由于存在着一些特殊的情况以及需要设置终止递归的条件。因此实际的处理过程要更为复杂些最简单的情况就是当正则表达式推进到末尾时(regexp=='')所有前面的判断都成功了那么这个正则表达式就与文本匹配。如果正则表达式是一个字符后面跟着一个*那么将会调用matchstar来判断闭包(closure)是否匹配。函数matchstar(c,regexp,text)将尝试匹配重复的文本字符c从零重复开始并且不断累加直到匹配text的剩余字符如果匹配失败那么函数就认为不存在匹配。这个算法将识别出一个“最短的匹配”这对简单的模式匹配来说是很好的例如grep这种情况下的主要问题是尽可能快地找到一个匹配。而对于文本编辑器来说“最长的匹配”则是更为直观且肯定是更好的因为通常需要对匹配的文本进行替换。在目前许多的正则表达式库中同时提供了这两种方法在《ThePracticeofProgramming》一书中给出了基于本例中matchstar函数的一种简单变形我们在后面将给出这种形式。如果在正则表达式的末尾包含了一个$那么仅当text此时位于末尾时才会匹配成功:if(regexp=='$'regexp=='')return*text==''如果没有包含$并且如果当前不是处于text字符串的末尾(也就是说*text!='')并且如果text字符串的第一个字符匹配正则表达式的第一个字符那么到现在为止都是没有问题的我们将接着判断正则表达式的下一个字符是否匹配text的下一个字符这是通过递归调用matchhere函数来实现的。这个递归调用不仅是本算法的核心也是这段代码如此紧凑和整洁的原因。如果所有这些匹配尝试都失败了那么正则表达式和text在这个位置上就不存在匹配因此函数matchhere将返回。在这段代码中大量地使用了C指针。在递归的每个阶段如果存在某个字符匹配那么在随后的递归调用中将执行指针算法(例如regexpandtext)这样在随后的函数调用中参数就是正则表达式的下一个字符和text的下一个字符。递归的深度不会超过匹配模式的长度而通常情况下匹配模式的长度都是很短的因此不会出现耗尽内存空间的危险。其他的方法这是一段非常优雅并且写得很好的代码但并不是完美的。我们还可以做哪些其他的工作?我可能对matchhere中的操作进行重新安排在处理*之前首先处理$。虽然这种安排不会对函数的执行带来影响但却使得函数看上去要自然一些而在编程中一个良好的规则就是:在处理复杂的情况之前首先处理容易的情况。不过通常这些判断的顺序是非常重要的。例如在matchstar的这个判断中:}while(*text!=''(*text==c||c==''))无论在什么情况下我们都必须推进text字符串中的一个或多个字符因此在text中的递增运算一定要执行。该代码对终止条件进行了谨慎的处理。通常匹配过程的成功与否是通过判断正则表达式和text中的字符是不是同时处理完来决定的。如果是同时处理完了那么就表示匹配成功如果其中一方在另一方之前被处理完了那么就表示匹配失败。在下面这行代码中很明显地说明了这个判断。if(regexp=='$'regexp=='')return*text==''但在其他的情况下还有一些微妙的终止条件。如果在matchstar函数中需要识别最左边的以及最长的匹配那么函数将首先识别输入字符c的最大重复序列。然后函数将调用matchhere来尝试把匹配延伸到正则表达式的剩余部分和text的剩余部分。每次匹配失败都会将cs的出现次数减然后再次开始尝试包括处理零出现的情况:*matchstar:leftmostlongestsearchforc*regexp*intmatchstar(intc,char*regexp,char*text){char*tfor(t=text*t!=''(*t==c||c=='')t)do{**matcheszeroormore*if(matchhere(regexp,t))return}while(t>text)return}我们来看一下正则表达式(*)它将匹配括号内任意长度的text。假设给定了text:for(t=text*t!=''(*t==c||c=='')t)从开头位置起的最长匹配将会识别整个括号内的表达式而最短的匹配将会停止在第一次出现右括号的地方。(当然从第二个左括号开始的最长匹配将会延伸到text的末尾)构建《ThePracticeofProgramming》一书主要讲授良好的程序设计。在编写该书时Rob和我还在贝尔实验室工作因此我们知道在课堂上使用这本书有什么样的效果。令人高兴的是我们发现这本书中的某些内容在课堂上确实有着不错的效果。从年教授程序设计中的重点要素时我们就使用了这段代码。首先这段代码以一种全新的形式展示了递归的强大功能及其带来的整洁代码。它既不是另一种版本的快速排序(或者阶乘!)算法也不是某种树的遍历算法。这段代码同时还是性能试验的一个很好示例。其性能与系统中的grep并没有太大的差异这表明递归技术的开销并不是非常大的因此没有必要对这段代码进行调整。此外这段代码还充分说明了优良算法的重要性。如果在模式中包含了几个*序列那么在简单的实现中将需要进行大量的回溯操作并且在某些情况下将会运行得极慢。在标准的Unixgrep中有着同样的回朔操作。例如下面这个命令:grep'a*a*a*aa'在普通的机器上处理一个MB的文本文件要花费秒的时间。如果某个实现是基于把非确定有限自动机转换为确定有限自动机例如egrep那么在处理恶劣的情况时将会获得比较好的性能它可以在不到十分之一秒的时间内处理同样的模式和同样的输入并且运行时间通常是独立于模式的。对于正则表达式类型的扩展将形成各种任务的基础。例如:.增加其他的元字符例如用于表示前面字符的一个或多个出现或者用于表示零个或一个字符的匹配。还可以增加一些方式来引用元字符例如$表示在模式中的$字符。.将正则表达式处理过程分成编译阶段和执行阶段。编译阶段把正则表达式转换为内部形式使匹配代码更为简单或者使随后的匹配过程运行得更为迅速。对于最初设计中的简单的正则表达式来说这种拆分并不是必须的但在像grep这样的程序中这种拆分是有意义的因为这种类型的正则表达式要更为丰富并且同样的正则表达式将会用于匹配大量的输入行。.增加像abc和这样的类型这在传统的grep中分别匹配a或b或c和一个数字。可以通过几种方式来实现最自然的方式似乎就是把最初代码中的char*变量用一个结构来代替:typedefstructRE{inttype*CHAR,STAR,etc*intch*thecharacteritself*char*ccl*forinstead*intnccl*trueifclassisnegated^*}RE并且修改相应的代码来处理一个结构数组而不是处理一个字符数组。在这种情况下并不一定要把编译阶段从执行阶段中拆分出来但这里的拆分过程是非常简单的。如果学生们把匹配代码预编译成这个结构那么总会比那些试图动态地解释一些复杂模式数据结构的学生要做得更好。为字符类型编写清晰并且无歧义的规范是件有难度的工作而要用代码完美地实现处理更是难上加难这需要大量的冗长并且晦涩的编码。随着时间的推移我简化了这个任务而现在大多数人会要求像Perl那样的速记例如d表示数字D表示非数字而不再像最初那样在方括号内指定字符的范围。.使用不透明的类型来隐藏RE结构以及所有的实现细节。这是在C语言中展示面向对象编程技术的好方法不过除此之外无法支持更多的东西。在实际情况中将会创建一个正则表达式类其中类中成员函数的名字像REnew()和REmatch()这样而不是使用面向对象语言的语法。.把正则表达式修改为像各种shell中的通配符那样:匹配模式的两端都被隐含地固定了*匹配任意数量的字符而则匹配任意的单个字符。你可以修改这个算法或者把输入映射到现有的算法中。.将这段代码转换成Java。最初的代码很好地使用了C指针并且把这个算法在不同的语言中实现出来是一个很好的实践过程。在Java版本的代码中将使用StringcharA(使用索引而不是指针)或者Stringsubstring(更接近于指针)。这两种方法都没有C代码整洁并且都不紧凑。虽然在这个练习中性能并不是主要的问题但有趣的是可以发现了Java版本比C版本在运行速度上要慢到倍。.编写一个包装类把这种类型的正则表达式转换成Java的Patter类和Matcher类这些类将以一种与众不同的方式来拆分编译阶段和匹配阶段。这是适配器(Adapter)模式或者外观(Façade)模式的很好示例这两种模式用来在现有的类或者函数集合外部设置不同的接口。我曾经大量地使用了这段代码来研究测试技术。正则表达式非常的丰富而测试也不是无足轻重的但正则表达式又是很短小的程序员可以很快地写出一组测试代码来执行。对于前面所列出的各种扩展我要求学生用一种紧凑的语言写出大量的测试代码(这是“记法”的另一种示例)并且在他们自己的代码中使用这些测试代码自然我在其他学生的代码中也使用了他们的测试代码。小结当RobPike最初写出这段代码时我被它的紧凑性和优雅性感到惊讶这段代码比我以前所想像的要更为短小并且功能也更为强大。通过事后分析我们可以看到为什么这段代码如此短小的众多原因。首先我们很好地选择了功能集合这些功能是最为有用的并且最能从实现中体现出核心思想而没有多余的东西。例如虽然固定模式^和$的实现只需要写~行代码但在统一处理普通情况之前它展示了如何优雅地处理特殊情况。闭包操作*必须出现因为它是正则表达式中的基本记号并且是提供处理不确定长度的惟一方式。增加和并不会有助于理解因此这些符号被留作为练习。其次我们成功地使用了递归。递归这种基本的编程技巧通常会比明确的循环带来更短、更整洁的以及更优雅的代码这也正是这里的示例。从正则表达式的开头和tex的开头剥离匹配字符然后对剩余的字符进行递归的思想模仿了传统的阶乘或者字符串长度示例的递归结构但这里是用在了一种更为有趣和更有用的环境中。第三这段代码的确使用了基础语言来达到良好的效果。指针也可能被误用但这里它们被用来创建紧凑的表达式并且在这个表达式中自然地表达了提取单个字符和推进到下一个字符的过程。数组索引或者子字符串可以达到同样的效果但在这段代码中指针能够更好的实现所需的功能尤其是当指针与C语言中的自动递增运算和到布尔值的隐式转换结合在一起使用时。我不清楚是否有其他的方法能够在如此少的代码中实现如此多功能并且同时还要提供丰富的内涵和深层次的思想。第章我编写过的最漂亮的代码JonBentley我曾经听一位大师级的程序员这样称赞到“我通过删除代码来实现功能的提升。”而法国著名作家兼飞行家AntoinedeSaintExupéry的说法则更具代表性“只有在不仅没有任何功能可以添加而且也没有任何功能可以删除的情况下设计师才能够认为自己的工作已臻完美。”某些时候在软件中根本就不存在最漂亮的代码最漂亮的函数或者最漂亮的程序。当然我们很难对不存在的事物进行讨论。本章将对经典Quicksort(快速排序)算法的运行时间进行全面的分析并试图通过这个分析来说明上述观点。在第一节中我将首先根据我自己的观点来回顾一下Quicksort并为后面的内容打下基础。第二节的内容将是本章的重点部分。我们将首先在程序中增加一个计数器然后通过不断地修改从而使程序的代码变得越来越短但程序的功能却会变得越来越强最终的结果是只需要几行代码就可以使算法的运行时间达到平均水平。在第三节将对前面的技术进行小结并对二分搜索树的运行开销进行简单的分析。最后的两节将给出学完本章得到的一些启示这将有助于你在今后写出更为优雅的程序。我编写过的最漂亮代码当GregWilson最初告诉我本书的编写计划时我曾自问编写过的最漂亮的代码是什么。这个有趣的问题在我脑海里盘旋了大半天然后我发现答案其实很简单:Quicksort算法。但遗憾的是根据不同的表达方式这个问题有着三种不同的答案。当我撰写关于分治(divideandconquer)算法的论文时我发现CARHoare的Quicksort算法(“Quicksort”ComputerJournal)无疑是各种Quicksort算法的鼻祖。这是一种解决基本问题的漂亮算法可以用优雅的代码实现。我很喜欢这个算法但我总是无法弄明白算法中最内层的循环。我曾经花两天的时间来调试一个使用了这个循环的复杂程序并且几年以来当我需要完成类似的任务时我会很小心地复制这段代码。虽然这段代码能够解决我所遇到的问题但我却并没有真正地理解它。我后来从NicoLomuto那里学到了一种优雅的划分(partitioning)模式并且最终编写出了我能够理解甚至能够证明的Quicksort算法。WilliamStrunkJr针对英语所提出的“良好的写作风格即为简练”这条经验同样适用于代码的编写因此我遵循了他的建议“省略不必要的字词”(来自《TheElementsofStyle》一书)。我最终将大约行左右的代码缩减为十几行的代码。因此如果要回答“你曾编写过的最漂亮代码是什么?”这个问题那么我的答案就是:在我编写的《ProgrammingPearls,SecondEdition》(AddisonWesley)一书中给出的Quichsort算法。在示例中给出了用C语言编写的Quicksort函数。我们在接下来的章节中将进一步地研究和改善这个函数。【示例】Quicksort函数voidquicksort(intl,intu){inti,mif(l>=u)returnswap(l,randint(l,u))m=lfor(i=li<=ui)if(xi<xl)swap(m,i)swap(l,m)quicksort(l,m)quicksort(m,u)}如果函数的调用形式是quicksort(,n)那么这段代码将对一个全局数组xn进行排序。函数的两个参数分别是将要进行排序的子数组的下标:l是较低的下标而u是较高的下标。函数调用swap(i,j)将会交换xi与xj这两个元素。第一次交换操作将会按照均匀分布的方式在l和u之

用户评价(0)

关闭

新课改视野下建构高中语文教学实验成果报告(32KB)

抱歉,积分不足下载失败,请稍后再试!

提示

试读已结束,如需要继续阅读或者下载,敬请购买!

文档小程序码

使用微信“扫一扫”扫码寻找文档

1

打开微信

2

扫描小程序码

3

发布寻找信息

4

等待寻找结果

我知道了
评分:

/24

代码之美中文版

仅供在线阅读

VIP

在线
客服

免费
邮箱

爱问共享资料服务号

扫描关注领取更多福利