「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