「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