Blog JY

台北 101 大樓觀景台

2008-10-07T19:11:00.006+08:00

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

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

深入 qsort(3)

2008-09-09T02:28:00.015+08:00

如果你有學過演算法或資料結構，相信對 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 演算法，並採用以下幾點優化的設計：

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

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

開發 JavaScript 利器 - Prototype

2007-12-31T01:48:00.000+08:00

最近為了開發 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 程式庫。

平安夜的無聊小發現

2007-12-24T20:56:00.000+08:00

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

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

2007-11-16T02:28:00.001+08:00

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

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

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

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

註：聲音檔取自 The Free Dictionary

Google's Android SDK Now Available

2007-11-13T11:06:00.000+08:00

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 的頭髮怎麼了！？)

六福村之旅

2007-11-12T19:38:00.002+08:00

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

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

PHP vs. Ruby on Rails

2007-11-09T13:53:00.000+08:00

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

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

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

CakePHP 的優點

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

Ruby on Rails 的優點

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

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

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

Google's OpenSocial

2007-11-06T00:07:00.000+08:00

最近 Google Code 上最大的消息就是 OpenSocial 了。這幾天在 Google 相關的 blog 上都是她的蹤影，例如這裡、這裡還有這裡，另外還有Mr.6 的文章值得一看。OpenSocial 計畫企圖提供一個跨網站的 social network platform ("a set of common APIs for building social applications across the web")，串連當下眾多社群網站，包括： MySpace, Engage.com, Friendster, hi5, Hyves, imeem, LinkedIn, Ning, Oracle, orkut, Plaxo, Salesforce.com, Six Apart, Tianji, Viadeo, XING 等等。

簡單的說，OpenSocial 主要目標有二：

讓使用 OpenSocial API 開發的應用程式 (gadgets/plug-ins, ...) 得以突破社群網站的籓籬，執行在任何社群網站上。
只要支援 OpenSocial SPI，任何網站都可以當 host，讓這些豐富的應用程式執行其上。

如果將來 OpenSocial 大行其道，社群網站之間的幾乎就沒有什麼隔閡了。也就是說，想用某特定社群網站來綁住會員的作法也越來越難了，未來將會更重視在內容的創意上面。Google 出招果然了得，是否能夠帶來社群網站的美麗新世界呢？

Google Maps API 卡死，CPU 負載飆高

2007-11-01T21:38:00.000+08:00

最近為了某種特殊的應用，必須透過 Google Maps API 在 Google Maps 上展現行動軌跡圖。軌跡圖繪製的方式是用 polyline 的方式，連接數百點，甚至數千點。該程式在 IE6 與 Firefox 2.x 皆可正常執行，但是在 Firefox 3 alpha、Opera 或 Safari 等瀏覽器上時，執行到一半便會卡死不動，CPU 負載飆高到 9x%。深入追蹤的結果，發現程式會死在 GMap2.panTo 或 GMap2.setCenter 之類移動地圖的函式，狀似進入無限迴圈。而且在這幾個瀏覽器上執行都是死在同個地方，看起來很像跟座標資料有關，但我實在很難相信事實會是如此。

程式卡死在 Google Maps API 函式裡的情況，看起來不大好搞。上網搜尋一下相關討論，發現也有一些人發生類似的問題，雖然沒有找到什麼明確的解決方案，不過大概可以歸納出問題是出現在處理 polyline (GPolyline) 上。偶然之間，看到有人提到 API 版本不同所引發的其他問題，靈機一動便試著替換不同的 API 版本試看看。最後，我把原來預設的 v=2 換成 v=2.x，便神奇地解決了這個問題。而 v=2 與 v=2.x 有什麼差別呢？根據 Google Maps API 官方文件：

v=2 (default) 是使用預設的 API 版本。
v=2.x (latest) 是使用最新的 API 版本，加入新功能與 bugfix，但可能沒有 v=2 來得穩定。
v=2.s (stable) 是使用最穩定的 API 版本，但功能可能比較陽春。

看來 Google 也有發現處理 polyline 上的瑕疵，在 v=2.x 版上解決了這個問題。事實上，Google Maps 在處理 polyline 上並沒有那麼單純。為了能快速繪製 polyline，Google Maps 使用了不少方法輔助，甚至在伺服器端有一些輔助的設計。細節我就沒有研究了，等有空或有需要的時候再說吧！

Google Maps API 的版本有實際的數字代碼，而且更新的速度也很快。目前 v=2 代表 2.91a，v=2.x 為 2.92，而 v=2.s 為 2.73。Google Maps API 並沒有提供取得版本資訊的方法，有興趣的想知道確切版本，可以參考 Mapki 這個網站。如果非得要在程式中動態判斷版本，底下這一段 PHP 程式碼可以提供給你參考：


function get_gmaps_api_version($url) {
  if (preg_match('/mapfiles\/([\d\w]+)\/maps2/',
                 file_get_contents($url), $m))
      return "2." . $m[1];
  return "N/A";
}

其中輸入的 $url 是 script URL：

v=2 → http://maps.google.com/maps?file=api&v=2
v=2.x → http://maps.google.com/maps?file=api&v=2.x
v=2.s → http://maps.google.com/maps?file=api&v=2.s

Gmail 新面貌

2007-10-30T20:45:00.000+08:00

據 Gmail 官方 Blog 所述，Gmail 將會有為幅不小的改進。有些人甚至已經可以搶鮮嘗試新版的 Gmail 了，不過在我申請的數個帳號中，還不見新版的蹤影，可能還得等上一等。新版 Gmail 主要是改善效能與易用性，最大改變在於通訊錄管理與 mail prefetching，詳情請見 Official Gmail Blog 上的文章。Gmail 會進步到什麼程度令人期待，不過我覺得有意思的是這篇文章的最後一段：

One side effect of this change is that if you're using third-party Gmail extensions, they're likely to stop working. We've contacted a number of the developers behind some popular extensions and provided them with an opportunity to create fixes, so check back with them for updates. We're sorry that it may be a bit of a inconvenience, but we're trying to make this change as smooth as possible.

由此看來 Google 蠻鼓勵「在 Gmail 上面搞花樣」的，甚至還會主動提醒一些 third-party Gmail 擴充套件的作者有關 Gmail 架構的改變，並提供因應方法。我想，現行有些軟體把 Gmail 源源不絕的儲存空間做為他用，這樣的作法似乎是 Google 所默許的（至少尚未禁止）。

[更新] 2007-11-08 - 我的 Gmail 出現新版了！ (不過目前似乎只支援 Firefox)

Gmail to Support IMAP

2007-10-27T22:00:00.000+08:00

前幾天 Gmail 公布 IMAP 的支援，這一個令人期待已久的功能，讓 Gmail 更臻完整。IMAP 的好處就不用多說了，對我來說，腦中第一個浮現的應用就是備份舊信。隨著 Gmail 容量不斷加大，再加上 Google 在搜尋方面的強項，把以前舊信件通通塞給 Gmail 管理是個不錯的主意。

以前就曾經想要把舊信匯入到 Gmail，稍微研究了一下，有幾種方法：

使用 Gmail 工具，如 Gmail Loader。
使用 Gmail 擷取外部 POP3 的功能。

第一種方法是利用 SMTP 將信件一封封寄入 Gmail 信箱，而 Gmail Loader 支援很多種 mailbox 格式。但是使用第一種方法的缺點是，寄入 Gmail 的舊信所顯示的時間並非舊信當時的時間。既然舊信的日期無法保留，這種方法對我來說就沒什麼意義了。

第二種方法需要架設 Mail Server，想辦法把所有舊信塞到特定帳戶的 mailbox 中，再叫 Gmail 過來擷取。我利用第二種方法，成功地將大部分的舊信匯入 Gmail 中，但某些信件會被 Gmail 認為內含病毒或是垃圾信，需要費一番心力手動調整方能成功匯入。Gmail 的 POP3 取信功能每次最多擷取 200 封信件，每擷取 200 封信件會休息一陣子再繼續擷取。我把大約 22,500 封左右的舊信匯入 Gmail，共費時兩天多。

現在 Gmail 支援 IMAP 了，要匯入舊信就不用那麼麻煩了。如果你是使用類似 Outlook Express 的電子郵件軟體，直接將舊信複製到 Gmail 帳號目錄下的 [Gmail]/All Mail 子目錄下，便可以直接將舊信存回 Gmail 了，相當方便。不過，我還沒利用這種方法備份大量的信件，不知道速度如何。

Array Subscripting in C

2006-11-23T20:30:00.000+08:00

在 C 語言中，我們這樣宣告一個陣列：

char c[] = "abcdefgh";

一般，我們會用 c[0], c[1], ... 這樣的語法來存取陣列。在這個例子中，我們知道 c[0] 為 'a'，而 a[1] 為 'b'，如果是寫成 3[c] 呢？一般人大概會猜 'd'，沒錯！跟 c[3] 的值一樣，就是 'd'。那如果宣告成 int 陣列呢？會不會有什麼不一樣的結果呢？

int i[] = {1, 2, 3, 4, 5, 6, 7, 8};

2[i] 的值應該是多少？沒錯，答案還是跟 i[2] 一樣，就是 3。

類似 3[c] 這般的寫法看起來很奇怪，令人全身不舒服，但是在 C/C++ 語言中卻是合法的。我們可以大膽假設：

對於一維陣列來說，如果 x[y] 符合語法，則 x[y] 就等於 y[x]。

在 C 語言中，指標 (pointer) 與陣列 (array) 之間有著很密切的關係，一般人也常不明就裡地混用。根據 C 語言的規定，x[y] 跟 *((x) + (y)) 是完全一樣的。換句話說，C 編譯器會把 x[y] 解讀為 *((x) + (y))。而 x[y] 要能夠通過 C 語言文法，x 或 y 其中一個必須為指標，另一個必須能夠賦值 (evaluate) 為整數。以 binary operator + (加法) 作用在整數與指標上，最後會賦值為指標型別。因為加法具有可交換性 (commutativity)，所以不管是 ((x) + (y)) 或是 ((y) + (x)) 都是作指標相加，因此這兩個述式所得到的結果是一樣的。

當然，類似 0[i] 這種寫法並不值得鼓勵，除非你是在參加 IOCCC 比賽。

參考：C FAQ: Question 6.11