台北 101 大樓觀景台

拿到兩張台北 101 大樓觀景台的票，九月底就要截止了。雖然天氣不好，但眼看號稱今年最強的薔蜜颱風要撲台了，所以趁這個週末跟 Oberon 趕快去參觀，順便測試使用 i-gotU 軌跡記錄器，搭配 @trip 服務的效果。

點取底下地圖可以看到詳細內容：

深入 qsort(3)

如果你有學過演算法或資料結構，相信對 quicksort 一定不會陌生，或許細節忘了，但是至少應該有聽過。實作 quicksort 讓我們學習到重要的「divide and conquer」設計典範 (design paradigm)，並且對於操作邊界值有更精確的體體認。我每隔一段時間都會重新實作幾個典型的排序演算法，例如 quicksort、insertion sort、bubble sort、heapsort、merge sort 等等。藉此磨練自己的 coding 技巧，靈活一下自己的腦袋。

實作 quicksort 時，不免讓人想到 standard C library 中的 qsort(3)。從 qsort 這個字眼上，很直覺地想到他可能是由 quicksort 這個名稱來的，甚至直覺地推斷 qsort 就是 quicksort 的實作。實際上只答對了一半，qsort 遠比我原本想像的還要複雜。參考 GNU libc 2.4 中 qsort 的實作部分，在記憶體方面，運用了不少跟硬體平台相關的特性，以加速記憶體的處理。撇開平台相依部分不談，單就演算法設計方面來看也有很多巧妙之處。

void qsort(void *base, size_t nmemb, size_t size, 
           int(*compar)(const void *, const void *));

首先，qsort 會先判斷欲排列元素個數 size 是否小於 1024，若小於 1024 則呼叫 msort_with_tmp 來處理。msort_with_tmp 實作 merge sort 演算法，最後一個參數是一個 size 大小的 buffer，作為 merge sort 所需的 O(n) 空間之用，可以避免過於頻繁的記憶體配置。若是 size 大於 1024，則會根據目前系統的記憶體狀況，決定該使用什麼演算法。在最壞情況下，merge sort 演算法的時間複雜度是 O(n log n)，好過 quicksort 的 O(n²)。由於 merge sort 需要額外的 O(n) 空間，所以在記憶體空間允許的條件之下，會優先使用 merge sort，否則便呼叫 _quicksort。

_quicksort 實作一個真正的 quicksort 演算法，並採用以下幾點優化的設計：

1. Non-recursive (非遞迴) - 使用 stack 資料結構取代遞迴呼叫所需要的 function stack，增進程式執行效率。實際上這個 stack 不用太大，在 32-bit 環境下，最多只需要 32 個元素空間 (在 64-bit 環境下，則為 64 個)。為什麼是 32？因為在 32-bit 環境下 size_t 為 32-bit，log 2³² 為 32。
   
2. 以 median-of-three 方法決定 pivot - 一般 quicksort 演算法通常取開頭元素當作 pivot，但這往往不是一個理想的值，尤其對於已排序的陣列來說，會造成最壞的結果。以陣列開頭、最後與中間位置三值的中位數當作 pivot，比較有機會取到較理想的值。
3. 混合 insertion sort 增加效率 - 對於元素個數少於某個 threshold 的 partition，使用 insertion sort 能夠大大地增加執行效率。對於小陣列而言，insertion sort 會比 quicksort 來的有效率許多。在 GNU libc 2.4 實作中，此 threshold 值設定為 4 (MAX_THRESH)，個人感覺太小了點。有些實作將它設定為 8，如 Visual C++。
   
4. 較小的 partition 優先處理 - 換言之，較大的 partition 先放入 stack 中，此舉保證 log(size) 不會超過 stack 大小。

多讀經典程式碼，實在獲益良多啊！

開發 JavaScript 利器 - Prototype

最近為了開發 AJAX 網站，需要找一套支援 AJAX 的程式庫，想到了前一陣子發現的 script.aculo.us 這套 JavaScript 程式庫。script.aculo.us 裡面提供了很多令人讚嘆的 JavaScript 視覺特效，而其是架構在 Prototype 這套 JavaScript 框架上。其實要使用 AJAX 功能，只需要 Prototype 即可。再動手寫幾個測試程式之後，發現 Prototype 實在太好用了，尤其是有 Prototype 的 Swiss Army Knife 之稱的 $() 函式，令人覺得非常神奇。

當然，作為一個 programmer 不能只是感到神奇而罷休，便開始追蹤 Prototype 的程式碼。在追蹤之後才發現，原來 JavaScript 可不是我原本想像的那樣而已，JavaScript 也決不簡單。在 Prototype 原始碼中看到了很多高段的 JavaScript 技巧，不得不佩服作者的巧思，令我獲益良多。如果能看懂 Prototype 原始碼，我敢說你的 JavaScript 功力已經是很不得了了。

Prototype 已經變成我開發網頁的必備良藥之一，改天有空開始再來玩玩 script.aculo.us、Rico 或 YUI 等等其他 JavaSctipt 程式庫。

平安夜的無聊小發現

大家大概知道，從前一陣子開始，Gmail 的容量成長開始加速，預計明年達到 6 GB 以上。剛剛無聊粗略計算了一下，發現 Gmail 的容量在美國時間平安夜當天 (約中午) 會剛好成長到 6000 MB。不知道是不是 Google 故意設計的？ :)

台灣辦公室中常聽到念錯的英文單字

在台灣辦公室中，尤其在科技業的，說話時老喜歡夾雜一些英文單字。對於某些外來的專有名詞，直接唸原文會比較直接，避免誤會。但是對於動詞，除非有特殊情況，我個人認為還是盡量使用中文。習慣一旦養成，要改談何容易，但最起碼發音要正確。如果很愛「ㄌㄠ\」英文卻又發音不正確，不是很糗嗎？對於英文非母語的我們，要發音非常標準是有點強人所難啦，但至少要正確吧。

底下舉幾個常被念錯英文單字 (有些字念錯意思可是差了十萬八千里呢)：

1. file 唸成 fire 。
   例：麻煩你把 fire 傳給我。(不禁讓我想到 Prometheus 普羅米修斯)
2. email 唸成 emare (依媚兒)。
   例：給我你的依媚兒。
3. cancel 唸成 cancer。
   例：這個 case 最後被 cancer 了。(怎麼會扯到癌症)
   
4. standard 字尾 dard 應該要發的是 spider 的音，而非 radar 的音。
5. implement 唸成 impriment。
6. exit。

類似 l 與 r 的音不分的情況不勝枚舉，這可能是亞洲國家英文的通病吧。只要把這兩個音分辨清楚，我想英文發音就算是前進一大步了。

註：聲音檔取自 The Free Dictionary

Google's Android SDK Now Available

Google 上星期才公佈了 Open Handset Alliance，今天隨即開放 Android SDK 下載，讓開發者在 Android 上創造手機應用程式。想當然爾，軟體開發平台充分利用到 open source 的資源：Linux 2.6, Java, Eclipse, WebKit, SQLite 等等。同時也使用較寬鬆的 Apache License，讓參與的硬體廠商得以保護其智財。目前公布的 SDK 算是個「搶鮮版」，Google 在廣納開發社群意見後也會不斷地發佈更新版本。

為了刺激全世界的開發者共襄盛舉，Google 更大手筆端出高達千萬美金的獎金，舉辦 Android Developer Challenge。想必此舉一定讓全世界的高手摩拳擦掌，躍躍欲試。第一輪入選的五十名，每位可以得到 $25,000 美金，第二輪則選出二十名，其中十位可得 $100,000 美金，另外十位可得 $275,000 美金。而這應該只是第一階段而已，因為上述獎金只佔總獎金的一半 (五百萬美金)，沒意外的話還會有第二階段的比賽。看到這樣的獎項，真的令人很心動啊！

Android 的介紹：

(看到這段影片第一個反應是：Sergey Brin 的頭髮怎麼了！？)

六福村之旅

星期六是公司舉辦的 Family Day，地點在六福村主題樂園。上一次到六福村已經是六年前的事了，還記得那天是 2001 年的國慶日，所以印象比較深刻。現在六福村對我來說已經沒有多大的吸引力了，我對於人工式的樂園沒多大興趣，也不熱衷刺激的遊樂設施。老實說，去玩那些刺激的遊樂設施，心裡多少會毛毛的。人說越老越怕死，一點都不假。不過相較於男生，女生似乎比較喜歡這種刺激的遊樂設施。不知道是不是不懂的害怕，還是喜歡享受尖叫的快感？這天六福村主題樂園的重點項目「笑傲飛鷹」與「大怒神」因風強所以暫停開放，現場抱怨聲連連，我倒是鬆了一口氣。

以往到六福村總是忽略它還有一個野生動物園 (曾幾何時，野生動物園是六福村的招牌項目)，總認為要玩到遊樂設施才算是值回票價，不過這次的六福村之行有了新的體會。常被忽略的野生動物園，才是這次讓我們覺得值回票價的項目。參觀野生動物園有兩條路線，一個是搭乘蒸汽小火車環繞動物園區，另一個是搭乘猛獸遊園巴士。聽說蒸汽小火車 (當然不是用真的蒸汽火車頭) 是前不久才規劃好的，遊客可以近距離觀賞較溫和的動物。跟台北動物園相比，雖然六福村野生動物園的動物種類不多，但是動物們的活動空間比較大，也比較自由，在這裡的動物應該會比較快樂吧！下次如果有機會到六福村一遊，建議可以去逛逛野生動物園。

PHP vs. Ruby on Rails

因為工作的需要，必須在有限的時間內開發一個網站。這個網站需要具備使用者帳戶管理與認證的功能，並管理使用者上傳的資料，故與資料庫之間的關係密切。我也希望這個網站能盡量運用到 open source 的力量，所以基本的軟體平台將會以 Linux + Apache + MySQL 為主。網站開發工具方面，目前有三個選項：

1. 純 PHP (不使用 PHP framework)
   
2. CakePHP (或其他 PHP framework)
3. Ruby on Rails (RoR)

就我自己以往的 web development 經驗來說，我大多只是利用 PHP 寫一些網頁小工具，最多就是開發規模不大的小網站。對於開發一個中型的網站來說，只使用純 PHP 開發是相當辛苦的，除了人力有限之外，未來還要面臨維護與後續擴充的問題。因此，我需要一個 framework，而現在的問題就是該選擇 PHP 的 framework (目前以 CakePHP 為首選) 或是目前當紅的 Ruby on Rails？對我來說，這兩者各有優劣：(我必須再強調，這是根據我個人情況來說 :)

CakePHP 的優點

1. 我比較熟悉 PHP 語言
2. PHP 豐富的資源 (容易整合許多現有 PHP 的 open source 計畫)
3. 成熟度高，品質已被廣為驗證 (許多之名網站都是用 PHP 打造的)
4. 執行效率快 (相較之下，Ruby is slow!)

Ruby on Rails 的優點

1. Ruby 語言優勢 (如 OO)，以及學習新語言的樂趣。
2. 可能是明日之星 (迅速崛起，目前很火紅的 framework)
3. Rails framework 肇始者 (比較忠於原味？)
4. Ruby 社群團結，只有一個 RoR (相對之下，PHP 選擇太多，容易缺乏向心力)
   

學習新語言固然很有趣，但總是需要時間才可以達到某種深度。雖然 CakePHP 可算是 RoR clone，但並非 clone 就會比較遜色。有時候非但不會比較遜色，反而能夠截長補短。CakePHP 以成熟的 PHP 技術為基礎，廣納 Rails 的設計哲學與精神 (MVC, ActiveRecord, 等等)，應該具備相當的實力才是。Ruby 面臨到的最大問題之一就是效率，效率問題牽扯到的層面很廣，包含根本的基礎語言本身。David Heinemeier Hansson (RoR 之父) 也不穢言，為了解決效率問題，曾經將一段 Ruby 的程式法以 C 改寫。Twitter 可能是目前以 RoR 開發的網站中的最大者，其開發者也為 RoR 效率問題所苦。

以此來看，CakePHP 似乎是比較符合我的需求。