2008年10月23日 星期四

Reverse linked-list

剛才看了《The Guerrilla Guide to Interviewing (version 3.0)》,立即想重寫 Joel 提到的兩題面試關鍵題:“reversing a linked list” 和 “detect loops in a tree structure.”。後者很簡單,前者要更動指標內容,記得初學 C 時讓我奮鬥了很久,想來看看自己現況如何。

完成的程式如下(全文見這裡,記得用 gcc -std=c99 編譯):

Node* reverse(Node *node) { if (!node || !node->next) return node; Node* head = reverse(node->next); node->next->next = node; node->next = 0; return head; }

若是以前的話,大概不能這麼自然地寫出簡潔的 code,看來學過 scheme 果然有差,變得較能從高階觀點堆砌程式,也就是將 function 看成基本單位,如此一來,遞迴是自然而然的事。得找個時間練練 functional language,這計畫不能放棄。

2008年10月16日 星期四

中翻英,線上翻譯測試 - Google Strikes Back!

剛才無聊看看 Google Analytics ,發現本站最熱門的文章還是那篇《中翻英,線上翻譯測試》,我不知該說什麼,這不是件令人高興的事啊。總之,一時興起又來測看看。

最近 Google 翻譯似乎變強了,果然有在學習啊!輸入問題如下:

我要代替月亮來懲罰你

兩年前 Google 的回報令我很失望:

I want to punish you replace Moon

沒想到現在 Google 幾乎翻對了

I want to punish you in place of the moon

google 一下會發現有不少人提到類似的句子,附帶一提,個人心目中最完美的翻譯是:

In the name of the moon, I will punish you!

其它家翻譯結果沒什麼變,就不再貼了。

另外再測了之前亂測的中文詩詞,有些變化,不過說不上是變好變壞,都很糟就是了。看來博大精測的中文仍是機器翻譯無法跨越的高牆,也是國高中生們無法跨越的牆啦

2008年10月13日 星期一

碩士研究生涯回顧 (4)

最近週末都在打 YsO,不小心就拖稿了。

上回提到碩一上的結束,我終於確定研究方向為 social bookmark。碩一下修指導老師開的 Data Mining 和必修課 Formal Language。由於我兩門課都有些背景知識,沒花太多時間在課業上。學期初滿認真地做研究,也在 delicious 的 tag 裡找到一些有趣的訊息,像是人們提到 usb 時,容易聯想到 portable [*1],我猜這是因為隨身碟是最熱門的 USB 產品而帶來的印象。後來斷斷續續想了些相關點子,可惜沒足夠的時間做進一步的研究。

結果後來被會長拐去參加比賽,加上專題生的比賽,同一時間報了五六個比賽吧。原本想亂槍打鳥,看那些發展較好就做下去,結果都有過初賽,搞得寫完初賽報告就不想比了(一口氣寫太多報告把參加整個比賽的力氣用完了)。最後大多爛掉了,幸好還有一兩個有好成績,像是去西安參加微軟思源競賽,是滿有趣的經驗。這算是我參加過的比賽裡,自認為做得最有成就感的,開發速度快,demo 效果不壞,報告也滿成功的。我們做的產品 BNW (Brand New World)用來比較公司品牌或產品。輸入公司或產品名稱後,BNW 會彙集網路上的直述句,再計算出分數。

Brand New Wrold

上圖是其中一個 demo 例子,比較四家公司的品牌。資料只是 web 上的一小部份取樣,不見得能反映實際情況,但不管怎麼說,我們是去向主辦單位 Microsoft 報告,這個結果還挺尷尬的,最後決定在簡報時快速帶過這張,免得被人誤認為是去拆台的。另外,當時看了相關研究「Opinion Mining」,主要是看 Bing Liu 的論文和書,滿有意思的。比賽結束後老師問我是否有意延伸這方面的研究,不過我覺得資料難以取得(比賽時有 MSRA 支援),而且我比較想做 social bookmark 的研究,就結束掉這個小插曲,而碩一下也這麼結束了。之後是碩士兩年裡最發光發熱的暑假衝刺時期,後來完成的兩篇論文,都是在這暑假內完成一半以上的內容。

ps

*1 我用 association rule,發現”usb” -> “portable” with confidence 80%,”portable” -> “usb” with 60%。