第3章我編寫過的最漂亮的代碼

1、第3章 我編寫過的最漂亮的代碼Jon Bentley我曾經聽一位大師級的程序員這樣稱贊到，“我通過刪除代碼來實現功能的提升?！倍▏骷壹骘w行家Antoine de Saint-Exupéry的說法則更具代表性，“只有在不僅沒有任何功能可以添加，而且也沒有任何功能可以刪除的情況下，設計師才能夠認為自己的工作已臻完美?！?某些時候，在軟件中根本就不存在最漂亮的代碼，最漂亮的函數，或者最漂亮的程序。 當然，我們很難對不存在的事物進行討論。本章將對經典Quicksort（快速排序）算法的運行時間進行全面的分析，并試圖通過這個分析來說明上述觀點。在第一節(jié)中，我將首先根據我自己的觀點來回顧

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

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

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

5、出的Quichsort算法。在示例3-1中給出了用C語言編寫的Quicksort函數。我們在接下來的章節(jié)中將進一步地研究和改善這個函數?！臼纠?3-1 Quicksort函數void quicksort(int l, int u) int i, m; if (l >= u) return; swap(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); 如果函數的調用形式是qu

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

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

8、述了我們如何設計出一個比這個算法的其他實現要更為清晰，速度更快以及更為健壯的新函數部分原因是由于這個函數的代碼更為短小。Gordon Bell的名言被證明是正確的：“在計算機系統(tǒng)中，那些最廉價，速度最快以及最為可靠的組件是不存在的?！爆F在，這個函數已經被使用了10多年的時間，并且沒有出現任何故障。 考慮到通過縮減代碼量所得到的好處，我最后以第三種方式來問自己在本章之初提出的問題。“你沒有編寫過的最漂亮代碼是什么？”。我如何使用非常少的代碼來實現大量的功能？答案還是和Quicksort有關，特別是對這個算法的性能分析。我將在下一節(jié)給出詳細介紹。3.2 事倍功半 Quicksort是一種優(yōu)雅的算法

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

10、所使用的數學知識超出了大多數程序員的理解范圍。當我為本科生講授Quicksort算法時，許多學生即使在費了很大的努力之后，還是無法理解其中的證明過程，這令我非常沮喪。下面，我們將從Hoare的程序開始討論，并且最后將給出一個與他的證明很接近的分析。我們的任務是對示例3-1中的Quicksort代碼進行修改，以分析在對元素值均不相同的數組進行排序時平均需要進行多少次比較。我們還將努力通過最短的代碼、最短運行時間以及最小存儲空間來得到最深的理解。為了確定平均比較的次數，我們首先對程序進行修改以統(tǒng)計次數。因此，在內部循環(huán)進行比較之前，我們將增加變量comps的值（參見示例3-2）?！臼纠?-2】 修

11、改Quicksort的內部循環(huán)以統(tǒng)計比較次數。 for (i = l+1; i <= u; i+) comps+; if (xi < xl) swap(+m, i); 如果用一個值n來運行程序，我們將會看到在程序的運行過程中總共進行了多少次比較。如果重復用n來運行程序，并且用統(tǒng)計的方法來分析結果，我們將得到Quicksort在對n個元素進行排序時平均使用了1.4 nlgn次的比較。在理解程序的行為上，這是一種不錯的方法。通過十三行的代碼和一些實驗可以反應出許多問題。這里，我們引用作家Blaise Pascal和T. S. Eliot的話，“如果我有更多的時間，那么我給你寫的信就會更

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

13、，同時統(tǒng)計比較的次數。不過，如果我們的目標只是統(tǒng)計比較的次數，那么就不需要對數組進行實際地排序。在示例3-4中去掉了對元素進行排序的“實際操作”，而只是保留了程序中各種函數調用的“框架”?！臼纠?-4】將Quicksort算法的框架縮減為只進行統(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); 這個程序能夠實現我們的需求，因為Quichsort在選擇劃分元素時采用的是“隨機”方式

14、，并且我們假設所有的元素都是不相等的?，F在，這個新程序的運行時間與n成正比，并且相對于示例3-3需要的存儲空間與n成正比來說，現在所需的存儲空間縮減為遞歸堆棧的大小，即存儲空間的平均大小與lgn成正比。 雖然在實際的程序中，數組的下標（l和u）是非常重要的，但在這個框架版本中并不重要。因此，我們可以用一個表示子數組大小的整數(n)來替代這兩個下標（參見示例3-5）【示例3-5】 在Quicksort代碼框架中使用一個表示子數組大小的參數void qc(int n) int m; if (n <= 1) return; m = randint(1, n); comps += n-1; qc

15、(m-1); qc(n-m); 現在，我們可以很自然地把這個過程整理為一個統(tǒng)計比較次數的函數，這個函數將返回在隨機Quicksort算法中的比較次數。在示例3-6中給出了這個函數?！臼纠?-6】 將Quicksort框架實現為一個函數int cc(int n) int m; if (n <= 1) return 0; m = randint(1, n); return n-1 + cc(m-1) + cc(n-m);在示例3-4、示例3-5和示例3-6中解決的都是相同的基本問題，并且所需的都是相同的運行時間和存儲空間。在后面的每個示例都對這些函數的形式進行了改進，從而比這些函數更為清晰和

16、簡潔。 在定義發(fā)明家的矛盾（inventor's paradox）(How To Solve It, Princeton University Press)時，George Póllya指出“計劃越宏大，成功的可能性就越大?！爆F在，我們就來研究在分析Quicksort時的矛盾。到目前為止，我們遇到的問題是，“當Quicksort對大小為n的數組進行一次排序時，需要進行多少次比較？”我們現在將對這個問題進行擴展，“對于大小為n的隨機數組來說，Quichsort算法平均需要進行多少次的比較？”我們通過對示例3-6進行擴展以引出示例3-7?！臼纠?-7】 偽碼：Quicksort的

17、平均比較次數float c(int n) if (n <= 1) return 0 sum = 0 for (m = 1; m <= n; m+) sum += n-1 + c(m-1) + c(n-m) return sum/n 如果在輸入的數組中最多只有一個元素，那么Quichsort將不會進行比較，如示例3-6中所示。對于更大的n，這段代碼將考慮每個劃分值m（從第一個元素到最后一個，每個都是等可能的）并且確定在這個元素的位置上進行劃分的運行開銷。然后，這段代碼將統(tǒng)計這些開銷的總和（這樣就遞歸地解決了一個大小為m-1的問題和一個大小為n-m的問題），然后將總和除以n得到平均值并

18、返回這個結果。 如果我們能夠計算這個數值，那么將使我們實驗的功能更加強大。我們現在無需對一個n值運行多次來估計平均值，而只需一個簡單的實驗便可以得到真實的平均值。不幸的是，實現這個功能是要付出代價的：這個程序的運行時間正比于3n（如果是自行參考（self-referential）的，那么用本章中給出的技術來分析運行時間將是一個很有趣的練習）。示例3-7中的代碼需要一定的時間開銷，因為它重復計算了中間結果。當在程序中出現這種情況時，我們通常會使用動態(tài)編程來存儲中間結果，從而避免重復計算。因此，我們將定義一個表tN+1，其中在tn中存儲cn，并且按照升序來計算它的值。我們將用N來表示n的最大值，也

19、就是進行排序的數組的大小。在示例3-8中給出了修改后的代碼?！臼纠?-8】 在Quicksort中使用動態(tài)編程來計算t0 = 0for (n = 1; n <= N; n+) sum = 0 for (i = 1; i <= n; i+) sum += n-1 + ti-1 + tn-i tn = sum/n 這個程序只對示例3-7進行了細微的修改，即用tn來替換c(n)。它的運行時間將正比于N2，并且所需的存儲空間正比于N。這個程序的優(yōu)點之一就是：在程序執(zhí)行結束時，數組t中將包含數組中從元素0到元素N的真實平均值（而不是樣本均值的估計）。我們可以對這些值進行分析，從而生成在Qui

20、chsort算法中統(tǒng)計比較次數的計算公式。我們現在來對程序做進一步的簡化。第一步就是把n-1移到循環(huán)的外面，如示例3-9所示?！臼纠?-9】 在Quicksort中把代碼移到循環(huán)外面來計算t0 = 0for (n = 1; n <= N; n+) sum = 0 for (i = 1; i <= n; i+) sum += ti-1 + tn-i tn = n-1 + sum/n現在將利用對稱性來對循環(huán)做進一步的調整。例如，當n為4時，內部循環(huán)計算總和為：t0+t3 + t1+t2 + t2+t1 + t3+t0在上面這些組對中，第一個元素增加而第二個元素減少。因此，我們可以把總和

21、改寫為：2 * (t0 + t1 + t2 + t3)我們可以利用這種對稱性來得到示例3-10中的Quicksort。【示例3-10】 在Quichsort中利用了對稱性來計算t0 = 0for (n = 1; n <= N; n+) sum = 0 for (i = 0; i < n; i+) sum += 2 * ti tn = n-1 + sum/n然而，在這段代碼的運行時間中同樣存在著浪費，因為它重復地計算了相同的總和。此時，我們不是把前面所有的元素加在一起，而是在循環(huán)外部初始化總和并且加上下一個元素，如示例3-11所示。【示例3-11】 在Quicksort中刪除了內部循

22、環(huán)來計算sum = 0; t0 = 0for (n = 1; n <= N; n+) sum += 2*tn-1 tn = n-1 + sum/n 這個小程序確實很有用。程序的運行時間與N成正比，對于每個從1到N的整數，程序將生成一張Quicksort的估計運行時間表。 我們可以很容易地把示例3-11用表格來實現，其中的值可以立即用于進一步的分析。在3-1給出了最初的結果行。表3-1 示例3-11中實現的表格輸出NSumtn000100201322.66747.3334.8335177.4631.810.3752.413.486879.37116.921這張表中的第一行數字是用代碼中的三

23、個常量來進行初始化的。下一行（輸出的第三行）的數值是通過以下公式來計算的：A3 = A2+1 B3 = B2 + 2*C2 C3 = A3-1 + B3/A3 把這些（相應的）公式記錄下來就使得這張表格變得完整了。這張表格是“我曾經編寫的最漂亮代碼”的很好的證據，即使用少量的代碼完成大量的工作。 但是，如果我們不需要所有的值，那么情況將會是什么樣？如果我們更希望通過這種來方式分析一部分數值（例如，在20到232之間所有2的指數值）呢？雖然在示例3-11中構建了完整的表格t，但它只需要使用表格中的最新值。因此，我們可以用變量t的定長空間來替代table t的線性空間，如示例3-12所示?！臼纠?

24、-12】 Quicksoft 計算最終版本 sum = 0; t = 0for (n = 1; n <= N; n+) sum += 2*t t = n-1 + sum/n 然后，我們可以插入一行代碼來測試n的適應性，并且在必要時輸出這些結果。這個程序是我們漫長學習旅途的終點。通過本章所采用的方式，我們可以證明Alan Perlis的經驗是正確的：“簡單性并不是在復雜性之前，而是在復雜性之后” ("Epigrams on Programming," Sigplan Notices, Vol. 17, Issue 9)。3.3 觀點在表3-2中總結了本章中對Quicks

25、ort進行分析的程序。表 3-2 對Quicksort比較次數的統(tǒng)計算法的評價 示例編號 代碼行數 答案類型 答案數量 運行時間 空間 2 13 Sample 1 n l g n N 3 13 " " " " 4 8 " " n lgn 5 8 " " " " 6 6 " " " " 7 6 Exact " 3N N 8 6 " N N2 N 9 6 " " " " 10 6 " &qu

26、ot; " " 11 4 " " N " 12 4 Exact N N 1 在我們對代碼的每次修改中，每個步驟都是很直接的；不過，從示例3-6中樣本值到示例3-7中準確值的過渡過程可能是最微妙的。隨著這種方式進行下去，代碼變得更快和更有用，而代碼量同樣得到了縮減。在19世紀中期，Robert Browning指出“少即是多（less is more）”，而這張表格正是一個證明這種極少主義哲學（minimalist philosophy）的實例。我們已經看到了三種截然不同的類型的程序。示例3-2和示例3-3是能夠實際使用的Quicksort，可以

27、用來在對真實數組進行排序時統(tǒng)計比較次數。示例3-4到示例3-6都實現了Quicksort的一種簡單模型：它們模擬算法的運行，而實際上卻沒有做任何排序工作。從示例3-7到示例3-12則實現了一種更為復雜的模型：它們計算了比較次數的真實平均值而沒有跟蹤任何單次的運行。我們在下面總結了實現每個程序所使用的技術：*示例3-2，示例3-4，3-7:對問題的定義進行根本的修改。* 示例3-5，示例3-6，3-12：對函數的定義進行輕微的修改* 示例3-8：實現動態(tài)編程的新數據結構這些技術都是非常典型的。我們在簡化程序時經常要發(fā)出這樣的疑問，“我們真正要解決的問題是什么？”或者是，“有沒有更好的函數來解決這

28、個問題？”當我把這個分析過程講授給本科生時，這個程序最終被縮減成零行代碼，化為一陣數學的輕煙消失了。我們可以把示例3-7重新解釋為以下的循環(huán)關系： 這正是Hoare所采用的方法，并且后來由D.E.Knuth在他經典的The Art of Computer Programming（Addison-Wesley）一書的第三卷：排序與查找中給出的方法中給出了描述。通過重新表達編程思想的技巧和在示例3-10中使用的對稱性，使我們可以把遞歸部分簡化為：Knuth刪除了求和符號，從而引出了示例3-11，這可以被重新表達為一個在兩個未知量之間有著兩種循環(huán)關系的系統(tǒng)： Knuth使用了“求和因子”的數學方法來

29、實現這種解決方案： 其中表示第n個調和數（harmonic number），即1 + 1/2 + 1/3 + 1/n。這樣，我們就從對程序不斷進行修改以得到實驗數據順利地過渡到了對程序行為進行完全的數學分析。 在得到這個公式之后，我們就可以結束我們的討論。我們已經遵循了Einstein的著名建議：“盡量使每件事情變得簡單，并且直到不可能再簡單為止。”附加分析 Goethe的著名格言是：“建筑是靜止的音樂”。按照這種說法，我可以說“數據結構是靜止的算法。”如果我們固定了Quichsort算法，那么就將得到了一個二分搜索樹的數據結構。在Knuth發(fā)表的文章中給出了這個結構并且采用類似于在Quich

30、sort中的循環(huán)關系來分析它的運行時間。如果要分析把一個元素插入到二分搜索樹中的平均開銷，那么我們可以以這段代碼作為起點，并且對這段代碼進行擴展來統(tǒng)計比較次數，然后在我們收集的數據上進行實驗。接下來，我們可以仿照前面章節(jié)中的方式來簡化代碼。一個更為簡單的解決方案就是定義一個新的Quichsort，在這個算法中使用理想的劃分算法把有著相同關聯順序的元素劃分到兩邊。Quichsort和二分搜索樹是同構的，如圖3-1所示。圖3-1 實現理想劃分的Quicksort以及相應的二分搜索樹左邊的方框給出了正在進行中的理想劃分的Quicksort，右邊的圖則給出了相應的從相同輸入中構建起來的二分搜索樹。這兩

31、個過程不僅需要進行相同次數的比較，而且還將生成相同的比較集合。通過在前面對于在一組不同元素上進行Quicksort實驗的平均性能分析，我們就可以得到將不同的元素隨機插入到二分搜索樹中的平均比較次數。3.4 本章的中心思想是什么？表面上看來，我“所寫的”內容就是從示例3-2到示例3-12的程序。我最初是漫不經心地編寫這些程序，然后將這些程序寫在給本科生講課的黑板上，并且最終寫到本章中。我有條不紊地進行著這些程序的修改，并且花了大量的時間來分析這些程序，從而確信它們都是正確的。然而，除了在示例3-11中實現的表格外，我從來沒有把任何一個示例作為計算機程序運行過。 我在貝爾實驗室呆了將近二十年，我從

32、許多教師（尤其是Brian Kernighan，他所編寫的編程內容作為本書的第1章）那里學到了：要“編寫”一個在大眾面前展示的程序，所涉及到的東西比鍵入這個程序要多得多。有人用代碼實現了這個程序，最初運行在一些測試示例中，然后構建了完整的系統(tǒng)框架、驅動程序以及一個案例庫來支撐這段代碼。理想的情況是，人們可以手動地把編譯后的代碼包含到文本中，不加入任何的人為干涉?；谶@種想法，我編寫了示例3-1（以及在Programming Pearls中的所有代碼）。為了維護面子，我希望永遠都不要實現從示例3-2到示例3-12的代碼，從而使我保持誠實的名聲。然而，在計算機編程中的近四十年的實踐使我對這個任務的

33、困難性有著深深的敬畏（好吧，更準確地說，是對于錯誤的害怕）。我妥協了，把示例3-11用表格方式實現出來，并且無意中得到了一個完備的解答。當這兩個東西完美地匹配在一起時，你可以想象一下我當時的喜悅吧！因此，我向世界提供了這些漂亮的并且未曾實現的程序，雖然在這些程序中可能會有一些還未發(fā)現的錯誤，但我對這些程序的正確性還是有一定信心的。我希望一些細微的錯誤不會掩蓋我在這些程序中所展示的那些漂亮思想。 當我為給出這些沒有被實現過的程序感到不安時，Alan Perlis的話安慰了我，他說“軟件是不是不像任何一個事物，它就是意味著被拋棄：軟件的所有意義就是把它看作為一個肥皂泡？”3.5 結論 漂亮的含義有

34、著許多來源。本章通過簡化、優(yōu)雅以及精簡來刻畫了漂亮的含義。下面這些名言表達的是同樣的意思：*通過刪除代碼來實現功能的提升。*只有在不僅沒有任何功能可以添加，而且也沒有任何功能可以刪除的情況下，設計師才能夠認為自己的工作已臻完美。*有時候，在軟件中根本就不存在最漂亮的代碼，最漂亮的函數，或者最漂亮的程序。*良好的寫作風格即為簡練。省略不必要的字詞。 (Strunk and White)*在計算機系統(tǒng)中，那些最廉價、速度最快以及最為可靠的組件是不存在的（Bell）*努力做到事倍功半。*如果我有更多的時間，那么我給你寫的信就會越短（Pascal）*發(fā)明家的矛盾：計劃越宏大，成功的可能性就越大。（Pólya）*簡單性并不是在復雜性之前，而是在復雜性之后（Perlis）*少即是多。（Browning）*盡量使每件事情變得簡單，并且直到不可能再簡單為止（Einstein）*軟件有時候應該被視作為一個肥皂泡（Perlis）*在簡單中尋找漂亮。本章的內容到此結束。讀者可以復習所學到的內容并進行模擬實驗。對于那些想要得到更具體信息的人們，我在下面給出了一些觀點，這些觀點分為三類程序分析 深入理解程序行為的方式之一就是修改這個程序，然后在具有代表性的數據上運行這個程序，就像示例3-2那樣。不過，我們通常會更關心程序的某個方