[讀書心得] Programming Pearls 心得





書名:Programming Pearls (2nd Edition)
作者:Jon Bentley

Programming Pearls 這本書裡面,主要分成三大部分:
第一部分 (Column 1~5) 講述程式設計的一些基本觀念.
第二部分 (Column 6~10) 講的是程式的效能調校.
第三部分 (Column 11~15) 講的是分析實際上遇到的問題.

這本書很有意思,很多地方對於程式設計師都有很大的啟發.最好是開始學程式設計時,就熟讀這本書.
書裡面想要講的,並不是多高深的學問,而是使用簡單的例子引導你去思考為什麼!這一點我覺得很棒!

第一部分講的五個專欄,摘要如下:

Column 1 問題描述
程式設計師在學了一些資料結構或演算法之後,遇到問題總是會迫不及待的運用自己會的資料結構或演算法,而忘記仔細去了解問題本身是不是有更簡單的解法?
舉例說明:
假設你的磁碟非常的大,但是 RAM 只有 1M Bytes。在磁碟裡面大概存了 n 個唯一的正整數 (任兩個整數值都不同),每一個正整數都小於 n ,而 n=10^7。問題來了,你要怎麼設計一個最快的演算法來輸出一串由小到大排序好的數字? (這一題 Interview 實在太常考啦!)
從課本裡面出來的解法,都沒有辦法有效率的解決這個問題!但是其實解法很簡單,怎麼解呢? 請參考本書的 Column 1。 “Cracking the code interview” 那本書裡面,有 Java 版的解法。
當你詳細了解了問題之後,你就有更大的機率可以想出解決特定問題的特定演算法,讓你更有效率的解決問題.

Column 2 演算法
作者要讀者思考三個問題怎麼解:

  1. 給定一個檔案,檔案裡面大概有 40 億筆 32-bit 隨機順序的整數的資料,請找出一個不在這個檔案裡面的32-bit 整數!如果你有很多記憶體空間,你如何解決這個問題?如果有只有幾百 bytes 的記憶體,但是你有很多檔案空間,你會如何解決這個問題?
  2. 將一個有 n 個字元的一維向量往左旋轉 i 個位置。譬如說:原本的向量值是 abcdefgh,而 $n=8, i=3$ 時,向量會旋轉成 defghabc。如果我們只有幾十 bytes 的多餘空間,我們要如何做這個旋轉的動作呢?
  3. 給定一個英文字典,找出 anagrams 的所有集合。譬如說,”pots”, “stop”, 跟 “tops” 彼此是 anagrams,因為他們是使用同樣的字母排列組合而產生。

問題 2 有一個很快而且很酷的演算法,方法如下:
假設 reverse(int i, int j) 是將從 index i 到 index j 的字元反轉,則將 n 個字元的向量旋轉 i 個位置的方法如下:

Column 3 資料結構

  • 如果可以把程式寫的簡短扼要,千萬不要把它寫的很長。
  • General case 有可能比 special case 還要好解。譬如說,你要寫一個跟數值 23 相關的程式,到不如寫一個跟 n 相關的程式,再令 $n=23$ 帶入求解。General case n 的程式有可能比 Special case 23 的程式好寫。
  • 如果發現有很多重複的 code ,可以思考一下是不是應該使用 Array。譬如說,你有很多 menuitem,check 其中一個之後,要 uncheck 所有其它的 menuitem,這個時候 array 加 for 迴圈就很好用了。
  • 想辦法將複雜的結構封裝起來。
  • 可以的話選擇進階的工具來解決問題,譬如說選用 Hypertext, name-value pairs 等。
  • 配合所選用的合適的資料結構來撰寫程式。

Column 4 程式驗證
在這一章裡面,作者提到使用 test case 來驗證 pseudo code 的重要性。他舉出在 Knuth 的書裡面提到,Binary Search 的概念在 1946 年就被提出來了,但是到 1962 年第一個沒有 Bug 的 Binary Search 才出現,這就是沒有做好程式驗證的關係。

Column 5 測試
這一章講述了簡單的 Testing (Scaffolding 跟 automated testing 等), Debugging, 跟 Timing 的觀念。

Column 6 關於效能

Column 7 概略估算 (The back of the Envelope)

Column 8 如何設計演算法?

Column 9 程式調校 (Code Tuning)

Column 10 充分運用空間

Column 11 排序

Column 12 取樣問題

Column 13 搜尋

Column 14 堆積

Column 15 字串問題中的精品

發現很多地方有點忘了,各章節的細節,等我再看一次這本書之後,再來寫吧~ :p




Be the first to comment

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.