1、版本版）（非印刷登錄China-Pub此書完整版了解本書信息本書的InfoQ 中文站本書由 InfoQ 中文站和InfoQ 中文站以支持作者，如果您從其他獲取本書，請商，并InfoQ 企業(yè)軟件開發(fā)系列。本書主頁為© 2008 C4Media Inc.所有C4Media 是 InfoQ.com 這一企業(yè)軟件開發(fā)社區(qū)的商本書屬于 InfoQ 企業(yè)軟件開發(fā)如果您打算訂購 InfoQ 的，請books者預(yù)先的，不得以任何方式或者本書的，本書不得用于再印刷，于可重復(fù)使用的系統(tǒng)，或者以任何方式進(jìn)行電子、 機(jī)械、復(fù)印和錄制等形式。本書提到的公司或者使用到的商標(biāo)為。如果讀者要了解具體的商標(biāo)和信息，應(yīng)

2、該相應(yīng)的公司。本書在征得華章公司下制作，以電子文檔形式發(fā)布。歡迎共同參與 InfoQ 中文站的內(nèi)容建設(shè)工作，包括 editors。投稿和翻譯等，請 序Greg Wilson我在1982年夏天獲得了第一份程序員工作。在我工作了兩個后，一位系統(tǒng)管理員借給了我兩本書：Kernighan和Plauger編寫的The Elements of Programming Style(McGraw-Hill)和Wirth編寫的Algorithms + Data Structures = Programs (Prentice Hall社)。這兩本書讓我大開眼界我第一次發(fā)現(xiàn)程序并不僅僅只是一組計算機(jī)執(zhí)行的指令。它們

3、可以像做工優(yōu)良的櫥柜一樣精致，像懸索吊橋一樣漂亮，或者像George Orwell的散文一樣優(yōu)美。自從那個夏天以來，我經(jīng)常聽到人們感嘆我們的教育并沒有學(xué)生看到這一點。師們需要觀摩物，作曲家們需要研習(xí)他人的，而程序員他們只有在需要修改bug時才會去閱讀其他人的代碼；即使在這個時候，他們也會盡可能減少閱讀量。我們曾告訴學(xué)生使用有意義的變量名，曾向他們介紹過一些基本的設(shè)計模式，但很奇怪，為什么他們編寫的大多數(shù)代碼都是很難看的呢！本書將試圖改變這種狀況。2006年5月，我邀請了一些著名的（以及不太著名的）軟件設(shè)計師來分析和討論他們所知道的漂亮代碼。正如在本書中將要介紹的，他們在許多不同的地方發(fā)現(xiàn)了代碼

4、的漂亮性。有些漂亮性存在于手工精心打造軟件的細(xì)微之處，而有些漂亮性是蘊涵在大局之中那些使程序能夠持續(xù)發(fā)展的架構(gòu)，或者用來構(gòu)造程序的技術(shù)。無論他們是在什么地方發(fā)現(xiàn)的這些漂亮性，我都非常感謝我們的投稿人抽出時間為我們奉獻(xiàn)了這樣的一次學(xué)習(xí)旅程。我希望你能夠享受閱讀此書的樂趣，就像Andy和我非常享受編輯這本書的過程，此外，我還希望這本書能激發(fā)你創(chuàng)建出一些漂亮的。i前言Beautiful Code是由Greg Wilson在 2006 年構(gòu)思的，本書的初衷是希望從優(yōu)秀的軟件和計算機(jī)科學(xué)家中提煉出一些有價值的思想。他與助理編輯Andy Oram一起走訪了世界開發(fā)各地不同技術(shù)背景的。本代碼之美精選版是從原

5、書中精選出其中的 6 章。本書章節(jié)內(nèi)容的組織第 1 章，正則表達(dá)式匹配器，作者 Brian Kernighan，介紹了對一種語言和一個問題的深入分析以及由此產(chǎn)生的簡潔而優(yōu)雅的解決方案。第 2 章，我編寫過的最漂亮代碼，作者 Jon Bentley，介紹了如何在無需執(zhí)行函數(shù)的情況下測試函數(shù)的性能。第 3 章，美麗的測試，作者 Alberto Savoia，介紹了一種全新的測試方法，不僅能夠消除 bug， 還可以使你成為一個更優(yōu)秀的程序員。第 4 章，NASA 火星漫步者任務(wù)中的高可靠企業(yè)系統(tǒng)，作者 Ronald Mak，介紹了如何使用工業(yè)標(biāo)準(zhǔn)，最佳實踐和 Java 技術(shù)來滿足 NASA 探險任務(wù)

6、的高可靠性需求。第 5 章，美麗的并發(fā)，作者 Simon Peyton Jones，通過軟件事務(wù)內(nèi)存（Software TransactionalMemory）來消除大多數(shù)并發(fā)程序中的，在本章中使用 Haskell 語言來說明。第 6 章，以 REST 方式集成業(yè)務(wù)伙伴，作者 Andrew Patzer，通過根據(jù)需求來設(shè)計一個 B2BWebService 從而表現(xiàn)出設(shè)計者對程序開發(fā)的尊重。ii目錄序i前言ii第 1 章 正則表達(dá)式匹配器編程實踐2實現(xiàn)3討論4其他的方法5構(gòu)建6小結(jié)8第 2 章 我編寫過的最漂亮代碼我編

7、寫過的最漂亮代碼10事倍功半11觀點16本章的中心思想是什么？18結(jié)論18致謝20第 3 章 美麗測試3.4討厭的二分查找22JUnit 簡介27將二分查找進(jìn)行到底29結(jié)論47第 4 章 NASA 火星漫步者任務(wù)中的高可靠企業(yè)系統(tǒng)44.44.5任務(wù)與 CIP49任務(wù)需求50系統(tǒng)架構(gòu)51案例分析：流服務(wù)54可靠性57iii4.6 穩(wěn)定性664.7 結(jié)束語67第 5 章 美麗的并發(fā)6一個簡單的例子68軟件事務(wù)內(nèi)存71圣誕老人問題80對 Haskell 的一些思考90結(jié)論91致謝92第 6 章 以 REST 方式集成業(yè)務(wù)

8、伙伴96.46.5項目背景93把服務(wù)開放給外部客戶93使用工廠模式轉(zhuǎn)發(fā)服務(wù)97用電子商務(wù)協(xié)議來交換數(shù)據(jù)98結(jié)束語104后記106iv第 1 章 正則表達(dá)式匹配器Brian Kernighan正則表達(dá)式是描述文本模式的表示法，它可以有效地構(gòu)造一種用于模式匹配的語言。雖然正則表達(dá)式可以有多種不同的形式，但它們都有著共同的特點：模式中的大多數(shù)字符都是匹配字符串中的字符本身，但有些元字符（metacharacter）卻有著特定的含義，例如*表示某種重復(fù)，而.表示方括號中字符集合的任何一個字符。實際上，在文本編輯器之類的程序中，所執(zhí)行的查找操作都是查找文字，因此正則表達(dá)式通常是像“p

9、rint”之類的字符串，而這類字符串將與文檔中所有的“printf”或者“sprintf”或者“printer paper”相匹配。在Unix和Windows中可以使用所謂的通配符來指定文件名，其中字符*可以用來匹配任意數(shù)量的字符，因此匹配模式*.c就將匹配所有以.c結(jié)尾的文件。此外，還有許許多多不同形式的正則表達(dá)式，甚至在有些情況下，這些正則表達(dá)式會被認(rèn)為都是相同的。Jeffrey Friedl編著的Mastering Regular Expressions一書對這一方面問題進(jìn)行了廣泛的研究。Stephen Kleene在20世紀(jì)50年代的中期發(fā)明了正則表達(dá)式，用來作為有限自的表示法，事實上

10、，正則表達(dá)式與其所表示的有限自是等價的。20世紀(jì)60年代年代中期，正則表達(dá)式最初出現(xiàn)在Ken Thompson版本的QED文本編輯器的程序設(shè)置中。1967年Thompson申請了一項基于正則表達(dá)式的快速文本匹配機(jī)制的專利。這項專利在獲得了批準(zhǔn)，它是最早的軟件專利之一U.S. Patent 3,568,156, Text Matching Algorithm, March 2, 1971.后來，正則表達(dá)式技術(shù)從QED移植到了Unix的編輯器ed中，然后又被移植到經(jīng)典的Unix工具grep中，而grpe正是由于Thompson對ed進(jìn)行了徹底地修改而形成的。這些廣為應(yīng)用的程序使得正則表達(dá)式為早期的

11、Unix社群所熟知。Thompson最初編寫的匹配器是非?？斓?，因為它結(jié)合了兩種的思想。一種思想是在匹配過程中動態(tài)地生成指令，這樣就可以以指令執(zhí)行的速度而不是解釋執(zhí)行的速度來運行。另一種思想是在每個階段中都盡可能地執(zhí)行匹配操作，這樣無需回朔（backtrack）就可以查找可能的匹配。在Thompson后來編寫的文本編輯器程序中，例如ed，匹配代碼使用了一種更為簡單的算法，這種算法將會在必要的時候進(jìn)行回朔。從理論上來看，這種方法的運行速度要更慢，但在實際情況中，這種模式很少需要進(jìn)行回朔，因此，ed和grep中的算法和代碼足以應(yīng)付大多數(shù)的情況。在后來的正則表達(dá)式匹配器中，例如egrep和fgrep

12、等，都增加了更為豐富的正則表達(dá)式類1型，并且重點是要使得匹配器無論在什么模式下都能夠快速執(zhí)行。功能更為強(qiáng)大的正則表達(dá)式正在被越來越多地使用，它們不僅被包含在用C語言開發(fā)的庫中，而且還被作為語言如Awk和Perl的語法的一部分。1.1編程實踐在1998年，Rob Pike和我還在編寫The Practice of Programming（Addison-Wesley）一書。書中的最后一章是“記法”，在這一章中收錄了許多示例代碼，這些示例都很好地說明了良好的記法將會帶來更好的程序以及更好的設(shè)計。其中包括使用簡單的數(shù)據(jù)規(guī)范（例如printf）以及從表中生成代碼。由于我們有著深厚的Unix技術(shù)背景以及

13、在使用基于正則表達(dá)式記法的工具上有著近30年的經(jīng)驗，我們很自然地希望在本書中包含一個對正則表達(dá)式的討論，當(dāng)然包含一個實現(xiàn)也是必須的。由于我們強(qiáng)調(diào)了工具軟件的使用，因此似乎最好應(yīng)該把重點放在grep中的正則表達(dá)式類型上而不是，比方說，在shell的通配符正則表達(dá)式上這樣我們還可以在隨后再討論grep本身的設(shè)計。然而，問題是現(xiàn)有的正則表達(dá)式軟件包都太龐大了。grep中的代碼長度超過500行（大約10頁書的長度），并且在代碼的周圍還有復(fù)雜的上下文環(huán)境。開源的正則表達(dá)式軟件包則更為龐大代碼的長度幾乎布滿整本書因為這些代碼需要考慮通用性，靈活性以及運行速度；因此，所有這些正則表達(dá)式都不適合用來教學(xué)。我向

14、Rob建議我們需要一個最小的正則表達(dá)式軟件包，它可以很好地詮釋正則表達(dá)式的基本思想，并且能夠識別出一組有用的并且重要類的模式。理想的情況是，所需代碼長度只有一頁就夠了。Rob聽了提議后就離開了他的辦公室。我現(xiàn)在還記得，一，兩個小時后他回來了，并且給了我一段大約30行的C代碼，在The Practice of Programming一書的第9章中包含了這段代碼。在這段代碼實現(xiàn)了一個正則表達(dá)式匹配器，用來處理以下的模型。字符含義c匹配任意的字母c.（句點）匹配任意的單個字符匹配輸入字符串的開頭$匹配輸入字符串的結(jié)尾*匹配前一個字符的零個或者多個出現(xiàn)這是一個非常有用的匹配器，根據(jù)我在日常工作中使用正

15、則表達(dá)式的經(jīng)驗，它可以輕松解決95的問題。在許多情況下，解決正確的問題就等于朝著創(chuàng)建漂亮的程序邁進(jìn)了一大步。Rob2值得好好地表揚，因為他從大量可選功能集中選出了一組非常小但卻重要的，并且是明確的以及可擴(kuò)展的功能。Rob的實現(xiàn)本身就是漂亮代碼的一個極佳示例：緊湊，優(yōu)雅，高效并且實用。這是我所見過的最好的遞歸示例之一，在這段代碼中還展示了C指針的強(qiáng)大功能。雖然當(dāng)時我們最關(guān)心的是通過使程序更易于使用（同時也更易于編寫）來體現(xiàn)良好記法的重要性，但正則表達(dá)式代碼同樣也是闡述算法，數(shù)據(jù)結(jié)構(gòu)，測試，性能增強(qiáng)以及其他重要主題的最好方式。1.2實現(xiàn)在The Practice of Programming一書中

16、，正則表達(dá)式匹配器是一個模擬grep程序中的一部分，但正則表達(dá)式的代碼完全可以從編寫環(huán)境中出來。這里我們并不關(guān)心主程序；像許多Unix工具一樣，這個程序?qū)⑵錁?biāo)準(zhǔn)輸入或者一組文件，然后輸出包含與正則表達(dá)式匹配的文本行。以下是匹配算法的代碼：/*match: search for regexp anywhere in text */ int match(char *regexp, char *text)if (regexp0 = '')return matchhere(regexp+1, text);do /* must look even if string is empty *

17、/if (matchhere(regexp, text) return 1; while (*text+ != '0'); return 0;/* matchhere: search for regexp at beginning of text int matchhere(char *regexp, char *text)*/if(regexp0 = '0') return 1; (regexp1 = '*')return matchstar(regexp0, regexp+2, text);ifif(regexp0 = '$'

18、 && regexp1 = '0') return *text = '0'(*text!='0' && (regexp0='.' | regexp0=*text) return matchhere(regexp+1, text+1);ifreturn 0;3/* matchstar: search for c*regexp at beginning of text */ int matchstar(int c, char *regexp, char *text)do /* a * matches z

19、ero or more instances */if (matchhere(regexp, text) return 1; while (*text != '0' && (*text+ = c | c = '.'); return 0;1.3討論函數(shù)match(regexp，text)用來文本中是否出現(xiàn)正則表達(dá)式；如果找到了一個匹配的正則表達(dá)式則返回1，否則返回0。如果有多個匹配的正則表達(dá)式，那么函數(shù)將找到文本中最左邊的并且最短的那個。match函數(shù)中的基本操作簡單明了。如果正則表達(dá)式中的第一個字符是（固置的匹配），那么匹配就一定要出現(xiàn)在字符串的

20、開頭。也就是說，如果正則表達(dá)式是xyz，那么僅當(dāng)xyz出現(xiàn)在文本的開頭而不是中間的某個位置時才會匹配。在代碼中通過把正則表達(dá)式的剩余部分與文本的起始位置而不是其他地方進(jìn)行匹配來。如果第一個字符不是，那么正則表達(dá)式就可以在字符串中的任意位置上進(jìn)行匹配。在代碼中通過把模式依次與文本中的每個字符位置進(jìn)行匹配來。如果存在多個匹配，那么代碼只會識別第一個（最左邊的）匹配。也就是說，如果則在表達(dá)式是xyz，那么將會匹配第一次出現(xiàn)的xyz，而且不考慮這個匹配出現(xiàn)在什么位置上。注意，對輸入字符串的推進(jìn)操作是在一個do-while循環(huán)中進(jìn)行的，這種結(jié)構(gòu)在C程序中使用相對較少。在代碼中使用do-while而不是w

21、hile通常會帶來疑問：為什么不在循環(huán)的起始處循環(huán)條件，而是在循環(huán)末尾當(dāng)執(zhí)行完了某個操作之后才進(jìn)行呢？不過，這里的是正確的：由于*運算符零長度的匹配，因此我們首先需要是否存在一個空的匹配。大部分的匹配工作是在matchhere(regexp，text)函數(shù)中完成的，這個函數(shù)將正則表達(dá)式與文本的開頭部分是否匹配。函數(shù)matchhere把正則表達(dá)式的第一個字符與文本的第一個字符進(jìn)行匹配。如果匹配失敗，那么在這個文本位置上就不存在匹配，因此matchhere將返回0。然而，如果匹配了，函數(shù)將推進(jìn)到正則表達(dá)式的下一個字符和文本的下一個字符繼續(xù)進(jìn)行匹配。這是通過遞歸地調(diào)用matchhere函數(shù)來實現(xiàn)的。

22、由于存在著一些特殊的情況，以及需要設(shè)置終止遞歸的條件。因此實際的處理過程要更為4復(fù)雜些最簡單的情況就是，當(dāng)正則表達(dá)式推進(jìn)到末尾時(regexp0 = '0')，所有前面的都了，那么這個正則表達(dá)式就與文本匹配。如果正則表達(dá)式是一個字符后面跟著一個*，那么將會調(diào)用matchstar來閉包（closure）是否匹配。函數(shù)matchstar(c, regexp, text)將嘗試匹配重復(fù)的文本字符c，從零重復(fù)開始并且不斷累加，直到匹配text的剩余字符，如果匹配失敗，那么函數(shù)就認(rèn)為不存在匹配。這個算法將識別出一個“最短的匹配”，這對簡單的模式匹配來說是很好的，例如grep，這種情況下的

23、主要問題是盡可能快地找到一個匹配。而對于文本編輯器來說，“最長的匹配”則是更為直觀，且肯定是更好的，因為通常需要對匹配的文本進(jìn)行替換。在目前許多的正則表達(dá)式庫中同時提供了這兩種方法，在The Practice of Programming一書中給出了基于本例中matchstar函數(shù)的一種簡單變形，我們在后面將給出這種形式。如果在正則表達(dá)式的末尾包含了一個$，那么僅當(dāng)text此時位于末尾時才會匹配：if (regexp0 = '$' && regexp1 = '0')return *text = '0'如果沒有包含$，并且如果當(dāng)前不

24、是處于text字符串的末尾（也就是說，*text!='0'）并且如果text字符串的第一個字符匹配正則表達(dá)式的第一個字符，那么到現(xiàn)在為止都是沒有問題的；接著正則表達(dá)式的下一個字符是否匹配text的下一個字符，這是通過遞歸調(diào)用matchhere函數(shù)來實現(xiàn)的。這個遞歸調(diào)用不僅是本算法的，也是這段代碼如此緊湊和整潔的。如果所有這些匹配嘗試都失敗了，那么正則表達(dá)式和text在這個位置上就不存在匹配，因此函數(shù)matchhere將返回0。在這段代碼中大量地使用了C指針。在遞歸的每個階段，如果存在某個字符匹配，那么在隨后的遞歸調(diào)用中將執(zhí)行指針?biāo)惴ǎɡ?，regexp+1 and text+1

25、），這樣在隨后的函數(shù)調(diào)用中，參數(shù)就是正則表達(dá)式的下一個字符和text的下一個字符。遞歸的深度超過匹配模式的長度，而通常情況下匹配模式的長度都是很短的，因此出現(xiàn)耗盡內(nèi)存空間的。1.4其他的方法這是一段非常優(yōu)雅并且寫得很好的代碼，但并不是完美的。我們還可以做哪些其他的工作？我可能對matchhere中的操作進(jìn)行重新安排，在處理*之前首先處理$。雖然這種安排對函數(shù)的執(zhí)行帶來影響，但卻使得函數(shù)看上去要自然一些，而在編程中一個良好的規(guī)則就是：在處理復(fù)雜的情況之前首先處理容易的情況。不過，通常這些的順序是非常重要的。例如，在matchstar的這個中： while (*text != '0'

26、; && (*text+ = c | c = '.');5無論在什么情況下，我們都必須推進(jìn)text字符串中的一個或多個字符，因此在text+中的遞增運算一定要執(zhí)行。該代碼對終止條件進(jìn)行了謹(jǐn)慎的處理。通常，匹配過程的與否，是通過正則表達(dá)式和text中的字符是不是同時處理完來決定的。如果是同時處理完了，那么就表示匹配，如果其中一方在另一方之前被處理完了，那么就表示匹配失敗。在下面這行代碼中很明顯地說明了這個。if (regexp0 = '$' && regexp1 = '0')return *text = '0

27、'但在其他的情況下，還有一些微妙的終止條件。如果在matchstar函數(shù)中需要識別最左邊的以及最長的匹配，那么函數(shù)將首先識別輸入字符c的最大重復(fù)序列。然后函數(shù)將調(diào)用matchhere來嘗試把匹配延伸到正則表達(dá)式的剩余部分和text的剩余部分。每次匹配失敗都會將cs的出現(xiàn)次數(shù)減1，然后再次開始嘗試，包括處理零出現(xiàn)的情況：/* matchstar: leftmost longest search for c*regexp */ int matchstar(int c, char *regexp, char *text)char *t;for (t = text; *t != '0&

28、#39;do /* * matches zero or if (matchhere(regexp,return 1; while (t- > text); return 0;&& (*t = c | c= '.'); t+)more */ t)我們來看一下正則表達(dá)式(.*)，它將匹配括號內(nèi)任意長度的text。假設(shè)給定了text：for (t = text; *t != '0' && (*t = c | c = '.'); t+)從開頭位置起的最長匹配將會識別整個括號內(nèi)的表達(dá)式，而最短的匹配將會停止在第一次出現(xiàn)

29、右括號的地方。（當(dāng)然，從第二個左括號開始的最長匹配將會延伸到text的末尾）1.5構(gòu)建The Practice of Programming一書主要講授良好的程序設(shè)計。在編寫該書時，Rob和我還在貝爾工作，因此我們知道在課堂上使用這本書有什么樣的效果。令人高興的是，6我們發(fā)現(xiàn)這本書中的某些內(nèi)容在課堂上確實有著不錯的效果。從2000年教授程序設(shè)計中的重點要素時，我們就使用了這段代碼。首先，這段代碼以一種全新的形式展示了遞歸的強(qiáng)大功能及其帶來的整潔代碼。它既不是另一種版本的快速排序（或者階乘！）算法，也不是某種樹的遍歷算法。這段代碼同時還是性能試驗的一個很好示例。其性能與系統(tǒng)中的grep并沒有太大

30、的差異，這表明遞歸技術(shù)的開銷并不是非常大的，因此沒有必要對這段代碼進(jìn)行調(diào)整。此外，這段代碼還充分說明了優(yōu)良算法的重要性。如果在模式中包含了幾個.*序列，那么在簡單的實現(xiàn)中將需要進(jìn)行大量的回溯操作，并且在某些情況下將會運行得極慢。在標(biāo)準(zhǔn)的Unix grep中有著同樣的回朔操作。例如，下面這個命令：grep 'a.*a.*a.*a.a'在普通的上處理一個4 MB的文本文件要花費20秒的時間。如果某個實現(xiàn)是基于把非確定有限自轉(zhuǎn)換為確定有限自，例如egrep，那么在處理惡劣的情況時將會獲得比較好的性能；它可以在不到十分之一秒的時間內(nèi)處理同樣的模式和同樣的輸入，并且運行時間通常是于模式的

31、。對于正則表達(dá)式類型的擴(kuò)展將形成各種任務(wù)的基礎(chǔ)。例如：1增加其他的元字符，例如+用于表示前面字符的一個或多個出現(xiàn)，或者?用于表示零個或一個字符的匹配。還可以增加一些方式來元字符，例如$表示在模式中的$字符。2將正則表達(dá)式處理過程分成編譯階段和執(zhí)行階段。編譯階段把正則表達(dá)式轉(zhuǎn)換為內(nèi)部形式，使匹配代碼更為簡單或者使隨后的匹配過程運行得更為迅速。對于最初設(shè)計中的簡單的正則表達(dá)式來說，這種拆分并不是必須的，但在像grep這樣的程序中，這種拆分是有意義的，因為這種類型的正則表達(dá)式要更為豐富，并且同樣的正則表達(dá)式將會用于匹配大量的輸入行。3增加像abc和0-9這樣的類型，這在傳統(tǒng)的grep中分別匹配a或b

32、或c和一個數(shù)字?？梢酝ㄟ^幾種方式來實現(xiàn)，最自然的方式似乎就是把最初代碼中的char*變量用一個結(jié)構(gòu)來代替：typedef struct REinttype;/*CHAR, STAR, etc. */intch;/*the character itself */char*ccl;/*for . instead */intnccl;/*true if class is negated . */ RE;并且修改相應(yīng)的代碼來處理一個結(jié)構(gòu)數(shù)組而不是處理一個字符數(shù)組。在這種情況下，并不一定要把編譯階段從執(zhí)行階段中拆分出來，但這里的拆分過程是非常簡單的。如果學(xué)生們把匹7配代碼預(yù)編譯成這個結(jié)構(gòu)，那么總會比那些

33、試圖動態(tài)地解釋一些復(fù)雜模式數(shù)據(jù)結(jié)構(gòu)的學(xué)生要做得更好。為字符類型編寫清晰并且無歧義的規(guī)范是件有難度的工作，而要用代碼完美地實現(xiàn)處理更是難上加難，這需要大量的冗長并且晦澀的編碼。隨著時間的推移，我簡化了這個任務(wù)，而現(xiàn)在大多數(shù)人會要求像Perl那樣的速記，例如d表示數(shù)字，D表示非數(shù)字，而不再像最初那樣在方括號內(nèi)指定字符的范圍。4使用不透明的類型來隱藏RE結(jié)構(gòu)以及所有的實現(xiàn)細(xì)節(jié)。這是在C語言中展示面向?qū)ο缶幊碳夹g(shù)的好方法，不過除此之外無法支持的東西。在實際情況中，將會創(chuàng)建一個正則表達(dá)式類，其中類中成員函數(shù)的名字像RE_new( )和RE_match()這樣，而不是使用面向?qū)ο笳Z言的語法。5把正則表達(dá)式

34、修改為像各種shell中的通配符那樣：匹配模式的兩端都被隱含地固定了，*匹配任意數(shù)量的字符，而?則匹配任意的單個字符。你可以修改這個算法或者把輸入到現(xiàn)有的算法中。6將這段代碼轉(zhuǎn)換成Java。最初的代碼很好地使用了C指針，并且把這個算法在不同的語言中實現(xiàn)出來是一個很好的實踐過程。在Java版本的代碼中將使用String.charA（使用索引而不是指針）或者String.substring（更接近于指針）。這兩種方法都沒有C代碼整潔，并且都不緊湊。雖然在這個練習(xí)中性能并不是主要的問題，但有趣的是可以發(fā)現(xiàn)了Java版本比C版本在運行速度上要慢6到7倍。7編寫一個包裝類把這種類型的正則表達(dá)式轉(zhuǎn)換成Ja

35、va的Patter類和Matcher類，這些類將以一種與眾不同的方式來拆分編譯階段和匹配階段。這是適配器（Adapter）模式或者外觀（Façade）模式的很好示例，這兩種模式用來在現(xiàn)有的類或者函數(shù)集合外部設(shè)置不同的接口。我曾經(jīng)大量地使用了這段代碼來研究測試技術(shù)。正則表達(dá)式非常的豐富，而測試也不是無足輕重的，但正則表達(dá)式又是很短小的，程序員可以很快地寫出一組測試代碼來執(zhí)行。對于前面所列出的各種擴(kuò)展，我要求學(xué)生用一種緊湊的語言寫出大量的測試代碼（這是“記法”的另一種示例），并且在他們的代碼中使用這些測試代碼；自然我在其他學(xué)生的代碼中也使用了他們的測試代碼。1.6小結(jié)當(dāng)Rob Pike最

36、初寫出這段代碼時，我被它的緊湊性和優(yōu)雅到驚訝這段代碼比我以前所想像的要更為短小并且功能也更為強(qiáng)大。通過事后分析，我們可以看到為什么這段代碼如此短小的眾多。首先，我們很好地選擇了功能集合，這些功能是最為有用的并且最能從實現(xiàn)中體現(xiàn)出8思想，而沒有多余的東西。例如，雖然固定模式和$的實現(xiàn)只需要寫34行代碼，但在統(tǒng)一處理普通情況之前，它展示了如何優(yōu)雅地處理特殊情況。閉包操作*必須出現(xiàn)，因為它是正則表達(dá)式中的基本記號，并且是提供處理不確定長度的惟一方式。增加+和?并有助于理解，因此這些符號被留作為練習(xí)。其次，我們地使用了遞歸。遞歸這種基本的編程技巧通常會比明確的循環(huán)帶來更短、更整潔的以及更優(yōu)雅的代碼，這

37、也正是這里的示例。從正則表達(dá)式的開頭和tex的開頭剝離匹配字符，然后對剩余的字符進(jìn)行遞歸的思想，模仿了傳統(tǒng)的階乘或者字符串長度示例的遞歸結(jié)構(gòu)，但這里是用在了一種更為有趣和更有用的環(huán)境中。第三，這段代碼的確使用了基礎(chǔ)語言來達(dá)到良好的效果。指針也可能被誤用，但這里它們被用來創(chuàng)建緊湊的表達(dá)式，并且在這個表達(dá)式中自然地表達(dá)了提取單個字符和推進(jìn)到下一個字符的過程。數(shù)組索引或者子字符串可以達(dá)到同樣的效果，但在這段代碼中，指針能夠更好的實現(xiàn)所需的功能，尤其是當(dāng)指針與C語言中的自動遞增運算和到布爾值的隱式轉(zhuǎn)換結(jié)合在一起使用時。我不清楚是否有其他的方法能夠在如此少的代碼中實現(xiàn)如此多功能，并且同時還要提供豐富的內(nèi)

38、涵和次的思想。9第 2 章 我編寫過的最漂亮的代碼Jon Bentley我曾經(jīng)聽一位大師級的程序員這樣稱贊到，“我通過刪除代碼來實現(xiàn)功能的提升。”而法國著名作家兼飛行家 Antoine de Saint-Exupéry 的說法則更具代表性，“只有在不僅沒有任何功能可以添加，而且也沒有任何功能可以刪除的情況下，設(shè)計師才能夠認(rèn)為的工作已臻完美?！?某些時候，在軟件中根本就不存在最漂亮的代碼，最漂亮的函數(shù)，或者最漂亮的程序。當(dāng)然，我們很難對不存在的事物進(jìn)行討論。本章將對經(jīng)典 Quicksort（快速排序）算法的運行時間進(jìn)行全面的分析，并試圖通過這個分析來說明上述觀點。在第一節(jié)中，我將首先根

39、據(jù)的觀點來回顧一下 Quicksort，并為后面的內(nèi)容打下基礎(chǔ)。第二節(jié)的內(nèi)容將是本章的重點部分。首先在程序中增加一個計數(shù)器，然后通過不斷地修改，從而使程序的代碼變得越來越短，但程序的功能卻會變得越來越強(qiáng)，最終的結(jié)果是只需要幾行代碼就可以使算法的運行時間達(dá)到平均水平。在第三節(jié)將對前面的技術(shù)進(jìn)行小結(jié)，并對二分搜索樹的運行開銷進(jìn)行簡單的分析。最后的兩節(jié)將給出學(xué)完本章得到的一些啟示，這將有助于你在今后寫出更為優(yōu)雅的程序。2.1我編寫過的最漂亮代碼當(dāng)Greg Wilson 最初告訴我本書的編寫計劃時，我曾自問編寫過的最漂亮的代碼是什么。這個有趣的問題在我腦海里盤旋了大半天，然后我發(fā)現(xiàn)其實很簡單：Quic

40、ksort 算法。但遺憾的是，根據(jù)不同的表達(dá)方式，這個問題有著三種不同的。當(dāng)我撰寫關(guān)于分治（divide-and-conquer）算法的時，我發(fā)現(xiàn) C.A.R. Hoare 的Quicksort 算法（“Quicksort”，Computer Journal 5）無疑是各種 Quicksort 算法的鼻祖。這是一種解決基本問題的漂亮算法，可以用優(yōu)雅的代碼實現(xiàn)。我很喜歡這個算法，但我總是無法弄明白算法中最內(nèi)層的循環(huán)。我曾經(jīng)花兩天的時間來調(diào)試一個使用了這個循環(huán)的復(fù)雜程序，并且?guī)啄暌詠?，?dāng)我需要完成類似的任務(wù)時，我會很地段代碼能夠解決我所遇到的問題，但我卻并沒有真正地理解它。這段代碼。雖然這我后來從

41、 Nico Lomuto 那里學(xué)到了一種優(yōu)雅的劃分（partitioning）模式，并且最終編寫出了我能夠理解，甚至能夠證明的 Quicksort 算法。William Strunk Jr.英語所提出的“良好的寫作風(fēng)格即為簡練”這條經(jīng)驗同樣適用于代碼的編寫，因此我遵循了他的建議， “省略不必要的字詞”（來自The Elements of Style一書）。我最終將大約 40 行左右的代碼縮減為十幾行的代碼。因此，如果要回答“你曾編寫過的最漂亮代碼是什么？”這個問題，那么就是：在我編寫的Programming Pearls, Second Edition (Addison-Wesley)一書中給

42、出的 Quichsort 算法。在示例 2-1 中給出了用 C 語言編寫的Quicksort 函數(shù)。我們在接下來的章節(jié)中將進(jìn)一步地研究和這個函數(shù)。【示例】 2-1 Quicksort 函數(shù)void quicksort(int l, int u)int i, m;if (l >= u) return;10swap(l, randint(l, u); m = l;for (i = l+1; i <= u; i+) if (xi < xl)swap(+m, i);swap(l, m); quicksort(l, m-1); quicksort(m+1, u);如果函數(shù)的調(diào)用形式是

43、quicksort(0, n-1)，那么這段代碼將對一個全局?jǐn)?shù)組 xn進(jìn)行排序。函數(shù)的兩個參數(shù)分別是將要進(jìn)行排序的子數(shù)組的下標(biāo)：l 是較低的下標(biāo)，而 u 是較高的下標(biāo)。函數(shù)調(diào)用 swap(i,j)將會交換 xi與 xj這兩個元素。第一次交換操作將會按照均勻分布的方式在 l 和u 之間隨機(jī)地選擇一個劃分元素。在Programming Pearls一書中包含了對 Quicksort 算法的詳細(xì)推導(dǎo)以及正確性證明。在本章的剩余內(nèi)容中，我將假設(shè)讀者熟悉在Programming Pearls中所給出的 Quicksort 算法以及在大多數(shù)初級算法教科書中所給出的 Quicksort 算法。如果你把問題改

44、為“在你編寫那些廣為應(yīng)用的代碼中，哪一段代碼是最漂亮的？”還是 Quicksort 算法。在我和 M. D. McIlroy 一起編寫的一篇文章（"Engineering a sort function," Software-Practice and Experience, Vol. 23, No. 11）中指出了在原來 Unix qsort 函數(shù)中的一個嚴(yán)重的性能問題。隨后，我們開始用 C 語言編寫一個新排序函數(shù)庫，并且考慮了許多不同的算法，包括合并排序（Merge Sort）和堆排序（Heap Sort）等算法。在比較了 Quicksort 的幾種實現(xiàn)方案后，我們著手創(chuàng)

45、建的 Quicksort 算法。在這篇文章中描述了我們?nèi)绾卧O(shè)計出一個比這個算法的其他實現(xiàn)要更為清晰，速度更快以及更為健壯的新函數(shù)部分是由于這個函數(shù)的代碼更為短小。Gordon Bell 的名言被證明是正確的：“在計算機(jī)系統(tǒng)中，那些最廉價，速度最快以及最為可靠的組件是不存在的。”現(xiàn)在，這個函數(shù)已經(jīng)被使用了 10 多年的時間，并且沒有出現(xiàn)任何故障?？紤]到通過縮減代碼量所得到的好處，我最后以第三種方式來問在本章之初提出的問題?！澳銢]有編寫過的最漂亮代碼是什么？”。我如何使用非常少的代碼來實現(xiàn)大量的功能？紹。還是和 Quicksort 有關(guān)，特別是對這個算法的性能分析。我將在下一節(jié)給出詳細(xì)介2.2事倍

46、功半Quicksort 是一種優(yōu)雅的算法，這一點有助于對這個算法進(jìn)行細(xì)致的分析。大約在 1980 年左右，我與 Tony Hoare 曾經(jīng)討論過 Quicksort 算法的歷史。他告訴我，當(dāng)他最初開發(fā)出Quicksort 時，他認(rèn)為這種算法太簡單了，不值得，而且直到能夠分析出這種算法的預(yù)期運行時間之后，他才寫出了經(jīng)典的“Quicksoft”。我們很容易看出，在最壞的情況下，Quicksort可能需要n2的時間來對數(shù)組元素進(jìn)行排序。而在最優(yōu)的情況下，它將選擇中值作為劃分元素，因此只需nlgn次的比較就可以完成對數(shù)組的排序。那么，對于n個不同值的隨機(jī)數(shù)組來說，這個算法平均將進(jìn)行多少次比較？Hoar

47、e 對于這個問題的分析非常漂亮，但不幸的是，其中所使用的數(shù)學(xué)知識超出了大多數(shù)程序員的理解范圍。當(dāng)我科生講授 Quicksort 算法時，許多學(xué)生即使在費了很大的努力之后，還是無法理解其中的證明過程，這令我非常沮喪。下面，從 Hoare 的程序開11始討論，并且最后將給出一個與他的證明很接近的分析。我們的任務(wù)是對示例 2-1 中的 Quicksort 代碼進(jìn)行修改，以分析在對元素值均不相同的數(shù)組進(jìn)行排序時平均需要進(jìn)行多少次比較。我們還將努力通過最短的代碼、最短運行時間以及最小空間來得到最深的理解。為了確定平均比較的次數(shù)，我們首先對程序進(jìn)行修改以統(tǒng)計次數(shù)。因此，在內(nèi)部循環(huán)進(jìn)行比較之前，增加變量 c

48、omps 的值（參見示例 2-2）。【示例 2-2】 修改 Quicksort 的內(nèi)部循環(huán)以統(tǒng)計比較次數(shù)。for (i = l+1; i <= u; i+) comps+;if (xi < xl) swap(+m, i);如果用一個值 n 來運行程序，會看到在程序的運行過程中總共進(jìn)行了多少次比較。如果重復(fù)用 n 來運行程序，并且用統(tǒng)計的方法來分析結(jié)果，n 個元素進(jìn)行排序時平均使用了 1.4 nlgn 次的比較。得到 Quicksort 在對在理解程序的行為上，這是一種不錯的方法。通過十三行的代碼和一些實驗可以反應(yīng)出許多問題。這里，我們作家 Blaise Pascal 和 T. S.

49、 Eliot 的話，“如果我有的時間，那么我給你寫的信就會更短?！爆F(xiàn)在，我們有充足的時間，因此就讓我們來對代碼進(jìn)行修改，并且努力編寫出更短（同時更好）的程序。我們要做的事情就是提高這個算法的速度，并且盡量增加統(tǒng)計的精確度以及對程序的理解。由于內(nèi)部循環(huán)總是會執(zhí)行 u-l 次比較，因此我們可以通過在循環(huán)外部增加一個簡單的操作來統(tǒng)計比較次數(shù)，這就可以使程序運行得更快一些。在示例 2-3 的Quicksort 算法中給出了這個修改?！臼纠?2-3】 Quicksort 的內(nèi)部循環(huán)，將遞增操作移到循環(huán)的外部comps += u-l;for (i = l+1; i <= u; i+) if (xi

50、< xl)swap(+m, i);這個程序會對一個數(shù)組進(jìn)行排序，同時統(tǒng)計比較的次數(shù)。不過，如果我們的目標(biāo)只是統(tǒng)計比較的次數(shù)，那么就不需要對數(shù)組進(jìn)行實際地排序。在示例 2-4 中去掉了對元素進(jìn)行排序的“實際操作”，而只是保留了程序中各種函數(shù)調(diào)用的“框架”?！臼纠?2-4】將 Quicksort 算法的框架縮減為只進(jìn)行統(tǒng)計void quickcount(int l, int u)int m;if (l >= u) return; m = randint(l, u); comps += u-l; quickcount(l, m-1); quickcount(m+1, u);12這個程序能

51、夠?qū)崿F(xiàn)我們的需求，因為 Quichsort 在選擇劃分元素時采用的是“隨機(jī)”方式，并且我們假設(shè)所有的元素都是不相等的?，F(xiàn)在，這個新程序的運行時間與 n 成正比，并且相對于示例 2-3 需要的空間與 n 成正比來說，現(xiàn)在所需的空間縮減為遞歸堆棧的大小，即空間的平均大小與 lgn 成正比。雖然在實際的程序中，數(shù)組的下標(biāo)（l 和 u）是非常重要的，但在這個框架版本中并不重要。因此，我們可以用一個表示子數(shù)組大小的整數(shù)(n)來替代這兩個下標(biāo)（參見示例 2-5）【示例 2-5】 在 Quicksort 代碼框架中使用一個表示子數(shù)組大小的參數(shù)void qc(int n)int m;if (n <= 1

52、) return; m = randint(1, n); comps += n-1;qc(m-1);qc(n-m);現(xiàn)在，我們可以很自然地把這個過程整理為一個統(tǒng)計比較次數(shù)的函數(shù)，這個函數(shù)將返回在隨機(jī) Quicksort 算法中的比較次數(shù)。在示例 2-6 中給出了這個函數(shù)。【示例 2-6】 將 Quicksort 框架實現(xiàn)為一個函數(shù)int cc(int n)int m;if (n <= 1) return 0; m = randint(1, n);return n-1 + cc(m-1) + cc(n-m);在示例 2-4、示例 2-5 和示例 2-6 中解決的都是相同的基本問題，并且所需

53、的都是相同的運行時間和空間。在后面的每個示例都對這些函數(shù)的形式進(jìn)行了改進(jìn)，從而比這些函數(shù)更為清晰和簡潔。在定義發(fā)明家的（inventor's paradox）(How To Solve It, Princeton UniversityPress)時，George Póllya 指出“計劃越宏大，的可能性就越大。”現(xiàn)在，我們就來研究在分析 Quicksort 時的。到目前為止，我們遇到的問題是，“當(dāng) Quicksort 對大小為n 的數(shù)組進(jìn)行一次排序時，需要進(jìn)行多少次比較？”我們現(xiàn)在將對這個問題進(jìn)行擴(kuò)展，“對于大小為 n 的隨機(jī)數(shù)組來說，Quichsort 算法平均需要進(jìn)行多少

54、次的比較？”我們通過對示例 2-6 進(jìn)行擴(kuò)展以引出示例 2-7?！臼纠?2-7】 偽碼：Quicksort 的平均比較次數(shù)float c(int n)if (n <= 1) return 0sum = 0for (m = 1; m <= n; m+)sum += n-1 + c(m-1) + c(n-m) return sum/n如果在輸入的數(shù)組中最多只有一個元素，那么 Quichsort 將進(jìn)行比較，如示例 2-613中所示。對于更大的 n，這段代碼將考慮每個劃分值 m（從第一個元素到最后一個，每個都是等可能的）并且確定在這個元素的位置上進(jìn)行劃分的運行開銷。然后，這段代碼將統(tǒng)計這

55、些開銷的總和（這樣就遞歸地解決了一個大小為 m-1 的問題和一個大小為 n-m 的問題），然后將總和除以 n 得到平均值并返回這個結(jié)果。如果我們能夠計算這個數(shù)值，那么將使我們實驗的功能更加強(qiáng)大。我們現(xiàn)在無需對一個n 值運行多次來估計平均值，而只需一個簡單的實驗便可以得到真實的平均值。不幸的是， 實現(xiàn)這個功能是要付出代價的：這個程序的運行時間正比于 3n（如果是自行參考（self-referential）的，那么用本章中給出的技術(shù)來分析運行時間將是一個很有趣的練習(xí)）。示例 2-7 中的代碼需要一定的時間開銷，因為它重復(fù)計算了中間結(jié)果。當(dāng)在程序中出現(xiàn)這種情況時，我們通常會使用動態(tài)編程來中間結(jié)果，從而避免重復(fù)計算。因此，定義一個表 tN+1，其中在 tn中cn，并且按照升序來計算它