他們是我們的孩子！

昨天晚上聽到學生攻佔行政院時，整個心揪在一起，直覺告訴我會出事了。即使今天8點多就要開會，也睡不著，我不知道有沒有我的學生或教過的學生。

當過我的學生都應該知道我「從不」 對他們談政治，因為我實在對藍綠的紛爭，政治的黑暗沒興趣。但當我看到電視畫面，棍棒打到學生的時候，實在很痛，就像是打到我小孩一樣，實在不能再沉默。

以前是藍綠紛爭，然而現在卻是世代的紛爭，世代的正義。我們有沒有善待下一代，我們有沒有想留給下一代甚麼？

我們在學校上課，不就是希望我們的下一代成長，比我們好？我們教他們要獨立思考，勇於問題，打破砂鍋問到底。(我還怕台灣學生過於內向不敢問題，還常常要求每位同學一定要發言。)

可是當學生問一堆問題時，不是持續政令宣導，就是沒有針對問題回答，這怎麼會讓學生服氣。

我們留給下個世代甚麼？

我們這個世代，有想過我們到底要留給年輕世代甚麼東西嗎？有將他們看成自己的孩子嗎？我相信我們這一輩很多人一定有個共同的記憶，那就是：我們的長輩們辛苦一輩子，即使賺了一些錢，還是省吃儉用，留給後代，能力所及的還要幫子女們留一棟房子，這是因為他們以前苦過，希望留給子女有更美好的未來。

那麼再看看我們怎麼對待我們的下一代：

從齊柏林的「看見台灣」，看到我們帶給年輕世代的竟然是一堆汙染的環境，給他們收拾。
當全世界都確定無法處理核廢料的時候，我們也還是留給他們這些「資產」去收拾。
還奉送一個快要破產的勞退保，讓他們承受。
洪仲秋冤死，到現在還不知道真相！
。。。

若我們真的把我們的下一代看成是我們的小孩子，會這麼作嗎？

下一代已經很恐慌了，還說可以到大陸拿50K以上。就算沒有把下一代看成是自己的小孩子，至少請也好好告訴下一代，要留給他們甚麼？

「Coding」與「創意」: 別把賣弄當創意

「創意」是很重要的一件事, 但在 coding 或軟體發展, 過度的濫用常常是適得其反. 最近看到一篇有趣的文章, 讓我想寫這篇來與大家分享一些看法.

該文提到一個面試的題目 (詳見原文), 最後一個 "台灣面談者" 的解法頗具創意, 時間複雜度"理論上"也不差. 但我的comment是: 若我是軟體部門的主管, 除非這位仁兄有分析或解釋在何種場合要如此做, 我不會雇用這位仁兄. 理由是: 縱然這解法有趣有創意, 但有overflow的問題, 且更重要的是程式比較難看懂難維護.

類似地, 以前上課時常舉的例子: 有一家公司對應徵者, 常會考一個簡單的基本問題: SWAP(x,y), 將變數值 x,y 交換. 一位面談者的答案是: x ^= y ^= x ^= y; 可以省下一個記憶空間, 很有創意吧! 但那公司後來決定不雇用他. 原因是: 這解法還是有潛在問題(e.g., SWAP(x,x)), 且這樣的軟體很難維護.

好, 這時你可能會質疑我: 我們不是都在鼓勵有創意嗎? 你是教授, 反而要抹煞創意.

我的回答是: 我同意「創意」很重要, 但更重要的是要分析這個「創意」在整個軟體是否達到特定的成效; 在程式中, 有簡明的做法, 反而用更複雜難懂的技巧且無較好的效果, 這樣的創意是沒太大意義的.

試想當一個人維護程式時, 看到 "x ^= y ^= x ^= y;" 是否要多花個上分鐘來檢視這是否正確. 你可能認為這只是幾分鐘而已, 但一個程式裡, 若有好幾個類似的寫法, 維護程式就得多了好幾倍時間, 這對軟體發展及維護都是很嚴重的情形.

當然若你清楚會有產生效果時, 那當然另當別論. 例如, 我聽說我一位學生到一家很賺錢公司面談, 面談官問了一個題目: 寫 bitcount: 將一個整數中, 含有1的位元加總起來, 這是假設CPU沒有這樣指令. 原來的面談官應該只期望回答簡單的 a loop with "shift 1 bit" and "test LSB". 但我學生就立即回答我們 computer game 常用的快速作法:

    int Bitcount(unsigned long long b)
    {
        b = ( b & 0x5555555555555555 )
            + ( ( b >> 1 ) & 0x5555555555555555 );
        b = ( b & 0x3333333333333333 ) 
            + ( ( b >> 2 ) & 0x3333333333333333 );
        return ((( b + (b >> 4) ) & 0x0f0f0f0f0f0f0f0f ) 
            * 0x0101010101010101 ) >> 56;
    }

有趣的是反而把面談官考倒, 讓面談官想了好幾分鐘.

從速度的角度, 這是很好的答案, 但更重要的是要分析在何種場合用何種做法. 若速度要求很低時, 這寫法反而不見得好, 有可能增加維護上的負擔.

因此, 我常在上課時告誡同學, 好的程式工程師, 不只是要很會寫程式及會很多演算法, 更重要的是會分析. 例如, 要建一個 data structure 做資料搜尋 (假設沒有library可用). 最簡單的是 linear search on array, 但大家都知道有很多問題, 當資料量大時很耗時, 且大小的彈性不好. 較進階的有 red-black tree, b-tree, hash table 等, 但開發時間較久. 好的軟體工程師, 就要能分析給主管, 若明天就要一個簡易測試版, 就用 linear array, 以後再來改寫更精緻的資料結構. 若他為了賣弄他在演算法學到的技巧, 一味地就用進階的做法, 很可能搞了幾天幾周都還未必好, 且影響軟體開發.

結論是: 軟體設計更重要是在於分析, 千萬不要賣弄技巧, 除非你知道你在做甚麼.

A Simple and Interesting Solution for Bucket Sort in a Circle

One of my students in my Algorithm class gave a simple and interesting answer to an exercise of the textbook "Introduction to Algorithms" (3rd ed.), much different from most solutions given in the Internet. The exercise is 8.4-4 as follows:

"We are given n points in the unit circle, pi = (xi, yi), such that for i = 1, 2, . . ., n, such that 0<x1^2 + y1^2<=1. Suppose that the points are uniformly distributed; that is, the probability of finding a point in any region of the circle is proportional to the area of that region. Design an algorithm with an average-case running time of Theta(n) to sort the n points by their distances from the origin. (Hint: Design the bucket sizes in BUCKET-SORT to reflect the uniform distribution of the points in the unit circle.)"

As you may see, most "standard" solutions are: split the distance at sqrt(i)/sqrt(n). However, this student raised another simple and interesting solution: simply split the distance evenly, that is, at 1/n. The justification of this solution is as follows:

"You will see the areas of regions are: (i^2-(i-1)^2)/n^2 = (2i-1)/n^2. The largest bucket (the outermost) has an averaged size: (2n-1)/n <= 2. So, the average-case running time is still Theta(n)."

I sent the solution to the authors, and Prof. Cormen answered the following (May 25th, 2013):

...  I believe that you are correct.  Of course, the solution your student developed is also interesting and makes the problem even more interesting since the simple solution works, too.

We'll think about what to do with this exercise for the next edition of the book.

Tom Cormen

It is nice to know that the authors would take this into consideration in the next edition.

I-Chen Wu

三輛腳踏車

大約十年前的有一天, 我回家時, 看到我太太氣呼呼地, 於是就問她怎麼回事, 她告訴我說「你看這小孩子, 竟然這麼簡單的英文問題都答錯, 腦筋不知道怎麼想的」然後就看到我小孩一臉委屈的坐在旁邊. 我知道我小孩子會粗心, 但其實不笨. 因此, 我就問一下什麼問題. 我太太還是氣呼呼地說「你看這麼簡單的問題：題目明明畫了五輛腳踏車, 問 "Are there three bicycles?", 他竟然答 "yes", 我真不曉得他在想什麼」

這時, 我腦中立即浮現過去在美國CMU念博士時, 與一些老美同學的溝通學習經驗.

過去在美國開始寫論文時, 我每次寫 "There is one node in the system" 來指系統確實只有一個節點時, 他們總是把我改成 "There is one and only one node in the system". 我覺得何須多此一舉, 有一次就問「你不是常常強調, 技術報告要愈簡短愈好且我沒說錯阿！」他說可是這有 "至少一個" 的意思. 後來, 我用 "There is one node in the system" 表達 "至少一個" 的時候, 又被他改成 "There is at least one node in the system". 這次, 我跳腳了, 我說你不是說有 "至少一個" 的意思. 他說沒錯, 但這句話也常有 "只有一個" 的暗示. 討論到最後,得到的結論是 "There is one node in the system" 這句話, 口語可以, 通常暗示只有一個, 但精確地說, 是最少一個. 但這對科技報告或論文而言, 會被視為語意不清. 之後, 我還故意在論文中試著用同樣方式寫幾次, 然後, 換別的老外來改, 結果屢試不爽, 都被改過來. 這點讓我蠻訝異的, 可看出這對他們似乎是從小就有的訓練.

回想起這些後, 於是立刻請我太太息怒, 我轉過身問小孩, 他的想法是什麼. 他很委屈地說「這題我是想了很久, 真的 "有" 三輛腳踏車在那兒阿！所以我答 "yes", 我還是覺得我的對」於是, 我就告訴他分享我過去的經驗. 並告訴小孩說「這題的問題是題目不清楚, 我很高興你有自己的想法. 我鼓勵你告訴老師你的想法, 並據理力爭, 但記得要有禮貌, 分數不是重點. 重點是表達你的想法, 並學習說服別人」

這問題不在答題者是否聰明, 是否學問夠, 而在題目出得不好. 身為老師, 我經常以此警惕自己, 並藉此教學生如何做到好的表達, 尤其在科技報告論文之寫作及簡報. 一篇好的科技報告文章, 就是應該要避免任何語意不清的地方.

前一陣子, 報導 "6÷2（1+2）等於多少", 很多媒體主軸還是在 "考倒很多人" (例如, http://www.ttv.com.tw/100/05/1000504/10005049061704I.htm). 其實, 這有點誤導, 真正的問題是不該出這樣的問題. 若是在寫文章的時候, 你不能寫成這樣, 這是不好的寫法. 這層意義更為重要, 卻常被大家忽略了.

後記: 

在此, 順便感謝一下過去在CMU幫我很多, 並相當值得尊敬一位同學: Joseph M. Tebelskis. 他就是上述經常幫我解惑的老外同學. 他除了經常幫助別人, 在二十多年前, 即推行環保不遺餘力. 不過, 他英年早逝, http://www.findagrave.com/cgi-bin/fg.cgi?page=gr&GRid=34616842. 想藉此追悼他.

啟用

平常忙於上課及做研究, 實在沒有太多時間碰部落格. 今天終於啟用這個部落格, 不過也還在學習試用, 以後會在此偶而寫寫心得. 不過十分抱歉, 可能不會有太多文章, 或即時回應留言. -- IC