星期三, 4月 22, 2009

美麗程式:頂尖程式設計師的思考方式

美麗程式:頂尖程式設計師的思考方式
Leading Programmers Explain How They Think

* 作者:Brian Kernighan等
* 譯者:陳建勳
* 出版社:歐萊禮
* 出版日期:2008年04月14日
* 語言:繁體中文
* ISBN:9789866840197
* 裝訂:平裝

或許是因為我本身寫的程式不多,所以無法感受到書中某些範例的美。

  • 1 正規運算式比對器---by Brian Kernighan

    基本上這是簡單版的 regular expression decider. 與其說這篇文章是在討論何謂 beautiful code,不如說在討論簡單又有延伸性的教學題目。

  • 2 Subversion 的 Delta 編輯器:只談介面---by Karl Fogel

    完全無法體會...XD

  • 3 我從沒寫過的最美麗程式---by Jon Bentley

    文章翻得不太好,譬如『動態程式設計』一詞應該是指 Dynamic Programming,一般是翻成動態規劃。『Knuth 的出版品』,應該是指 Knuth's publication,翻作 『Knuth 的著作』比較適當。

    這章是以 Quick Sort 為主,相當有趣。實作 Binary Search 和 Quick Sort 的文章有很多,實際上 Jon Bentley 本人的文章在這方面是經典。但是這篇文章的有趣之處在於他在討論如何『做實驗』。算是延伸了他之前的經典文章,相當有趣。

    有興趣更進一步的人其實可以看看他的線上演講:Three Beautiful Quicksorts

  • 4 找東西---by Tim Bray

    這一章主要是講正規表示式和 Binary Search。有趣之處有兩點。一是他的 Binary Search 和一般不同。(Gaston Gonnet 教的)

    我們在做二元搜尋法時,需要兩個變數紀錄邊界,並以此求出中間值,但在 Tim Bray 的程式中,他假設 這兩個變數的起始值是 -1 和 n+1,也就是說,這兩個值都是不合法的。他說這樣可以不用考慮很多 boundary cases,不過我不太清楚為什麼。

    另一個有趣之處是他的迴圈不會檢查是否找到搜尋值,因為 Tim Bray 覺得反正在大部分的情況下,都要花將近 log n 的時間才能找到元素,所以直接跑完迴圈再做檢查 (因為二分逼近法會夾住我們要的結果,所以可以事後再做檢查) 反而比較省時間。

    如果我們把這個 binary search 想成是 complete binary tree,我們就會發現,最後兩層的點會佔一半。所以這樣的作法還蠻合理的。

  • 5 正確>美麗>快速:設計 XML 查證器的教訓---by Elliotte Rusty Harold

    我的感想是,constant 非常重要。在演算法時間複雜度的分析中,constant 通常是不被注意的。除了某些已經被做到很徹底的領域,像是 String Matching。但在程式設計時,根據輸入資料的大小,提供好幾個方案是必要的,譬如 hash, array 等等,各自有其適用的尺度。

    但是這種 tunning 的動作在研究中似乎並不太被重視。

  • 6 整合測試的框架:來自脆弱性的美感---by Michael Feathers
  • 7 美麗測試---by Akberto Savoia
  • 8 動態產生影像處理程式---by Charles Petzold
  • 9 由上而下運算子優先權---by Douglas Crockford
  • 10 追尋加速的族群計數---by Henry S. Warren, Jr.
  • 11 安全通訊:自由技術---by Ashish Gulhati
  • 12 BioPerl 的美麗程式---by Lincoln Stein
  • 13 Gene Sorter 的設計---by Jim Kent
  • 14 優雅程式隨硬體演化:以高斯消去法為例---Jack Dongarra & Piotr Luszczek
  • 15 美麗設計的長期益處---by Adam Kolawa
  • 16 Linux 核心驅動程式模型:一起運作的益處---by Greg Kroah-Hartman
  • 17 另一層間接層---by Diomidis Spinellis
  • 18 Python 的辭典:滿足所有人的需要---by Andrew Kuchling

    這一章節中探討了 Python 辭典的設計。跟前面幾章一樣,一些優化的討論是免不了的,尤其是在 Python 之中,很多功能基本上都是以辭典為基礎建立起來,譬如 module 和 class 都是存放在辭典之中。

    文中也包含了一些我不太清楚的設計細節,譬如當 compiler 限制的 hash function 的 range 大小時,是採用 mask 的方式直接把高位 bits 給遮住。而且為了因應大量的比較,他們會把 mask 記憶下來。當然這種 tunning 其中牽扯到很多對效能的統計分析,譬如採用 open addressing 而非 chaining 等等。

    另外,作者也提到,跟 Jython 不同,Python 並不提供專門處理字串的辭典,而是根據 lookup key 來決定,如果使用的過程中都沒有碰到非字串型態的 lookup key ,則就採用只搜尋字串的 function,如果有碰到 非字串型態的 lookup key ,才會將 搜尋函數轉化為 general 的版本。

  • 19 NumPy 的多維迭代器---by Travis E. Oliphant

  • 20 NASA 火星探測任務~ 高度可靠的企業系統---by Ronald Mak
  • 21 ERP5:追求最大適應力的設計---Rogerio Atem de Carvalho & Rafael Monnerat
  • 22 一匙污水---by Bryan Cantrill
  • 23 分散式程式設計和 MapReduce---Jeffrey Dean & Sanjay Ghemawat
  • 24 美麗的並行性---by Simon Peyton Jones
  • 25 語法抽象:syntax-case 展開器---by R. Kent Dybvig
  • 26 省力架構:網路軟體之物件導向框架---William R. Otte & Douglas C. Schmidt
  • 27 整合商務夥伴:REST 方式---by Andrew Patzer
  • 28 除錯之美---by Andreas Zeller
  • 29 把程式視為文章---by Yukihiro Matsumoto
  • 30 對世界的唯一連繫---by Arun Mehta
  • 31 Emacspeak:完備的音訊桌面---by T. V. Raman
  • 32 運行中的程式碼---by Laura Wingerd & Christopher Seiwald
  • 33 替「算書」寫程式---by Brian Hayes

沒有留言: