2010年11月21日 星期日

Problem Solving 的技巧 (1):系統設計是一連串的取捨

費曼和杜書伍可說是影響我思考方式最深的人,即使重覆閱讀、重新思考他們話,仍能獲得不少新體悟。今天偶然發現《真正的問題是什麼?你想通了嗎?》的推薦序是杜書伍寫的,看了以後收獲良多,看了這麼多書,這還是頭一回看了推薦序而覺得有用。

文中提到:

釐清問題的真實性後,面對真正的問題時,須有一個認知:甚少問題能以單一方案解決,而須由不同面向,分頭淡化問題。...這些不同面向的解法,單獨用都只能解決局部問題,但配套提出後,卻能大幅降低問題的嚴重性,到一可接受的範圍內。

企業經營無時不刻面臨問題的發生與解決,在問題決的過程中會發現,現實生活中並沒有可「百分之百」被解決的問題。誠如書中所言:「每一個解決方案都是下一個問題的根源」,一個有利於某面向的方案,代價往往是犠牲另一面向的利益。因此,如何透過溝通、妥協的過程,尋求最適的解法而非完美的解法,將問題的衝擊降到多數人可接受的範圍內,即為好的解決方式,否則反而可能適得其反,滋生新的問題。

看了這段話,更明白杜書伍花了多少歲月與心力實踐他在《打造將才基因》裡說的方法,完全是實實在在的真工夫。用精簡的文字描述出極為深刻的道理,實在是太厲害啦!

舉例來說,使用資料庫時,需同時擔心寫入速度和確保不會損失資料。若每次寫入時都寫入硬碟,可以確保資料正確,但卻會很慢;若先寫入記憶體,集合成一批再一起寫入硬碟,可以大幅提昇速度,但若資料庫伺服器當掉,卻會喪失大批資料。

一個配套解法是每次都寫入硬碟確保資料正確,接著使用 RAID 提昇寫入速度。但是用上 RAID 仍是操作硬碟,提昇有限,於是再加上帶有 write cache 的 RAID,這樣就能大幅提昇速度。但這又造成新的問題:雖然資料庫伺服器掛了不會影響資料,但若機房停電,仍會喪失 RAID cache 內的資料。於是在 RAID 裡加上電池,就能克服這問題 (附帶一提,我很喜歡這句話:「系統設計是一連串的取捨」)。

整個串起來就是「資料庫伺服器每次都寫入硬碟,並使用帶有 write cache + 電池的 RAID 機器」,這樣能同時兼顧寫入速度並確保不會損失資料,不過就變成大幅提昇開銷了。若將支出也列入考量點的話,配套解法可能又不同,也許是降低寫入速度的要求,也許是容許損失多少時間內的資料。

以這麼技術的問題做為例子,其實有損杜書伍提的解題思維、以及《真正的問題是什麼?你想通了嗎?》的價值。真正在解決問題時,需要思考多個面向,而不能只局限在定死的框架裡以技術本位思考。以資工的術語類比的話,用 BFS 的方式思考會比 DFS 容易找出好方案。比方說可以考慮修改規格或換方式滿足需求,或是重新定義問題,找出真正的需求和剛好到位的解法。問題往往來自於期望和感受之間出現落差,有時換個角度看問題,就能剛好繞開原本的技術難題,並且沒有犠牲任何事情。

以我最近在做的事為例,我在找網站壓力測試的工具,雖然能找到一些好用的工具,但它們卻沒提供良好的登入機制,讓我無法開始測試。若硬往技術方向思考,解決問題的選項不外乎再找下一個工具,或是改工具的程式碼,加入一個前置登入的機制。但其實退一步思考,我真正的需求是產生大量連線,以「如同使用者登入」的方式進行壓力測試,我並不需要用正規的方式登入自家網站,大可另寫一個網址,開後門避開繁瑣的登入流程,直接登入測試帳號。於是,我只需要評估壓力測試工具,不用在意它是否有完備的登入機制。

但思考面向變廣後,比起定好其它因素、單純考量技術來說,問題也變得更複雜。要有效地在不同面向間穿梭,需要更多的經驗和練習,就像以往專精學一件事一樣,只是變得更困難。杜書伍在《打造將才基因》裡有不少這方面的說明,強烈推薦閱讀。概念是先專精一個技能,接著專精第二個技能,並找出和先前學習經驗的異同點,融會兩者成為自己的思考系統。接著專精第三個、第四個技能,找異同點,漸漸拼出多元且深入的思考方式。

最近這一年有點開竅,開始會朝多元化思考,先記錄目前的體悟。待有更多經驗後,再來寫心得吧。

2010年11月4日 星期四

讓 if、else 帶有更明確的語意

最近在維護程式時對於 if、else 有更深的體會,一但邏輯分支變多,很難釐清各種控制流程,一些簡單的習慣可以大幅簡化除錯和改程式的負擔。

變數的初始值

一個常見的情境是有個變數會依條件而有不同的值,典型的寫法如下:

1
2
3
4
5
# 假設後面有一長串算式會乘上 weight,這裡先決定它的值
if double:
   weight = 2
else:
   weight = 1

( 備註,在 Python 裡 if / else 裡設的變數和它的外層是同一個 scope。 )

或是善用程式語言提供的三元運算子設值 (即 ? : ),在 Python 裡則是這麼寫:

1
weight = 2 if double else 1

若有多種情況,在其它語言裡可能會用 switch,我個人不喜歡 switch,覺得用起來不直覺,Python 裡也沒有 switch,但可以用 dict 代替:

1
2
3
4
weight = {
    'double': 2,
    'triple': 3,
}.get(condition, 1)

操作複雜時可在 dict 的 value 裡改用輔助的小函式,明確的用簡短的程式表明「這區塊在決定 weight 的值」。

別小看這一點小改變,當程式碼很多時,看到 “value = a if condition else b” 可以立即明白這裡的判斷式是用來設值,可以省下為 if、else 這區塊煩心的時間,也可以減少消耗精神和腦內暫存記憶。

提前處理簡單的分支

以用遞迴的方式實作費氏數列為例:

1
2
3
4
5
6
def fib(n)if n < 0:  # Error input.
        raise ValueError('n must be positive.')
    if n == 0 or n == 1return 1
    return fib(n - 1) + fib(n - 2)

上面的寫法先處理例外,接著就能放心處理正常的情況,再來處理特例 (初始值),最後就能專心和主邏輯奮戰,而覺得主邏輯變得單純許多,很好處理。

較大的程式,就是先寫幾個簡單輔助小函式 (例如 is_invalid()),先呼叫小函式避開特殊情況,一樣可以化繁為簡。

避免巢狀區塊和 continue、break

常見到在多層迴圈裡呼叫 if、else,並和 continue、break 混用,我個人覺得這種寫法很亂,而傾向用小函式 + return 避開使用 continue 或 break,比方像下面的程式要從一個兩層 list 裡找出每個 list 第一個負數,並算出負數的總和:

1
2
3
4
5
6
7
sum = 0
for numbers in a_list_of_numbers:
    for n in numbers:
        if n < 0break
    if n < 0sum += n

可以改用小函式配合 return 避免使用 break 並「隱藏」分支:

1
2
3
4
5
6
7
8
9
10
def find_first_negative(numbers)'''Return 0 if there is no negative number.'''
    for n in numbers:
        if n < 0return n
    return 0
 
sum = 0
for numbers in a_list_of_numbers:
    sum += find_first_negative(numbers)

改寫後,兩個 if 都不見了,主邏輯很清楚地表現出「找出各 list 第一個負數並加總」。

同樣的,程式愈複雜時,這些寫法省下的思考時間愈可觀。

明確的指明 else 的處理方式

這和前面提的東西有一點相衝突,視情況而定。在任何有 if、elif 的情況,即使 else 的情況不需做任何處理,仍要明確的寫出 else 並加上註解。如下所示:

1
2
3
4
5
6
if some_condition:
    ...
elif another_condition:
    ....
else:  # Do nothing.
    pass

這個作法的目的是,讓其他讀這份程式的人,明白原作者沒有漏考慮 else 的情況,不處理是符合預期的作法。函式愈長時,這樣寫的好處愈明顯。別小看這個小動作,程式碼一多,回頭讀程式碼時,這點小動作可以省下不少分心的機會。

結語

上面提的例子背後的目的都一樣,就是避免讀程式碼的人分心在分支裡,而能專注在主邏輯上。類似的例子還有「使用 iterator 少用 for + index」,平時留意一些小細節,不但能愈寫愈快 (省去煩心細節的時間),也能降低維護成本,讓其他人易於理解。舉手之勞做環保,大家一起來維護程式碼的品質吧!

2010年9月11日 星期六

每件事都有它的價值

過去我一直在尋找捷徑,希望能找到經驗以外的價值,不然只是比年資,感覺很無趣。老手比新手強,只是因為他做得久、比較熟悉公司內的程式。待新手變強後,也只是因為他經驗變多。似乎人與人之間沒什麼差異性。改善自己學習的方式是個好主意,但有智慧的人都會不斷改善自己學習的方式,以能夠更有效率地學習。我不斷地思考自己的定位,以及如何學得更有效率。期望在天份、經驗外找到其它的聖杯。

Steve Jobs 在對 Stanford 大學的畢業演講裡提到:

Again, you can’t connect the dots looking forward; you can only connect them looking backwards.

抱著半信半疑的心態,我只能先相信這個看法,繼續邊做邊想。

後來在杜書伍的《打造將才基因》裡看到:

我並末想出什麼令人拍案叫絕的答案來,但當時得到的結論卻一直到現在我都認為是正確的,...,經驗要累積得快,除了比別人更努力工作外,似乎找不到其他的方法。

看第一次時仍是半信半疑。然而,最近重讀這本書,對照近來的體悟,忽然間想通了這點。

在經歷 TDD 的洗禮後,我覺得我好像找到一個不錯的答案,至少它是我在軟體開發領域裡找到最好的答案。似乎只要練 TDD,就能在同樣時間內爆增功力。相較於過去看的 Design Pattern、程式語言實作技巧等,TDD 似乎更宏觀實用。

就在實踐 TDD 一年後,偶然看到別人的討論,而有不同想法。練習 TDD 後確實能寫出較好維護的軟體,不過除錯的經驗也變少了。寫了快一年半的程式下來,我一直沒有用 debugger 的需求,只開過兩三次 python debugger,碰一下就放棄它,改成補寫 unit test 偵錯。這才發覺,每段時間都有它的意義,只是練得目標不同。我明白照目前的方式走下去,再過個三年五年,我用 TDD 的功力會愈來愈深,不過用 debugger 功力仍然會是零。這沒好壞之分,端看目標為何,以及自己的定位。

在其它學習的經驗裡,發覺看過的知識,還是要實際操作過數次才能內化到自己的思考體系裡。操作次數愈頻繁,體悟愈深。像許多系統設計或軟體開發流程的最佳實踐 (best practice),還是要走過不同的路,回頭才會明白最佳實踐背後的考量,才知道如何融會這些點到自己的情境裡。很多東西光用看的,或光用做的,無法體會背後的精神,遇到狀況時仍然使不出來。所以,減少嘗試多讀最佳實踐,效果有限;老是硬幹不讀別人的體悟,也是效果有限。

剛才在聊看 Python 源始碼的事Scott Thinker 不約而同建議直接看原始碼,而不用看書 (即使 Scott 認為書本的大綱看來不錯)。但我覺得先看書有個概念再來看原始碼應該比較有「效率」。經 Thinker 說明,才發覺這是練得目標不同。直接硬啃 code 看來較費工,但在費工之中才會有更多練習讀碼的機會,會更熟練相關工具和技巧。而我的目的是增加系統設計經驗為主,讀原始碼為輔,自然會覺得先讀書較好。

每件事都有它的價值,每個技術都需要時間才能挖深。然而,要將走過的路合起來發揮最大功效,要將所學收斂在相關領域裡。這讓我不經花更多時間思考,往後自己的定位為何,我想發展什麼樣的知識網。總之,相信 Steve Jobs 和杜書伍的話,「Stay hungry. Stay foolish.」繼續邊做邊想吧。

2010年7月18日 星期日

學習的自我要求

學生時代我一直在想一個問題,究竟是問題導向的學習方式較佳,還是技術導向較佳?舉例來說,我想寫個留言版,我發現要完成最基本的需求,我得學 HTML、PHP 和 MySQL,於是我針對我要做的功能學相關的語法,最後完成留言版。可能資料庫設計沒用到正規化,網站外觀沒用到 CSS,一些動態功能用 PHP 實現而非 JavaScript。相較於從頭學寫網站所需的各項技術,這個作法比較務實,我用較少的時間完成目標。極端地看,用問題導向的解法時,我可能找到相關的程式碼,用它們拼貼出結果,但不確定各塊在做什麼。技術導向的解法,可能要先花一段時間弄清楚寫網站需要的技術,再各別學個基本能力,接著開始實作。當然,世界上不是只有 0 和 1,我們常混著用問題導向和技術導向的方式解問題。這裡我說用問題導向的意思,是指偏向用問題導向。

不只做產品,做研究時也是類似的情況。問題導向就是從問題開始往下挖,看前人做那些方法,將自己不熟的部份補起來,有了必要的知識後,就能回頭解決問題。而技術導向的做法,我可能會加強基礎學科知識,視類別而定可能是機率和線代,或是計算機組織和編譯器,接著才開始思考如何解問題(或重新定義問題)。

以前我沒什麼時間觀念,通常是技術導向的作法,覺得有趣就看我能從多底層開始往上學。比方說使用 Java Collections Framework 時,我會弄清楚我要用的資料結構怎麼運作的的,時間複雜度是多少。實際上大部份的使用情境不需要這些知識,稍微讀一下文件的注意事項即可。要用 machine learning 的工具,就找適合的 machine learning 課程講義來讀,弄清楚要用到的 model 怎麼運作。直到現在,我無法確認這些對於使用工具究竟幫了多少忙,當初花的時間對應到目前的幫助,真的划算嗎?

最近我試著用問題導向的方式解問題,初期進展確實比較快,不過後來遇到一些狀況,才發覺技術導向的好處。有些情況,我們根本不明白問題出在那裡,有太多可能。舉例來說,前幾天我和同事發覺不同使用者登入同一頁面,操作速度卻差了一大截。有許多可能原因:網路連線 、網頁框架、資料庫等。做了一些初步測試,我懷疑是 MySQL 根據歷史記錄做錯 query optimization。於是用 EXPLAIN  看相同的 SQL 配合不同使用者 ID,結果發現 MySQL 執行 query 的方式有細微差異,造成取出某些使用者的資料時,用較慢方式執行 SQL。於是讓 MySQL 重分析表內的資料後,問題就解決了。若不是之前稍微看過 MySQL 執行 query 的相關知識,不會這麼快就直指問題核心。也許就會用別的方式繞開這問題,一輩子都不知道怎麼解它。待發生類似問題時,又用別的方式繞開它,長遠來看浪費開發時間又增加維護成本。

另一個反面的例子是,我一直沒用 lock 的習慣,教科書告訴我們 deadlock 很可怕,所以我會想辦法避開用 lock。結果最近有個小專案因為沒用 lock,真的發生 race condition 造成有一點點資料不正確。實作前我明白會有這樣的狀況,但這個問題對我們的目的沒什麼影響,衡量開發時間後我決定寫下註解強調會有 race condition,而選擇不處理它。對照最近的體悟,我明白這樣下去我不可能學會用 lock,這不是個好現象,所以又找時間回頭看 MySQL 怎麼 lock table,結果比想像中來得簡單,之前多慮了。

有很多類似這種的逃避例子,像多人一起寫程式容易有問題,於是大家傾向將功能切乾淨,每人寫沒有交集的功能,最後再來整合。但是,對照近年來的軟體開發的趨勢,愈早整合愈容易解決問題。一個人開發容易有盲點,互相協助可以降低初期錯誤,以利後期整合。問題是,要能順利地多人共同開發,得做對不少事才行。像是版本管理系統、coding style、天天合併程式等。每一項都需要時間練習。若一個人開發時有好好練習,和別人合作時會減少許多問題,比較容易推動密集的團隊合作。

在面試別人時,我發覺一個問題:有些人學到的技能剛好只能應付他負責的專案。問題在於,若平時我們都處理簡單的專案,要怎麼轉去負責困難的專案?兩者之間有個斷層。像這類的例子不勝杖舉。比方說要從資料庫表 A 取出部份資料塞入表 B,最「簡單」的作法是寫個程式用 SQL 取出資料,用程式做些處理再用 SQL 一筆筆寫入表 B。另一個作法是直接用一個較複雜的 SQL 直接搞定。當資料量大時,後者執行速度會快上不少。並且,學會後者的寫法後,之後只要花一點時間就能處理類似的情況,不用再寫一個小程式。其它像寫程式的習慣、用程式工具的習慣,都是一樣的。多數情況我們可以用最「不費力」的作法滿足需求,但長遠來看卻是毫無長進。實際上有更有效率的作法,這裡的效率包含開發時間和軟體品質。

對照大學的程式來看,這一年來我以為自己程式已寫得頗有品質了,雖然知道一些小問題,但覺得並不迫切,也不知怎麼查相關的解法,就放著它們。最近翻了一下 Effective Java 第二版Growing Object-Oriented Software Guided by Tests,才發覺還有太多的東西要學,自己和資深的軟體工程師差了一大截,照我目前的學習方式,和他們的差距只會拉大不會縮短。若只專注完成眼前的工作,我永遠無法補足和更難工作之間的差距,這才驚覺問題導向的盲點。

走過天平的兩端後,我現在的體悟是,得雙向夾擊來解決問題。一方面用問題導向解問題以符合時程,確保時間有花在刀口上。另一方面再抽時間用技術導向的方式強化自己的實力。如此一來,在完成當下的專案的同時,也有一點一滴地補足技術斷層,取得挑戰更難專案的機會。題外話,英文也是很重要的「技術」,這一年來我半強迫地讓自己盡量搜英文文件,思考關鍵字比以前敏銳不少,閱讀速度也變快,獲得答案的速度比以前快、品質也較佳。

2010年5月29日 星期六

養成寫程式的好習慣

我很喜歡 Kent Beck 說的這段話
“I’m not a great programmer, I’m a pretty good programmer with great habits.”
從學生時代開始,我就習慣照著書上的建議寫程式,一直沒覺得什麼特別的。後來和一些人合作,或是看到別人抱怨那裡又出錯了,才驚覺那些好習慣有這麼大的影響力。試著在一些場合向別人說明如何改進寫程式的方式,才發覺很難改變寫程式的習慣 — 大概就和我一直無法早睡早起一樣難...。

大前研一說許多人在解決問題時誤把結果當原因,沒有深入追究問題的根本,只是解決問題根源造成的表面問題。寫程式自然會有 bug,但是有許多 bug 並不是 bug,而是壞習慣造成的。像是在 PHP 或 JavaScript 裡不用 === 和 !==,而被 type casting 誤導造成 bug。或是在 if / while 裡用 assignment 又不小心漏了括號,寫出 if (a=foo() > 0) 這類 bug。
好習慣得隨時間慢慢累積,做得愈多愈久,功力自然會變深。就如同龜仙人要悟空和克林送牛奶那般練基礎功,帶著好習慣寫程式,經年累月下來,學到的東西會更多。以下針對一些特定的習慣提我自己的感受。

Coding style

網路上有不少 coding style 建議,有些如 Google coding style 甚至會解釋為何要這麼寫,這樣寫的好處和壞處為何。可以學到不少寫程式的小技巧。
最近遇到的實例是遵守 Python coding style 所說,在 module 開頭寫 import,並照順序 import 內建、第三方模組和自己的模組。在程式寫到近兩萬行後要做些修改時,我發覺這個簡單的習慣,讓我很容易明白那些模組有關聯,很快就能找出要修改的程式。反過來說,閱讀一些 Django 程式碼時,發覺常在函式裡 import module,不易掌握模組之間的關係。
還有控制函式的行數在螢幕的高度內、區域變數的使用範圍(要用到時再「宣告」)、避免用全域變數。遵守這些習慣使我容易掌握變數的影響範圍,除錯時可以省下不少心思思考變數是否被別的地方改到。
最近初學 JavaScript,就在 coding style 的建議裡找到減少 global object 和管理變數 scope 的技巧:使用一個 global object 存放所有變數和函式,藉此在 JavaScript 中做出模組的效果。

Version control (以 Mercurial 的指令為例)

即使一個人寫程式,version control 仍有很大的用處。保持每個 commit 精簡,每個 commit 只完成一個小功能,就能輕易追踪過去的改變。
以下是幾個我常用 VCS 協助的情況:
  • 寫程式較不怕被中斷,只要 hg diff 就知道剛才改了什麼。commit 前也能清楚明白這次做了那些修改,去掉忘了除掉的 debug code。
  • 可以放心地修改,改到昏頭就 hg up -C 清掉剛才不知所云的修改,不用花費力氣將程式弄回正常的版本。
  • 寫到一半發覺要先完成另一個功能,hg shelve 暫存目前的修改,接著將另一個功能做完並 commit,再 hg unshelve 回頭做原本的事,可以輕鬆地切換目標,隨時專注在目前的目標上。
  • 若發覺某個功能忽然不能運作,hg up 切回舊的版本,做個 binary search (或用 hg bisect) 立即找到改出問題的 commit。由於每個 commit 都很精簡,看一下就會找到改爛的原因。
我最近用 jQuery 寫的程式,過了一陣子後發覺某個功能不能運作。用 hg up 和 binary search 的方式,很快地找到在一百多版前改爛的,而且改爛的原因很奇妙,我將目標 tag 的 id 設為 “submit” 後就爛了,但若換個名字或不設 id 就沒事。若沒有 version control,我想我在原本的程式裡找半天也不會找到,根本不會懷疑問題出在這裡。最後大概會重寫該段,然後莫明奇妙地避開這個問題。
和人合作時 version control 就更有用了,方便和其他人共用程式、做 code review、自動跑測試確保各版運作正常,好處不勝杖舉。相較於每個人各自寫程式,多個人同寫一份程式不但方便討論,容易互相支援,開發時士氣也會較好。每次看到別人 push code,就會覺得待做事項漸漸變少,而寫得更有勁。

Refactoring

在寫新功能或修 bug 前,若發現有重覆程式碼或一些有潛在風險的程式,先重構程式再回頭做原本該做的事。重構前記得要確保重構後行為不變。若情況太糟很難補 unit test 或是沒時間補太細,準備好幾組常用的輸入資料,記好它們對應的輸出結果,寫個自動測試的 recorded test 會比較安全,也可加快後續的重構。配合 VCS 做起來更容易,改改發現無法通過 recorded test,就 hg up -C 重頭改一次。然後別太貪心,一次改一點比較不容易犯錯。視情況寫 recorded test 的方式有所不同。通常我會用 shell script + diff 這類指令很快的拼一個可以用的小工具,重構完就丟了,節省準備 recorded test 的時間還有免除日後維護它的負擔。但若打算長久維護的話,自然是照規矩一步步做會比較穩當。

Unit test / Acceptance test / TDD

這部份在先前的文章已提了不少,隨著時間演進,實例愈來愈多。最近將 Django 1.1 昇到 1.2,跑 unit test OK, 但跑 Selenium test 時看到 CSRF 的錯誤訊息。稍微修一下,測試程式全過。讓我立即確信所有用到的 plugin 都順利地在 1.2 版下運作。
開始用 TDD 可說是我寫程式生涯中的重大里程碑,踏入完全不同的格局。讓我明白如何寫出易於長期發展的程式,不用像在玩踩地雷般辛苦。

Pair programming

這不算是個人習慣,順便記在這裡。
這部份我沒太多經驗,有時運作的不錯,有時不太順。執行 pair programming 前要先確保兩人的背景知識差不多,才不會有一人跟不上進度,讓另一人空轉。運作順利時,可以很快地完成較複雜的設計,並確保至少有兩個人可以繼續維護這份程式。而且程式也會較易懂:兩個人覺得好懂的程式,遠比一個人覺得好懂的程式易懂多了。
Pair programming 比寫下規範更容易讓大家有一致的開發習慣,像是 coding style 或是 commit 的規範。藉由一人帶一人的方式連結開發習慣。也方便分享實作技巧,像操作工具的技巧、使用函式庫的經驗或是寫程式的技巧。

其它

除養成好習慣外,偶而抽點時間學習工具的操作,像是 Linux 架站裝軟體之類的,開發軟體時很難避免這些事。像我習慣用 Linux terminal 開發程式,多熟悉 screen、bash、Vim 的設定和操作,開發速度可以快上不少。
最近的例子是使用 Firefox 的 plugin Firebug。以前改 CSS 都笨笨地存檔、重讀網頁,用 Firebug 讓我用十倍以上的速度完工,令人不勝噓唏。

結語

剩下的就是熟悉函式庫、框架,還有學會資訊工程一些基本知識,了解程式背後運作的原理。一但每個人都能保持寫程式的好習慣,團隊合作將會簡單許多,大家方便共用程式,方便互相支援 (寫相依的元件或除錯),既能加快開發速度,也會比較有趣。

2010年4月24日 星期六

百人百觀 (3)

原本我以為大部份問題有「標準答案」,而不斷地尋找每個問題的「標準解」。兩個人見解不同,必然有人有誤,也可能都不對。在《百人百觀》裡,我才明白不是這麼一回事:

最後我發覺沒什麼最正確、最有道理的事,百人百觀,於是我不會硬把自己的想法套到別人身上,當別人和我抱怨誰的想法不合理,大家都如何,他偏偏不合群,即使我贊同大部份人的看法,卻不會像以前一樣,認為那個特立獨行的人有問題,想說服他。

《百人百觀 (2)》裡,我才明白不該強加自己的觀念在別人身上,即使我認為自己沒錯,也要尊重別人的見解:

於是我不在意我是否能影響聽者的觀點,有的話,當然很高興;沒有的話,對方可能需要不同的契機來改變,那個契機不是我。也可能這個想法適用於我,不適用於對方。另一方面,我仍然熱於與人討論,百人百觀不意味交流沒有意義,只是不用過於執著自己的想法。

但是直到最近,我才明白自己的想法常常有誤,要能接受不同的看法,從中學習。這個轉變花了我不少時間。先是看了費曼的言論而開始懷疑一切、懷疑自己。我很喜歡他在《這個不科學的年代! 》第一篇裡說的話:

有些人說:「你怎麼能夠活著而無知?」我不知道他們是什麼意思。我從來都活著,也從來都很無知。那容易得很。我想知道的是你如何能什麼都知道。

後來又看了 TED Talk 《Weird, or just different?》,裡面有段話很棒:

Whatever brilliant ideas you have or hear, the opposite may also be true.

我原本對此半信半疑,經過幾次實例驗證,發覺我堅信「絕對沒錯」的作法,仍有一些情境不適用。若能從自己習慣的作法中找出反面的價值,或許會大有幫助。一但認定「肯定如此」後,就失去改進的機會了。

至於前兩篇文章對於溝通的焦慮,現在的心得是,要能開放心胸,站在對方的角度思考。嘗試幾次後,會發覺以前沒想到的事。再來就是去除情緒,就事論事。說來容易做來難,還在持續練習中。附帶一提,站在對方的角度思考並不容易,不只是情緒上的問題,有時沒類似的經驗,無法明白對方看重的點。

2010年4月11日 星期日

寫出容易測試的程式

昨天和何米特、卡曼德 (不要懷疑,他們都是道地的台灣人)聊到測試,想到一個不錯的例子。這回就用實例來說明「容易測試」和「不容易測試」到底是怎麼一回事。完整的程式可以從這裡取得。

題目說明

從參數列讀入一個網址,計算網頁內的單字數量並輸出到螢幕。單字之間用空白區隔。當網址無效時,輸出 -1。

為了方便說明起見,我選了個簡單但完整的例子。若要將問題變得更有說服力,不妨想像要連線到網頁伺服器,需要來回幾次的通訊和分析網頁內容以達成目的。比方說寫個程式下載漫畫或美女圖之類的。總之,程式愈複雜,下面提到的問題愈嚴重。

直覺的寫法

相信大家看到這題目都會覺得簡單嘛,這樣的程式有什麼難的,寫一寫、跑一跑、改一改,來回幾次就搞定了。寫出來的程式大概長這個樣子:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
import sys
import optparse
import urllib2
 
def main(url):
    '''\
    %prog [options] <url>
    Print the number of words in <url>.
    Print -1 if <url> is invalid.
    '''
    try:
        content = urllib2.urlopen(url).read()
        print sum(len(line.split()) for line in content.split('\n'))
    except urllib2.URLError, e:
        print -1
 
    return 0
 
if __name__ == '__main__':
    parser = optparse.OptionParser(usage=main.__doc__)
    options, args = parser.parse_args()
 
    if len(args) != 1:
        parser.print_help()
        sys.exit(1)
 
    sys.exit(main(*args))

看起來沒啥問題,但是我們要怎麼確定這份程式是對的?嗯,大概找幾個有效的網址、無效的網址,試一試,看看跑出來的數字對不對。或著專業一點,自己弄幾個簡單的網頁方便計算答案,連入自己的網頁,對看看有沒有算對字數。

可以想見,這個測試過程冗長乏味。之後若做些修改,像是規格改成「輸出的數字要四捨五入到百位」、「輸出全部的字和它的次數」,沒人想從頭重測一次所有情況。

這裡的問題是什麼?問題出在沒有做到自動測試。那就寫個 shell script 讀入一串網址依序執行並存下結果,人工確認結果無誤後,再將答案存起來。之後就執行 shell script 讀網址比對輸出。比方說像這樣:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#!/bin/bash
# usage: ./check.sh <prog>
function check() {
    python $1 $2 > t.txt
    read n < t.txt
    rm -f t.txt
 
    if [ $n -eq $3 ]; then
        echo "Pass."
    else
        echo "Fail."
        exit 1
    fi
}
 
check MY_PROG http://www.googel.com/ 257
check MY_PROG http://www.googel/ -1

雖然少了冗長的手動測試,上述的測試流程仍有幾個問題:

  • 無法保證測試結果一致。有可能連到的網站改變內容,或是剛好連不上,使得每次測試可能得到不同的結果 (即使 Google 不會斷線,它總會改變網頁內容吧)。那麼,測試失敗時,我們怎麼知道是測試過程有問題,還是被測試的程式有問題?
  • 測試費時。受到網路連線的限制,測試相當費時。使得我們不會改一小段程式就執行所有測試。若我們能寫一行程式就跑一次測試,馬上能明白是那裡改出問題。
  • 測試失敗無法直指錯誤的源頭。我們只知道連 A 網址沒得到預期結果,接著得進程式一步步看,輸出內部資訊才能慢慢找到寫錯的地方。
  • 不易準備測試資料。若想測空網頁、有一個字的網頁和有一堆字的網頁,就得準備三個檔案。

目前看來,上述的問題似乎不大。但若有上萬行程式和上百個測試案例,一個案例要跑一秒,加起來就變一百秒。其中又有一兩個偶而會測試失敗,造成每次跑完測試無法相信測試結果。即使測試結果沒有疑慮,當測試失敗時,要怎麼從上萬行程式中找出錯在那裡?

第二版:將計算字元數的部份獨立成函式

在第一版的程式裡,為了測試是否有算對字數,得準備多份網頁和網頁伺服器再透過 HTTP 讀入內文做測試。光看這麼長的描述就會發覺那裡有些不對勁。若將計算字數的部份獨立成一個函式,就能單獨測「無內文」、「只有一個字」、「有很多字」等情況:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def count_lines(lines):
    return sum(len(line.split()) for line in lines)
 
def main(url):
    '''\
    %prog [options] <url>
    Print the number of words in <url>.
    Print -1 if <url> is invalid.
    '''
    try:
        content = urllib2.urlopen(url).read()
        print count_lines(content.split('\n'))
    except urllib2.URLError, e:
        print -1
 
    return 0

獨立出函式後,就能直接測算字數的部份:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class CountLinesTest(unittest.TestCase):
    def testEmptyContent(self):
        actual = wc.count_lines([""])
        self.assertEqual(0, actual)
 
    def testAWord(self):
        actual = wc.count_lines(["camel"])
        self.assertEqual(1, actual)
 
    def testWords(self):
        actual = wc.count_lines(["a camel can fly"])
        self.assertEqual(4, actual)
 
    def testWordsWithSpaces(self):
        actual = wc.count_lines([" a camel can fly "])
        self.assertEqual(4, actual)
 
    def testWordsWithAdjacentSpaces(self):
        actual = wc.count_lines([" a camel  can \tfly "])
        self.assertEqual(4, actual)
 
    def testMultiLines(self):
        actual = wc.count_lines(["a", "b c", "d e f"])
        self.assertEqual(6, actual)

看來不壞,上面的單元測試可以確保算字數的部份是對的。若上面的測試失敗,也能明白錯在那段程式,又有精簡的輸出入範例協助除錯。並且,獨立出來的函式 (count_lines) 可供其它程式使用。

但是對整個程式來說,我們還是擺脫不了下列問題:

  • 無法保證測試結果一致。
  • 測試費時。

第三版:將網路連線的部份封裝成物件,並用「傳入」的方式使用它

問題出在 main() 直接用 urllib2.urlopen() 連上網路,若能在測試時替換成我們準備好的函式,就能確保測試結果一致,且減少網路連線的時間。也許有人會說,可以在測試前直接換掉 urllib2.urlopen。這是一個解法,但不建議這麼做,原因日後再說明。比較適當的作法如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Client(object):
    def get(self, url):
        return urllib2.urlopen(url).read()
 
def count_web_page(client, url):
    try:
        content = client.get(url)
    except urllib2.URLError, e:
        return -1
    return count_lines(content.split('\n'))
 
def main(url):
    '''\
    %prog [options] <url>
    Print the number of words in <url>.
    Print -1 if <url> is invalid.
    '''
    client = Client()
    print count_web_page(client, url)
    return 0

於是我們可以用 mock (我用 pymox) 準備假的 Client 反應出我們期望的網頁連線結果,輕易地測試正常連線和網址無效的情況:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class CountWebPageTest(unittest.TestCase):
    def testCountWebPage(self):
        # Prepare the fixture
        url = 'http://www.google.com/'
        client = mox.MockObject(wc.Client)
        client.get(url).AndReturn('<html> ... </html>')
        mox.Replay(client)
 
        # Run
        actual = wc.count_web_page(client, url)
 
        # Verify
        self.assertEqual(3, actual)
 
        mox.Verify(client)
 
    def testPageNotFound(self):
        # Prepare the fixture
        url = 'http://www.google/'
        client = mox.MockObject(wc.Client)
        client.get(url).AndRaise(urllib2.URLError("..."))
        mox.Replay(client)
 
        # Run
        actual = wc.count_web_page(client, url)
 
        # Verify
        self.assertEqual(-1, actual)
 
        mox.Verify(client)

回頭看原本的程式有那些改變:

  • 獨立出 Client 物件,用來封裝網路連線的操作。
  • 傳 client 給 count_web_page() ,而不是在 count_web_page() 內部 new 出 Client。

想想看,若沒有上述兩個改變,要怎麼滿足測試需求呢?該怎麼測試各種網路連線問題呢?這個問題觸及容易測試和不易測試程式的關鍵差異。

結語

就結論來說,一但在函式內直接用全域變數、全域函式或使用自己 new 的物件 X,就不容易測試之後的程式了,因為之後的程式邏輯受到 X 的影響,但測試程式又無法直接控制 X 的行為。當然我們無法完全避免這個情況,總會有全域函式、需要 new 物件。重點在於,我們能將程式隔離到什麼程度?有沒有留「後門」讓測試程式方便控制內部邏輯。

也許有人會懷疑為了測試而改變原本的寫法,是否有些本末倒置?不妨自己練習做個幾次,對照一下原本的寫法和修正後的寫法,用自己的經驗判斷:為測試而改變的結果,是否恰好讓程式變得更彈性、更易重用?

附帶一提,上面的範例碼是逆向寫出來的。我是先用 TDD 寫出最後的版本,再將拆開的東西塞回去 main,弄出「直覺的寫法」。習慣 TDD 後,會改變寫程式的思維。先寫測試有助於寫出易測的程式。

2010年4月5日 星期一

[譯文] 為什麼我們不好意思承認,我們不知道如何寫測試?

原文見:《Why are we embarrassed to admit that we don’t know how to write tests?》

前言

這篇帶給我很大的影響。對我來說,明白「可測性是最重要的」是一大里程碑。隨著經驗累積,了解得愈深,愈明白 Miško Hevery 寫得多有道理。就當我打算寫篇心得時,才發覺很容易變成用我的話重說 Miško Hevery 說過的東西,而且還很容易漏講。轉念一想,乾脆翻譯他的文章好了。二月底時徵得他的同意,沒想到一拖就拖了一個月半,真不好意思。

大家覺得那裡譯得不好或呈現方式不好,就直接反應出來 。透過 Buzz、Murmur、Plurk、Facebook 或在此留言都可。謝啦。

本文

Take your average developer and ask “do you know language/technology X?” None of us will feel any shame in admitting that we do not know X. After all there are so many languages, frameworks and technologies, how could you know them all? But what if X is writing testable code? Somehow we have trouble answering the question “do you know how to write tests?” Everyone says yes, whether or not we actually know it. It is as if there is some shame in admitting that you don’t know how to write tests.

找出你公司內一般水準的開發者並問他們「你會語言/技術 X嗎?」沒有人會為承認自己不懂 X 而感到不好意思。畢竟有太多程式語言、框架和技術,你怎麼可能全部都會?但若 X 是寫出能被測試的程式呢?不知為何,我們很難回答這個問題:「你會寫測試嗎?」不論我們是否真的懂,每個人都回答會。就如同承認自己不懂寫測試是件很不好意思的事。

Now I am not suggesting that people knowingly lie here, it is just that they think there is nothing to it. We think: I know how to write code, I think my code is pretty good, therefore my code is testable!

我不是暗示人們故意說謊,而是他們認為測試沒什麼大不了的。我們認為「我知道如何寫程式,我覺得我的程式相當不錯,因此程式是可以測試的!」

I personally think that we would do a lot better if we would recognize testability as a skill in its own right. And as such skills are not innate and take years of practice to develop. We could than treat it as any other skill and freely admit that we don’t know it. We could than do something about it. We could offer classes, or other materials to grow our developers, but instead we treat it like breathing. We think that any developer can write testable code.

我個人認為如果我們能意識到可測試性是一個獨立的技術,我們可以做得好多了。這種技術並不是天生就會的,需要經年累月的練習來培養。我們可以將它視為另一項技術並坦率地承認我們不會這項技術。於是我們就能對它做點事。我們能提供課程或其它教材來讓開發者成長,而不是將寫測試的技術視為如同呼吸的能力,好像任何開發者都會寫可以測試的程式。

It took me two years of writing tests first, where I had as much tests as production code, before I started to understand what is the difference between testable and hard to test code. Ask yourself, how long have you been writing tests? What percentage of the code you write is tests?

在我開始了解可測試的程式和難以測試的程式的差別前,我花了兩年的時間先寫測試。在這些程式裡,測試碼的量和產品碼一樣多。問問你自己,你持續寫測試多久了?在你寫的程式裡,測試碼占了百分之多少?

Here is a question which you can ask to prove my point: “How do you write hard to test code?” I like to ask this question in interviews and most of the time I get silence. Sometimes I get people to say, make things private. Well if visibility is your only problem, I have a RegExp for you which will solve all of your problems. The truth is a lot more complicated, the code is hard to test doe to its structure, not doe to its naming conventions or visibility. Do you know the answer?

你可以問這個問題來證明我的觀點:「你如何寫出難以測試的程式?」我喜歡在面試時問這個問題,多數的時候我得到沉默的回應。有時有人回答「隱藏物件」。嗯,如果物件的可見範圍是唯一的問題,我可以給你一個正規表示式讓你解決這問題(譯者注:我猜是在測試程式前先用字串比對把程式內所有 private 換成 public,那就可以測了)。真正的答案複雜許多,是因為程式的結構造成它難以測試,而不是命名習慣或物件的可見範圍。你知道答案嗎?

We all start at the same place. When I first heard about testing I immediately thought about writing a framework which will pretend to be a user so that I can put the app through its paces. It is only natural to thing this way. This kind of tests are called end-to-end-tests (or scenario or large tests), and they should be the last kind of tests which you write not the first thing you think of. End-to-end-tests are great for locating wiring bugs but are pretty bad at locating logical bugs. And most of your mistakes are in logical bugs, those are the hard ones to find. I find it a bit amusing that to fight buggy code we write even more complex framework which will pretends to be the user, so now we have even more code to test.

一開始我們都是一樣的。當我第一次聽到測試時,我立即想到寫一個框架來假裝使用者,使得我能用它來執行被測的應用程式。很自然會這麼想。這類型的測試被稱為使用者端測試(end-to-end-tests)(或是情境測試、大型測試),它們應該是你最後寫的測試,而不是一開始想到的。使用者端測試很適合找出 wiring bugs(譯者注:不知該怎麼翻,請參見 wiring bug 連結的說明),但不適合找出邏輯錯誤。並且,你的多數錯誤會是邏輯錯誤,它們才是難以找到的錯誤。我發覺這有些有趣,為了對抗有錯誤的程式我們卻寫了更複雜的框架來假裝使用者,於是我們有更多程式待測。

Everyone is in search of some magic test framework, technology, the know-how, which will solve the testing woes. Well I have news for you: there is no such thing. The secret in tests is in writing testable code, not in knowing some magic on testing side. And it certainly is not in some company which will sell you some test automation framework. Let me make this super clear: The secret in testing is in writing testable-code! You need to go after your developers not your test-organization.

每個人都在尋找解決測試麻煩的神奇測試框架、技術、知識。然而我有個消息要告訴你:沒有這種東西。測試的祕訣就是寫出能被測試的程式碼,而不是明白測試領域中某種魔法。並且大概不會有某家公司賣你某種自動測試框架。讓我說得更清楚一些:測試的祕訣就是寫出能被測試的程式碼!你需要關注你的開發者而不是你的測試組織。

Now lets think about this. Most organizations have developers which write code and than a test organization to test it. So let me make sure I understand. There is a group of people which write untestable code and a group which desperately tries to put tests around the untestable code. (Oh and test-group is not allowed to change the production code.) The developers are where the mistakes are made, and testers are the ones who feel the pain. Do you think that the developers have any incentive to change their behavior if they don’t feel the pain of their mistakes? Can the test-organization be effective if they can’t change the production code?

現在讓我們想想這點。大部份的組織讓開發者寫程式,接著讓一個測試組織來測試。讓我確保我明白這是怎麼回事,有組人馬寫出無法測試的程式,和另一組人馬分頭試著測試這些無法測試的程式(喔,而且測試小組不被允許改變產品碼)。開發者是錯誤的來源,測試者感受這些痛苦。你認為有任何誘因讓開發者改變他們的行為 — 如果他們沒有為他們製造的錯誤而感到痛苦?在不能改變產品碼的情況下,測試組織能夠有效地作事嗎?

It is so easy to hide behind a “framework” which needs to be built/bought and things will be better. But the root cause is the untestable code, and until we learn to admit that we don’t know how to write testable code, nothing is going to change…

躲在能建造/買來的框架後面是很容易的,事情也會改善。但是問題的根源是無法測試的程式,直到我們學會承認我們不懂如何寫出能被測試的程式,情況不會改變的...。

相關閱讀

2010年4月1日 星期四

我們不能改變手裡的牌,但是可以決定如何出牌。

在愚人節發文章好像怪怪的,搞不好會被人誤以為在說反話。

我很喜歡 Randy 說的這段話:

我們不能改變手裡的牌,但是可以決定如何出牌。

了解自己能改變什麼、不能改變什麼,專注在自己能影響的範圍裡,就沒什麼需要煩惱的事了。

2010年3月1日 星期一

我學 Machine Learning 的方法

有人問我這個問題,想說就寫在這吧。目前還學不到家,只有斷斷續續讀個一陣子,有錯還請大家指正。

讀 Data mining 的書

一開始我讀 data mining 之類的課本、講義,發現內容講得滿概念的。但若只是想拿 ML 來用,那看這類文件會比較容易上手。比方 Introduction to Data Mining 寫得挺不錯的,可謂深入淺出!官網附的投影片挺棒的,可以先「快速」 (相對於看書來說……) 看一遍,再挑有興趣的部份閱讀課本。若有耐性慢慢讀完課本,會較有系統性地認識相關內容。由於碩論做 clustering 的緣故,我有好好地讀書本 clustering 部份。不過 clustering 論文種類多到爆炸,看完這本的內容也只是苦痛的開始而已……。

讀國外大學的授課講義

若想進一步了解 model 的原理,那就需要讀 ML 課程用的課本和講義。這類文件滿多的,其中我強力推薦 Andrew Ng 教的 Stanford CS229 Machine Learning。大部份教材在講解 model 最關鍵的數學時,只會從天空掉下來一句「套用 gradient ascending 求最大值」、「運用 EM 求最佳值」之類的話,接著結果就神奇地飛出來。這份講義卻從最基礎的數學開始講,包含需要用到的微分、線性代數、機率等,讓讀者有能力自己從頭推導數學算式,算是 ML 文件裡最親切的教材。當然,讀者也要有興趣慢慢地啃才行。我大概啃了一半多一點內容,收獲良多。可惜久一沒用也只記得概念了。有機會想再從頭自己推導一次。我覺得 Andrew Ng 數學寫得相當漂亮,這是我第一次察覺寫數學式和寫程式一樣,也有美醜、易懂難懂之分。附帶一提,當初會看這份教材是看 Mr. Saturday 推薦才讀的,感謝 Mr. Saturday 推薦。

後來我陸續看了一些不同國外大學的 ML 課程講義,發覺大家的切入點差很多,各有不同考量。像 MIT OCR 6.867 Machine Learning 有教 HMM,Stanford CS229 沒教。A Fundamentalist Organization of Machine Learning 提到由 Learning theory 的方式切入 ML,而不要走馬看花講一堆 model (作者稱為 “zoo approach”,挺傳神的譬喻)。我只有從 Andrew Ng 的講義裡讀了一點 learning theory,懂些基本觀念 (bias 和 variance),感覺挺有用的。若對 learning to theory 有興趣,印象中該文作者有推薦 15-859(B) Machine Learning Theory,Spring 2009。我看了一晚講義,內容是從簡單的假設環境中推導出明確的性質,還挺有趣的。但看到後來就看不懂了,也不明白能做什麼,就沒繼續看了。

讀 Wikipedia

此外,我發覺 Wikipedia 是學東西的好地方。有代表性的方法早已有系統地記錄下來,又提供詳細的參考資料可以一路讀下去。比方說想學 Linear classifier ,比起查書,查 Wikipedia 更有效率。我常拿 Wikipedia 內容和其它文件交叉對照,弄明白看不懂的部份。讀這些東西需要的是耐心以及不傷眼的 Wikipedia CSS 樣版

讀經典課本

後來又看到 Mr. Saturday 提到 Elements of Statistical Learning: data mining,inference,and prediction. 2nd Edition.,而且官網還有附完整電子書,就載來看看。不得不說這本書數學超硬,但內容超級紮實,相當值得一讀。我挑有興趣且讀得下去的部份加減看,學到 bagging、random forest 等東西,讓我擴展眼界,明白許多原理。除數學太硬之外,這本書另一問題是實驗資料太小了,令人懷疑實驗結果是否適用於真實世界的情況。只好先暫時相信大師,之後再從實驗中確認。

有興趣的話可以在 Amazon 查一下其它書,或以這本書為底看相關書籍。ML 有不少經典書籍,也有針對影像處理或文字處理的。

其它

O’Reilly 出的 Programming Collective Intelligence - O’Reilly Media 也是不錯的書,適合初學者閱讀。配合使用情境,作者簡單地解釋 model 的概念並用 Python 說明如何實作。最令人讚賞的是,作者還有比較各個模型的優缺點。雖然分析的內容不見得正確,對初學者來說挺受用的。

總結

讀這些理論時,我發覺有許多文件提供不同的講解方式,可以多比較一番,找自己看得懂的。不用刻意從某個地方學會某種 model。文中提的是我學習的歷程,每個人的需求不同,數學底也不同,我的經驗不見得適用於其他人。寫在這裡供大家做個參考,有錯還請告知,感謝。

2010年2月10日 星期三

觀察實驗資料和畫圖表的小技巧

之前在《減少操作實驗浪費的時間》提到一些做實驗的小技巧,方便自動化重覆實驗、觀察結果和產生圖表。最近實驗做得比以前更多,意外發覺更好用的方式 。有需求就會進步,這是工程師的宿命啊!

主要的改變有三點:

  • 用 Python 寫程式執行實驗。Python 功能比 shell script 強上不少,也方便維護和增加功能。「Can I use Python as a bash replacement?」提到這樣做的好處和簡單的實施要點。什麼?你看了上篇文章發現我好像用 Ruby 較多?這...總之我跳槽了。男子漢做事,有時是不需要理由的!
  • 改用 SQLite 當資料庫。使用 local database 至少有兩個好處:每次實驗都重建一個新資料庫,方便保留不同實驗結果;少掉煩人的設定,可以更彈性地使用。實驗後可以用 sqlite3 看內容,或另寫程式下 SQL 彙整結果。若有架 Wiki,直接將結果輸出成 Wiki code 也不壞,容易加上顏色、粗體和表格。
  • matplotlib 畫圖。matplotlib 是一套 Python 繪圖函式庫,能畫長方圖、折線圖、直方圖等多種類型圖片。更重要的是,它畫得還挺不賴的 (見官網範例)!既可以在 matplotlib 內建的應用程式裡看結果,也能存成 PNG 檔。依我個人過去用 gnuplot 的經驗,matplotlib 好用許多。不過這可能取決於使用者有多熟悉 Python。若你也喜歡用 Python,matplotlib 無疑是最好的選擇。「Tools I use: matplotlib」提出相似的見解,有興趣的人可以參考看看。

不論是 SQLite 還是 matplotlib 都有嚇死人詳細的文件,配合範例程式學起來挺輕鬆的。目前唯一的不便之處是,當實驗數據更多時,有時只想看部份東西,再一步步看不同層面。若一口氣把全部資料畫成圖表,不容易閱讀。有空時想來研究看看 Django (殺雞用牛刀嗎?),看能不能寫個簡單網頁,做為互動呈現數據的介面。反正資料存在 SQLite 裡,容易用各種方式存取資料。

2010年2月5日 星期五

學 Python 的入門書

常看到有人問這問題,想說來寫篇心得,省得重覆回一樣的問題。

我在學 Python 前已學過別的程式語言,所以想找針對已學過程式的人的書。一開始翻許多人推薦的《Learning Python》,發現它是針對沒學過程式的人,有太多篇幅在介紹基本觀念 (如 if 是什麼 ),翻沒幾頁就沒耐性看下去。而《Programming Python》又太厚了,於是找別本書。

後來 Scott 推薦我看《Python Essential Reference》 (目前出到第四版,包含 Python 2.6 的新功能),我一看就驚為天人,「if、elif、else」只有一頁!內容包含完整語法,以及特殊情況 ( 若 if 之後想放空的 statement ,要用 pass )。沒錯,這就是我要的書,去蕪存菁地讓讀者立即掌握 Python 的語法。附帶一提,Scott 明明已學會了,竟然還買了一本用來傳教,真是面惡心善的好學長。

看完這本後,有時查些 Python 觀念或函式名稱,發現常連到《Dive into Python》,才發覺這本也滿有名的,而且還有完整免費的網頁版。於是又找時間看了《Dive into Python 3》,順便了解 Python 3 有啥有趣的東西。發覺這本書超合我胃口,直接用完整的例子說明語法,在學到語法的同時,也明白怎麼實際使用這些語法。有些書就像辭典一般,提了很正式的語法,讀起來很累,讀完卻不知能怎麼用它們。《Dive into Python 3》不但用生動的實例避免這個問題,並進一步深入淺出地介紹運作細節。而且還提到如重構、單元測試等寫軟體的重要觀念,又有詳細的 Python 2 和 3 的比較。若只對 Python 2 有興趣也沒關係,大部份語法仍適用於 Python 2.6 (2.6 是承接 Python 2 和 3 的橋樑)。

總結來說,若你沒學過程式語言,我不知道能推薦什麼書藉。或許可以參考《Python Programming: An Introduction to Computer Science》,這是 MIT 6.00: Introduction to Computer Science and Programming 的參考書,該課程用 Python 教沒寫過程式的學生學會電腦科學家的思考方式。若有學過程式語言,《Python Essential Reference》或《Dive into Python 3》都值得一看。除了學會 Python 之外,兩者提供不同的額外內容,都看也不會浪費時間。

延伸閱讀

學會 Python 基本語法後,可以先看這幾篇了解如何寫出更道地的 Python。道地的 Python 程式不但易讀、易維護,通常也表示更有效率:

再來,可以到《Python Essential Reference》作者 David Beazley 的網站挖寶,像是:

另外若對 design patterns 有興趣,可以看 Google 員工 Joe Gregorio 寫的 (The Lack of) Design Patterns in Python

《Python Cookbook》也有不少經典寫法,不過該書有點舊了 (到 Python 2.4),有些方法已用不到,看的時候要挑一下。

原以為延伸閱讀應該沒多少東西,沒想到我拉拉雜雜也看了不少文件,整理到後來就累了。不知何時 Python 才會像 Java 有本《Effective Python》,一本搞定大部份的注意事項和經典寫法。

備註:設定開發環境

詳見《學習和開發 Python 的好幫手》

2010年1月31日 星期日

專利,就是科技競爭力

書籍基本資料:專利,就是科技競爭力

這年頭專利盛行,雖說專利申請書是專利工程師在寫,多少懂些專利知識,才能明白何謂專利,想出有用 (防範侵權或授權獲利) 的專利。這本書用白話的方式配合舉例,說明專利是什麼。藉由許多正反例子,幫我釐清不少觀念,總算有種「我好像有點明白專利」的感覺。以下為一些散亂的筆記。

專利的觀念澄清

專利的目的是鼓勵發明,保護發明人的權利。像寫作、程式碼屬於著作權,完成的當下作者就擁有著作權。然而,其他人只要寫法不同,即使概念和我的作法完全一樣,也不會侵犯到著作權。專利則是保護發明人的概念。以最近當紅的 MapReduce 來說,Hadoop 沒用到 Google 的原始碼,所以沒侵犯到 Google 的著作權,但是由於 Google 已申請到 MapReduce 的專利,Hadoop 就侵犯到 Google 的專利權 (Google 要不要告 Hadoop 是另一回事啦)。

但也不是光提概念就能申請專利,比方說申請「讓人類飛在空中」就不會通過,除提出概念外,至少還有提及一種實現方法。不過專利的重點是保護概念,而非實現方法。但這也得看專利的寫法,其他人可能以不同的實現方式迴避專利。我還沒搞清楚這部份差異。

閱讀專利書時,最重要的部份是申請專利範圍 (claim),其它部份只是交代相關知識,並無法律效果。

專利訴訟時會以專利範圍去比對侵權產品,比方說專利 A 包含 A1、A2 兩個元件,產品 B 包含 A1、B2,那麼產品 B 就沒有侵權。若產品 C 包含 A1、A2、C3,那產品 C 有侵權。用數學式來表示就是:

if A ^ B == A, then
B 侵犯到 A 專利
else
無侵權

若從字意上的解讀無法看出 B 包含 A 的專利範圍,可進一步做推論,判斷兩者是否有同意的詞。書中以鐵槌為例,若專利 A 和產品 B 只差在 A 用拉環來掛鐵槌,B 用挖洞。這就看法官是否認為這兩者是同樣的概念。

專利範圍的條件愈多,範圍愈小。所以若有兩個限制 A1、A2,若能拆開各別申請,效果會更好,但也會比較難申請。

由以上的描述可知,專利說明書的品質相當重要。現今廣為使用在滑鼠的滾輪,並不是第一個發明滾輪的人。在那之前也有人申請專利,只是他聲言的專利範圍除「輔助操作件」 (比方滾輪) 外,還多提到「彈性元件」,所以後來為滾輪申請專利就沒有侵權。

即使申請到專利 A,也不見得可以行使專利 A。比方說專利 A 包含 A1、A2 兩點,但可能 A1、A2 各有一個專利,於是要行使專利 A 的話,還得先和 A1、A2 的所有人購買專利權。

那些項目可以申請專利?

去除是否能獲利,申請專利其實是很簡單的事,只要滿足專利三要素即可

  1. 有用性:提出對發明人而言有用的理由即可,比方「狗手錶」聲稱給狗帶的手錶,實際上就是快七倍時間的手錶。申請人聲稱這可讓狗的主人明白狗的生命短暫,更珍惜狗。
  2. 新穎性:過去全世界文獻 (通常是索引專利資料庫) 中沒有出現過的方法。除不重要的細節外,只要有一絲不同,就有新穎性。所以有時即使是相當直覺的東西,沒有文獻就無法退回申請。另外若審查官懶得看他國的專利資料庫,也可能發生日本已有案例,卻仍在台灣申請成功。但這樣的專利也可能無用,事後若有人發現這點,可申請專利無效 (打官司時對手最常幹的事)。
  3. 進步性 (非顯而易見性):新穎性是一對一比方,而進步性是拿過去多件作品和目前的申請比對。申請人要證明過去任何方法都無法組出申請方法能達到的效果。那怕是 90% 的效果變成 90.1%,都可以申請。只要該領域的技術人士無法輕易想出你的作法,就有非顯而易見性。為免事後諸葛,審查時會比較寬鬆。進步性也不是非要「進步」不可,重點是「非顯而易見」。有許多高爾夫球專利,差別在於表面的洞有不同排列方式。到底有沒有飛得比較遠?那不是重點,只要不是「輕易」想到即可。

比方說現在已有電視這種東西,只要隨便把電視和另一個不相干的東西組在一起,就能機會申請專利。像是兼具暖爐功能的電視、能養魚的電視等。雖然拆開來看都是習以為常的產品,合起來卻是「沒有人想過」的概念 (無文獻記載)。書中舉了許多有趣的例子,像是避免忘了帶筆,把筆放在鑰匙圈裡、放在手錶裡、放在項鍊裡都被申請成專利。

新用途可以申請專利,像是阿司匹林原本是感冒藥,卻發現也有防治心血管疾病效果。後來這個新用途就被申請成專利。

雖然數學公式無法申請專利,使用數學的應用方式卻可以。所以無法申請傅立葉轉換,但可以申請「讀入一串資料,做傅立葉轉換,接著輸出」。可以歸可以,會不會過是另一回事 (比方說已有論文或書籍提及這種作法,那就不具新穎性了)。

軟體也可以申請專利,像美國賭場的吃角子老虎,以前是各台單獨累積獎金。有人提出讓全部機器連線,統一累積獎金,並用軟體控制產生的結果,確保中獎機率不會過高。這人有成功地申請專利,後來賣給賭場。還有像 Yahoo 也有申請到個人化網頁的專利:Dynamic page generator

An custom page server is provided with user preferences organized into templates stored in compact data structures and the live data used to fill the templates stored local to the page server which is handing user requests for custom pages. One process is executed on the page server for every…

注意,這裡保護的重點仍是概念,不是程式碼。一個大型軟體專案包含許多概念,可能會抽出其中幾點符合專利三要素的元件來申請專利,而不會申請整個軟體專案。作者以 e-mail 系統舉的例子滿不錯的,一個新的 e-mail 系統包含更好的編輯器和更好的偵測機制,編輯器和 Word 相比可能不具進步性 (使用者可以用 Word 編好內容,再用貼到舊的 e-mail 編輯器),然而偵測垃圾郵件的機制可能有進步性。

原本我也挺反對軟體專利 (應該說我還沒搞懂它的含蓋範圍,萬一 design pattern 被專利了,會發生什麼事?),不過作者舉的一些例子也滿有道理的,像是支援附加功能的傳真機,附加功能可能是傳真結束後輸出一張紙表示上個操作有無成功。這不需更新硬體即可達成,是很有用的功能 (現今有電子螢幕就不需要啦)。若沒有軟體專利,競爭對手即可抄走這個概念,違反了專利保護發明人概念的原意。

2010年1月5日 星期二

Python 加速的方法

這一年來用 Python 開發滿爽的,用久後發覺 Python 真的是不夠快啊。雖說這就是 trade-off,拿 CPU 執行時間換工程師開發的時間,但關鍵時刻跑得不夠快,還是得投入時間研究如何加速。程式開發就是一連串的 trade-off,人生也是如此啊!…………………還是少嘴炮,切入正題吧。

用 Profiling 測全體執行時間

去除演算法、資料結構的問題外 (像是 O(N log(N)) vs. O(N^2) 的方法 ),千萬別自己亂猜效能瓶頸就一頭熱地改程式。隨便想想都能舉出一堆自以為聰明的反例。我印象最深的經驗是,有一次我在寫資料結構作業答案,題目是實作 hash table 來統計文章裡單字出現的次數,身為課程助教,程式當然不能跑得太慢啊。所以調了一下效能,結果發覺改了一些演算法 (如 hash table 的 「chain」用 binary tree 而不用 linked-list ),卻沒快多少 (變慢是常有的事),一用 profiler 量,卻發現 1/3 的時間花在把一行文字切成單字上。我原本用 Java 的 split 一次切完回傳一個 List,改用 StringTokenizer 後就省下整體 1/3 的時間。

Python 有內建 profiling 的工具,叫做 profile,可以透過命令列直接下參數使用:

1
python -m cProfile -s time MODULE.py ARGUMENTS

這樣會執行 MODULE 再將測量結果輸出到螢幕,時間依單一函式執行時間來排序。引用官網的例子,cProfile 的輸出格式如下:

1
2
3
4
5
6
7
8
     2706 function calls (2004 primitive calls) in 4.504 CPU seconds
 
Ordered by: standard name
 
ncalls  tottime  percall  cumtime  percall filename:lineno(function)
    2    0.006    0.003    0.953    0.477 pobject.py:75(save_objects)
 43/3    0.533    0.012    0.749    0.250 pobject.py:99(evaluate)
 ...

前面的 tottime 是該函式自己執行的時間;後面的 cumtime 則是該函式整體 (包含它呼叫其它函式) 的執行時間。

附帶一提,以前試 Java profiling 工具時,執行速度會慢個數倍,但用 Python 的 cProfile 卻只變成一倍多慢而已,也可能我那時用的 Java 工具太糟,或參數沒設好吧。

用 timeit 來量單一 expression 的速度

timeit 也是內建模組,也可以用命令列執行:

1
python -m timeit EXPRESSION

下面是執行的例子:

1
2
3
4
5
$ python -m  timeit 'range(10)'
1000000 loops, best of 3: 0.3 usec per loop
 
$ python -m  timeit 'xrange(10)'
10000000 loops, best of 3: 0.166 usec per loop

我比較常寫程式來測 timeit,透過命令列執行 expression 相當受限,還是自己寫段程式包成函式後,再用 timeit 執行較方便。附上一個例子:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#!/usr/bin/env python
# Count numbers in a list.
# Demonstrate built-in functions' efficiency.
 
import timeit
import random
 
# prepare test data
numbers = range(2)
a = []
for n in numbers:
   a += [n] * 10000
random.shuffle(a)
 
def test():
   c = {}
   for x in a:
       c[x] = c.get(x, 0) + 1
 
def test2():
   c = {}
   for n in numbers:
       c[n] = 0
   for x in a:
       c[x] += 1
 
def test3():
   c = {}
   for n in numbers:
       c[n] = a.count(n)
 
 
if __name__=='__main__':
   t = timeit.Timer("test()", "from __main__ import test")
   print 'test', t.timeit(number=1000)
 
   t = timeit.Timer("test2()", "from __main__ import test2")
   print 'test2', t.timeit(number=1000)
 
   t = timeit.Timer("test3()", "from __main__ import test3")
   print 'test3', t.timeit(number=1000)

有興趣的人可以猜猜看那個方法最快 [1]。

找出瓶頸後加速的方法

用 profiling 找出瓶頸後,大概有幾種作法:

  • multiprocessing 平行化:這年頭 CPU 不用錢,隨便買都是 multi-core。若程式可以單純平行化,這個作法比用 C/C++ 方便一些,至少還是在寫 python code。但若程式稍微複雜,寫起來會很辛苦,且容易因 fork 或 lock 的 overhead 而沒快多少。
  • 將 CPU bound 的地方透過 ctypes 改寫成 C/C++:雖說 ctypes 很好用,不過寫 C/C++ 得注意的事比寫 Python 多太多了,所以我滿少這麼幹的。
  • 從 Python interpreter 下手,改用較快的寫法:這個作法需要一些 Python 運作的知識,才知道怎麼改會比較快。比方若不需用到整個 list 可以改用 generator 減少產生 list 的時間、使用 member field 存取資料以減少 function call、改用 built-in 函式組出要做的事 (如上面附的例子)。這時 timeit 就很好用了,可以先測好關鍵部份,減少重跑整個 profiling 的時間。

不勞而獲的加速方法

我只有偶而注意相關消息,還沒試過,只知道各家方法有些不適用的問題,這裡記些關鍵字。

Psyco 是老字號工具,大家都說讚,對數值運算特別有效,但它只支援 32-bit CPU,作者目前在開發 PyPy。另外 Google 開發的 unladen-swallow 也令人期待。也許在不久的將來,兩邊都會有足以實用的成果吧。

延伸閱讀

Victor 告知,Python 官方 Wiki 有幾篇超棒的文件,相當值得一看:

備註

  1. 這是我執行出來的數據:
    1
    2
    3
    
    test 5.41639614105
    test2 2.70715403557
    test3 0.619280815125

    即使走訪 list 兩次,方法三還是比前兩個方法 (只走訪一次) 快上不少,這是因為方法三用 C 實作的程式走訪迴圈,而前兩個方法用到 Python 的迴圈。