2007年9月27日 星期四

Gosh!我遇到Gosh了!!

既然是遇到Gosh,當然要用這麼老梗的標題囉。傍晚走向車棚時,看到眼熟的面孔,雖然之前有看過,但那時怕認錯人沒打招呼,五年沒見,樣子變了很多。這回沒想太多,就叫了聲「Gosh!」,結果真的是Gosh,和蘇胖子一樣,Gosh上大學沒多久就瘦了下來。和Gosh說上回看到你怕認錯人沒打招呼,Gosh馬上說「幹嘛這麼weak啊!」,果然是89人的說話風格,令人懷念。大概聊聊大家的近況,約看看之後要不要大家一起打球,新竹幫的走了幾個,又來了幾個,還是湊得到兩三隊打三對三鬥牛啦!和Gosh聊天時想了很久,想說新竹幫還有誰,偶而想到一個人,又多一分樂趣。結果打這篇時忽然想到漏提了王X宇,明明之前才在版上看到,怎麼會沒有印象,哈哈!

2007年9月24日 星期一

VIM-LaTeX

官網:http://vim-latex.sourceforge.net/

下載和安裝說明:抓下壓縮檔、解開到~/.vim下(Un*x)或~/vimfiles(Windows),就這麼簡單。

這玩意兒真是太強了,之前自己key那堆符號是key心酸的。place holder的概念真不錯,打完該打的字後,按個Ctrl+j就能跳到下個位置,像插入Figure時感受特別明顯,打個EFI後,就能一路填完檔名、標題、索引名稱等。還有以 ` (反單引號)開始的縮寫字,像是 `/ 會變成分數用的 \frac{}{}, `* 變成乘法 \cdot,省不少工。愛惜手指,才能用更久啊!

其它像插入reference也是超方便,會先列出各節內的label,游標移上去按個ENTER就自動加進去了。若要發揮更完整的力量GVIM才是王道啊,開始考慮要不要移回Windows環境用LaTeX,之前習慣在Un*x server上做事,自然地也在上面用LaTeX了。

白天的時候沒什麼差別,到了夜裡,沒有人的空房子,顯得特別冷清。平常室友間的交談也不多,夜裡也是睡得睡,沒睡得在自個兒房裡忙,照理說有沒有人在,沒什麼分別。然而,沒有人的四人公寓裡,就是有著這樣的微妙感,不禁讓我想到,等我有錢後,也不會想買大房子(不是因為富爸爸說房子是負債哦)。

第二天的夜裡,習慣了冷清的公寓,取而代之的,是熟悉、帶有潛藏愉悅的孤獨。孤獨和寂寞是不同的,也許這也是我一直沒交女朋友念頭的原因,畢竟,孤獨是一種享受,是隨著年歲增長,漸漸步入社會之後更難找回的感覺,另一方面,也是沒適合的對象。這種時期,正是閱讀村上春樹作品的好時機,可惜手邊只有一本英文版的「國境之南‧太陽之西」,讀起來費力許多。趁著晚餐送來之前翻了幾頁,立即從”Only”的字樣裡感受到村上營造的隔離感,配合封底的介紹,觸即內心深處、一個遺忘的角落。

”And a boyhood memory of a wise, lonely girl named Shimamoto clouds his heart.”

即使沒有放著音樂,即使是深沉的夜裡,週圍還是存在著聲音,在意識清醒的狀態下,絕對安靜是否存在呢?那又會是什麼樣的感受?記得小時候害怕完全無聲的夜,躲在被窩裡不敢伸出腳。習慣社會喧鬧聲後,反而漸漸期待著。然而,當絕對安靜出現的那一刻,立即又會害怕這樣的存在,而刻意破壞它吧。

對我來說,隱居在都市裡才是最棒的,如同陶淵明所言一般:

結盧在人境,而無車馬喧。
問君何能爾,心遠地自偏。

只不過我不是什麼心遠地偏這類高尚的心境,只是離不開網路和便利商店罷。既然要隱居,當然是選最方便的形式執行。

2007年9月13日 星期四

程式語言效能評比

這可能不少人看過了,剛才看了Joel的一篇文章,提到Ruby效能吊車尾,加上最近寫了不少Ruby program,感覺Ruby的確有點慢,好奇地看了一下熱門語言的差異。Ruby真的是時間慢又占空間,相較特性差不多的Python,Python快多了,但Java又比Python快,問題是Java用的空間比較多,但空間相較時間較沒那麼苛 ( 64bit的時代,RAM可以加,CPU很難再快了 ) 。大致上來看,Java的速度還不壞,雖然仍輸C++一大截啦,若JRuby完全整合成功的話,Ruby才有希望普及使用吧 但像Google不管怎麼樣,應該仍是用Python沒用Ruby吧,而且Python作者都挖進去了,必要時也可以投入改進Python。

不過我還是要強調一樣的觀點,大部份時候,我們並不需要那麼快的速度,而較重視開發時間。極端來說,跑得再快的程式沒有寫完,也是無法用的。
但這個平衡點就因人而異啦,我學Ruby是因為它能幫我快速處理掉大部份的事。

2007年9月8日 星期六

偽晨跑紀念

雖然不算晨跑,至少是上午跑,紀念一下。去程用走的,回程慢跑,來回大概半小時吧,先看看能不能一週至少跑一次。

2007年9月7日 星期五

快速找中位數演算法和KNN

之前找到kd-tree這個data strucutre,想說可以用它來找KNN (k nearest neighbors),而且建立kd-tree的速度很快,空間成本又和資料量成線性關係,實在是很讚的資料結構。

實作kd-tree的關鍵在於要能快速找到中位數,而在quick sort的Theta(N*log(N))的證明裡,有經典的找中位數演算法:用Theta(N)的時間找出中位數。不過這個演算法的常數項很大,是理論上很有意思的方法( 由它證明了quick sort的order可以寫為 Theta(N*log(N)) ),但實務上不會拿來用。

找了一下快速計算中位數的方法,找到一篇有趣的報告:“Fast Median Search: an ANSI C implementation”。這篇報告裡提供幾種找中位數的方法以及時間比較和實務考量的分析,並附有 C source code。這篇報告用的方法都是從沒排序的陣列裡找第 k 小的數字,而找中位數只是這個問題的特殊化罷了。關鍵在於從不同的角度思考中位數的定義:

The median of a list of N values has the property that in the list there are as many greater as smaller values than this element.

很漂亮的出發點,值得學習。

我從中選了差不多最快、且馬上能讀懂的Wirth,將它改成Ruby版,畢竟我其它相關的code都用Ruby寫的(按此觀看Ruby版的Wirth)。Wirth的精神和quick sort一樣,若已學過quick sort的話,看一下code就能明白Wirth的做法。

改完Ruby版的Wirth演算法後,準備要寫kd-tree時,才想到既然我要找KNN,其實找到第 k 近的鄰居後,就可以用它當pivot快速找出前 k-1 個鄰居(掃陣列一遍而已),可以不用實作kd-tree,執行效果應該還可以接受。事實上Wirth的演算法有個副作用(side effect),它會更動原來陣列內元素的順序,但妙的是,這個副作用在KNN裡反而省下一次線性搜尋的時間,因為找完第 k 近的鄰居後,前 k 個元素就是 KNN 了 (讀一下code立即可以明白)。

有時候意外地把不同時期學的片段記憶整理一下,串成一個完整的觀念,感覺頗爽的。最棒的是,破碎學到的東西,可以更有系統地重新吸收。

ps.

  • 當然,網路上可以找到不少kd-tree的實作code,像Weka裡就有Java版的kd-tree,只是功能太雜,code太長了,以我的小規模用途來說,看懂它的code還不如自己寫快一點。
  • 真的建出kd-tree的話,應該會更快,因為kd-tree建一次可以找所有元素的KNN,每個元素找的時間是O(N),但大部份元素應該不會真的要看N個元素。而Wirth的演算法在找各個元素的KNN時,相當於每個元素重算一次,每個都是Omega(N)。有時間的話真想來比較看看kd-tree能比Wirth快多少。

2007年9月1日 星期六

微軟就甘心:記錄篇

來學小豬記錄一下,今天剛好早睡成功,因為疲勞累積到一個程度,做事沒啥勁,大概晚上11點左右躺下去沒多久就睡著了。微軟真是貼心的作業系統,知道我早上都爬不起來,剛才利用windows servicepack幫我來個morning call(update後會自動重開電腦,會有關機音效),時機算的正準!難得能這麼早起,特此記錄一番。