fcamel's blog

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 的好幫手》。

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 的所有人購買專利權。

那些項目可以申請專利？

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

有用性：提出對發明人而言有用的理由即可，比方「狗手錶」聲稱給狗帶的手錶，實際上就是快七倍時間的手錶。申請人聲稱這可讓狗的主人明白狗的生命短暫，更珍惜狗。
新穎性：過去全世界文獻 (通常是索引專利資料庫) 中沒有出現過的方法。除不重要的細節外，只要有一絲不同，就有新穎性。所以有時即使是相當直覺的東西，沒有文獻就無法退回申請。另外若審查官懶得看他國的專利資料庫，也可能發生日本已有案例，卻仍在台灣申請成功。但這樣的專利也可能無用，事後若有人發現這點，可申請專利無效 (打官司時對手最常幹的事)。
進步性 (非顯而易見性)：新穎性是一對一比方，而進步性是拿過去多件作品和目前的申請比對。申請人要證明過去任何方法都無法組出申請方法能達到的效果。那怕是 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 的輸出格式如下：

     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

下面是執行的例子：

$ 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 執行較方便。附上一個例子：

#!/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 2 3
test 5.41639614105 test2 2.70715403557 test3 0.619280815125
即使走訪 list 兩次，方法三還是比前兩個方法 (只走訪一次) 快上不少，這是因為方法三用 C 實作的程式走訪迴圈，而前兩個方法用到 Python 的迴圈。

訂閱：文章 (Atom)

2010年4月5日 星期一

前言

本文

相關閱讀

2010年4月1日 星期四

2010年3月1日 星期一

讀 Data mining 的書

讀國外大學的授課講義

讀 Wikipedia

讀經典課本

其它

總結

2010年2月10日 星期三

2010年2月5日 星期五

延伸閱讀

備註：設定開發環境

2010年1月31日 星期日

專利的觀念澄清

那些項目可以申請專利？

2010年1月5日 星期二

用 Profiling 測全體執行時間

用 timeit 來量單一 expression 的速度

找出瓶頸後加速的方法

不勞而獲的加速方法

延伸閱讀

備註

2010年4月5日星期一

2010年4月1日星期四

2010年3月1日星期一

2010年2月10日星期三

2010年2月5日星期五

2010年1月31日星期日

2010年1月5日星期二