2011年11月4日 星期五

9. 空間轉換 - OpenGL FAQ

9.001 我搞不定空間轉換啦。我可以去哪兒學習了解矩陣這東西?

基本矩陣數學與線性代數的詳細解說已經超出了本FAQ的範圍,這些內容美國的高中課程會教。如果你已經學過了,只是現在有點混淆 (這是老手也有的常見問題),去讀 Steve Baker 的矩陣觀念複習尤拉角度的文章

這兒有向量、矩陣、四元數運算的 Delphi 基本演示代碼

9.005 OpenGL 矩陣是 column-major 還是 row-major 呢?

以編程觀點來看,OpenGL矩陣是個陣列,有16個數值,四個基底向量依序地擺放在記憶體中。陣列的索引值編號為 1~16,其中位移分量(Translate Component) 佔據了16值的陣列的第13、14、15號元素,這些內容都寫在 OpenGL 2.1 規格書的 2.11.2 小節。

Column-major 與 Row-major 表示法純粹只是慣例上的差別。請注意,把向量乘在 column-major 矩陣的後頭,跟把向量乘在 row-major 矩陣的前頭,產生的結果完全相同。OpenGL規格書與OpenGL參考手冊雙雙採用了 column-major 表示法。只要夠明確,你用任何一種表示法都行。

但不幸地,規格書跟藍皮書中的 columr-major 格式造成了 OpenGL社群無止盡的混淆。因為 Column-major 表示法與一般編程人員預期的記憶體布局不相同。

9.010 OpenGL坐標系使用什麼長度單位呢?

短答案: 你想要單位是什麼就是什麼。

依據於你的幾何資料,應用程式可以把OpenGL座標單位視為毫米(millimeter) / 秒差距 (parsec) 或者任意更大或更小的長度單位,端賴哪個對你比較方便。

OpenGL也允許你指定不同的坐標系單位。比方說,你覺得這樣做比較方便,飛機控制以公分為單位,但是機身使用單位公尺,翱翔在單位是公里的世界天空中。OpenGL 的 ModelView 矩陣可以隨意縮放不同的座標系統,最後落於同一個眼空間座標中。

建立適切的投影矩陣跟ModelView矩陣是應用程式的責任,確保觀看者有適當的距離、視角、而且近平面跟遠平面都位於適當的範圍。比方說,一個展示微米尺度級的分子應用程式的鏡頭就不該放在10呎遠,且視角60度寬。

9.020 如何只對場景裡的單一物體作空間轉換,或者賦予每個物體它自己的空間轉換?

對此 OpenGL 特別提供了矩陣堆疊 (matrix stacks) 。在這個狀況下,我們採用 ModelView 矩陣堆疊。

典型的 OpenGL 應用程式會先呼叫 glMatrixMode(GL_MODELVIEW) 來設定矩陣模式,之後或許會呼叫 gluLookAt() 來載入視圖轉換。更多關於 gluLookAt() 的資訊

接著呢,將繪圖代碼的前後用 glPushMatrix() 以及 glPopMatrix() 兩個函數包夾起來,那場景中的每個物體的繪製,就只會套用他的自己的空間轉換了,例子如下:

glPushMatrix();
glRotatef(90., 1., 0., 0.);
gluCylinder(quad,1,1,2,36,12);
glPopMatrix();


上面的代碼繪製了一個以X軸為轉軸旋轉了90度的圓柱體。呼叫 glPopMatrix() 之後,ModelView矩陣會回復到呼叫 glPushMatrix() 之前的值。Similar call sequences can render subsequent objects in the scene.

2011年10月30日 星期日

8. 使用視圖與相機鏡頭轉換,及 gluLookAt() - OpenGL FAQ

返回 OpenGL FAQ 目錄

8.010 OpenGL裡的相機鏡頭到底是怎麼運作的呢? 

就目前的OpenGL來說,沒有相機鏡頭這種東西。更精確地講,相機永遠都位處於眼空間座標的原點 (0,0,0)。你的OpenGL應用程式為了假裝出移動相機的樣子,必須移動場景,對整個世界場景做相機鏡頭的逆空間轉換。

8.020 我要如何移動場景裡的眼睛或者相機鏡頭?

以相機鏡頭模型來說,OpenGL 並沒有提供介面去做這件事情。然而,GLU庫提供了gluLookAt()函數,傳入眼睛本身位置,眼睛瞄準點位置,以及朝上向量,都是世界空間坐標。這個函數依據參數計算出正確的相機逆空間轉換矩陣,並且乘上目前的矩陣。

8.030 我的相機鏡頭應該放在 ModelView 矩陣還是 Projection矩陣?

GL_PROJECTION 矩陣只應該包含投影變換,它必須將眼空間坐標(eye space coordinates)轉換到裁切坐標(clip coordinates)。

GL_MODELVIEW矩陣呢,如其名,應該包含模型(modeling)與視圖(viewing)轉換,將物體空間坐標轉換成眼空間座標。所以請記住,永遠把相機鏡頭轉換放在GL_MODELVIEW矩陣,而不是GL_PROJECTION矩陣。

你可以把投影矩陣(projection matrix)想像成相機鏡頭的各種特性,像是視角的寬窄、焦距、用了魚眼鏡頭等等。而把模型視圖矩陣(model-view matrix)想成,你目前拿著相機站立的位置,及鏡頭指向的方向。

這份 The game dev FAQ 對這兩個矩陣說明得很不錯。

去讀讀 Steve Baker 的文章「濫用投影」(備用連結) 吧。此篇文章寫得很好,值得推薦。它曾經幫助過許多OpenGL新手程式員。

8.040 我該如何實現鏡頭變焦 (Zoom) 的操作?

簡單的做法是對 ModelView矩陣做等比縮放(uniform scale)。但是當模型放得太大時,通常會導致模型被近平面及遠平面裁切掉。一個比較好的做法是限縮投影矩陣裡view volume的寬與高。舉例來說,你的程式對應使用者的輸入,儲存了一個縮放參數值。當縮放值是1.0 時不變焦。縮放值變大就縮小視角,結果模型看起來就放大了。縮放值變小時就反過來做。程式碼範例看起來可能像這樣子:
/* 如果你想就設成全域變數。依使用者輸入改變值,初始值是1.0 */
static float zoomFactor; 

/* 一個設定投影矩陣的例程,通常在 resize 事件處理呼叫它。
   繪圖區域的寬、高是整數。
   此例程會創建一個投影矩陣,有正確長寬比以及縮放參數。
*/
void setProjectionMatrix (int width, int height)
{
   glMatrixMode(GL_PROJECTION);
   glLoadIdentity();
   gluPerspective (50.0*zoomFactor, (float)width/height, zNear, zFar);
   /* 'zNear' 與 'zFar' 隨你高興 */
}
你的程式也許用glFrustum() 而不是 glPerspective()。這有點棘手,因為 left, right, bottom, top 這四個參數與近平面(zNear) 的距離,也會影響視野大小。這裡合理的假設你使用固定的近平面距離,那 glFrustum() 看起來會是:
glFrustum(left*zoomFactor, right*zoomFactor,
    bottom*zoomFactor, top*zoomFactor,
    zNear, zFar);
glOrtho() 用法也差不多。

8.050 我有了目前的ModelView矩陣,該如何反推相機鏡頭在物體空間裡頭的座標位置?

相機鏡頭或眼睛位置永遠位於眼空間的原點 (0,0,0)。將原點轉換成向量 [0 0 0 1] ,然後用 ModelView 矩陣的反矩陣去乘,結果就是相機鏡頭在物體空間中的座標位置。OpenGL不允許你查詢ModelView矩陣的反矩陣 (用glGet*等函數),你必須要自己寫代碼來計算反矩陣。

8.060 我該怎麼樣讓鏡頭不斷「環繞」著場景中的某一點運行旋轉?

你可以把鏡頭留在原位不動,而轉動整個場景/世界來模擬環繞運行效果。比方說,鏡頭要以一個Y軸為中心繞行,同時也持續地盯著原點看的話,你可以這樣做:

gluLookAt(camera[0], camera[1], camera[2], /* 鏡頭的 XYZ  位置*/
          0, 0, 0,                         /* 看著原點 */
          0, 1, 0);                        /* Y朝上向量 */
glRotatef(orbitDegrees, 0.f, 1.f, 0.f);    /* 繞行Y軸的角度 */
/* ...也許 orbitDegrees 可以從滑鼠拖曳推算出來 */

glCallList(SCENE);                         /* 畫出整個場景 */
如果你堅持一定要在物理上旋轉相機位置,你需要在視圖轉換之前,先對相機鏡頭的位置向量做空間轉換。此種狀況下,我建議你去查考一下gluLookAt()這個函式。

8.070 我要怎樣才能自動推算出剛剛好涵蓋整個物體模型的視角? (我知道 bounding sphere 與 up vector.)

以下的視角系統設定取自 Dave Shreiner 發表的文章:

首先請計算出場景中所有物體的bounding sphere(碰撞球)。它應該會提供你兩個訊息: 球體中心 (令該點為 (c.x, c.y, c.z)),以及直徑 (我們叫它"diam" )。

接著,選定一個值作為近平面zNear。依照一般準則,我們會選一個比1大,但是很接近1的值。所以我們設定如下:
zNear = 1.0;
zFar = zNear + diam;
依此順序建構矩陣 (以平行投影來說)
GLdouble left = c.x - diam;
GLdouble right = c.x + diam;
GLdouble bottom c.y - diam;
GLdouble top = c.y + diam;

glMatrixMode(GL_PROJECTION);
glLoadIdentity();
glOrtho(left, right, bottom, top, zNear, zFar);
glMatrixMode(GL_MODELVIEW);
glLoadIdentity();
這個方法應該會令物體置中,同時視窗合適地包住物體。(這兒假設視窗長寬比是1.0)。如果你的視窗不是正方形,那先如上法計算出 left、right、bottom、與top的值,然後在呼叫glOrtho()之前加入以下代碼邏輯:
GLdouble aspect = (GLdouble) windowWidth / windowHeight;

if ( aspect < 1.0 ) { // 判斷視窗是狹長型還是橫寬型。
   bottom /= aspect;
   top /= aspect;
} else {
   left *= aspect;
   right *= aspect;
}
以上代碼應該可以很合宜地定位物件。如果你還想要操弄物體(例如旋轉它),那你還需要加上一個視圖轉換(viewing transform)。

典型的視圖轉換都應該做在ModelView矩陣上,看起來大概如下:
gluLookAt (0., 0., 2.*diam,
           c.x, c.y, c.z,
           0.0, 1.0, 0.0);

8.080 為什麼 gluLookAt() 故障了?

這通常肇因於錯誤的空間轉換。

假設你在投影矩陣上使用了 glPerspective() 並且給第三、四個參數傳入zNear、zFar,你必須把gluLookAt() 設在ModelView矩陣上,並且將幾何圖形放在zNear與zFar之間才行。

當你試著想弄懂視圖轉換時,最好的辦法就是用簡單的代碼來做實驗。比方說你想盯著一個位於原點的單位球體看。那你要建立如下的轉換:
glMatrixMode(GL_PROJECTION);
glLoadIdentity();
gluPerspective(50.0, 1.0, 3.0, 7.0);
glMatrixMode(GL_MODELVIEW);
glLoadIdentity();
gluLookAt(0.0, 0.0, 5.0,
          0.0, 0.0, 0.0,
          0.0, 1.0, 0.0);

重點是投影轉換(Projection transform)與模型視圖轉換(ModelView transform) 之間的合作。

在這個例子中,投影轉換將視角(field of view)設定為50度,長寬比為1.0。近裁切平面位於眼睛前方3.0個單位,遠裁切平面則位於眼睛前方7.0個單位。這留下了4.0個單位的Z視體距離,有充足的空間含納單位球體。

模型視圖轉換則將眼睛位置安置於(0.0, 0.0, 5.0),並把瞄準點設為原點,也就是單位球體的中心。請注意眼睛位置點與瞄準點之間的距離有5.0單位遠。這很重要,因為眼睛前方5.0單位剛好位於Z視體的中間,就如我們剛剛在投影變換裡定義的。如果呼叫 gluLookAt() 時把眼睛置於 (0.0, 0.0, 1.0),那眼睛距離原點就只有1.0單位。這長度不夠含納整個單位球體,球體就會被近平面zNear裁切掉。

同樣地,如果你把眼睛位置放在(0.0, 0.0, 10.0),那麼距離瞄準點有10單位遠,導致單位球體距離眼睛也是10單位遠,遠遠超過了遠平面zFar的7.0個單位。

如果這令你有點混淆,讀讀OpenGL紅皮書跟OpenGL規格書裡的空間轉換。一旦你弄懂了物體座標空間(object coordinate space)、眼座標空間(eye coordinate space),與裁切座標空間(clip coordinate space) 後,上面的內容應該就會很清楚了。還有,寫小支測試程式來做實驗。如果你在主專案裡頭碰到麻煩,找不到正確的轉換,那嘗試用簡單的幾何圖形跟一支小程式來重現問題,是很好的學習方式。

8.090 我該如何令一個指定的點(XYZ) 出現在場景的中心呢?

最容易的辦法就是 gluLookAt() 了。直接傳入特定點的座標 X, Y, Z 作為gluLookAt() 的第四、五、六個參數即可。

8.100 我在投影矩陣上呼叫 gluLookAt() 後,霧、貼圖、照明就全錯了。怎麼回事?

請看問題 8.030 的解釋。

8.110 我該如何創建立體視圖?

Paul Bourke 彙整了一些關於OpenGL立體視圖的資訊

2011年10月29日 星期六

讀書心得: 朱敬一 給青年知識追求者的信

More about 給青年知識追求者的信朱敬一先生是少數幾位我聽過的中研院院士的其中之一,可惜不是因為他的研究,而是新聞報導上常常看見朱先生的大名。個人粗淺的印象中,此人敢說敢做,意見頗值得一聽,所以偶然在圖書館翻到這本書,就把它帶回來了。本書總共由十封信組成,內容大略可分為兩半,前五封信是個人治學心得,我覺得相當不錯,後五封信則是對學術圈的建議,可能要有志於學術者讀起來才比較有感覺吧。

整本書看完後,我認為朱敬一先生想要對這個高度專業分工,以致於過於狹隘與僵化的社會提供一點反思,用朱敬一先生的話來說就是: 「你如果專注於其中部分領域而一頭鑽進去,當然是好的,但是你若想遊走諸方而觸類旁通,也沒有什麼不可以」。每當我想著「資訊工程是我的專業」的時候,到底是不是替我自己立下了一道牆,阻止我往外看,而失去了一些激發思想火花的機會。朱敬一是社會學家,所以書裡用很生動的例子來說明這種法政經社本一體的狀況,雖然表面觀察的對象不同,但是底下的氣息卻隱隱互通。

書裡舉了經濟學家拉維(Levitt) 作為這類遊走諸方的學者典型。拉維教授的其中一個研究證明,美國各州到一九九零年左右突然犯罪率大幅下降,其實是肇因於十八年前美國最高法院判定禁止墮胎違憲。墮胎合法化後,許多意外懷孕的女人就不用生下「不想要的小孩」,因而抑止了將來潛在的犯罪者的出生。這樣驚奇的研究結論,實在很難相信出自一位經濟學家之手。不過我看過拉維的例子後,我開始有點相信朱敬一說的,廣博的通識教育帶來的不是顯然可見的解題能力,而是「發掘、形成新問題」的能力。這也是許多台灣學生的弱點,解問題一流,但是不懂得找問題。

而想要有這種能力,就要依靠後天的「不住相讀書」,朱敬一改自金剛經的句子說「學子不住相讀書,其功用不可限量」,讀書不該功利的只求「有用」,不帶目的廣泛的讀書,才能成其大用,在大腦裡面埋下知識火種,也許有一天各個不相干的點會突然串起來,另闢蹊徑。這讓我想起賈伯斯的演講,他就是休學跑去旁聽書法課,我們今天才有漂亮字體的Mac電腦。

書中有段話剛好點醒了我最近的一些迷惘,朱敬一說,到了一定年紀之後,就不要再以「我某某還不夠好」的彌補心態來作為學習的動力,因為知識永遠學不完。最好的方式是一腳踏到浪頭上去,讓自己成為前緣浪花的一部份。

其實不管內容的話,聽聽朱敬一閒聊也是蠻有趣的,裏頭有一段兩三頁就簡單的道出社會科學的本質,文字淺顯清楚,相當精彩。對於自然科學、社會科學與人文科學分際探討也很有趣,讓我現在開始想一個問題,究竟我念的本科是屬於哪一方面? 電腦科學固然屬自然科學,不過一腳踏入軟體工程之後,是不是就有很強的社會科學的味道了呢?

2011年9月30日 星期五

遲到的 Amazon Kindle DX 電子閱讀器開箱文

Amazon 網路書店出的電子書閱讀器 Kindle DX,當初我看著機子猶豫了很久,一直無法決定要不要買。直到下定決心買下手後,到現在使用超過半年了,我的感想是「真的很不錯」, 雖然有些小缺點,但是瑕不掩瑜。


Kindle DX vs. iPad

首先,廢話不多說,我以「長時間閱讀」來評分,如果紙本閱讀是滿分10分,而螢幕閱讀是0分的話,那我會給這台 Kindle DX 打 7分,蘋果的 iPad 頂多只有 2 分吧。

這是單單以「長時間閱讀」來打的分數。我用 iPad 看完兩本書,Kindle 則是看完十幾本了,閱讀舒適度確實差很多。

iPad 的閱讀體驗跟螢幕差不多,除了拿在手上比較方便以外,所有螢幕的缺點 iPad 都有,像是背光會給眼睛造成負擔,近距離字的邊緣不夠清晰,太陽下會看不清楚等等。

Kindle 的閱讀感覺則已經 90% 像紙面印刷品,這感覺很奇妙,很難形容,我自己覺是最接近的形容就是「字印在墊板上」,不管怎樣 Kindle 使用的電子墨水技術已經甩開了一般印象中螢幕的閱讀體驗,文字邊緣銳利清楚,而且靠自然光閱讀就是舒服,長篇小說讀一整天都沒有問題。

不過除了閱讀以外,Kindle 就一無是處了,我建議絕對不要有任何一絲想用 Kindle 上網、玩遊戲、或者聽音樂等等的不純妄想,Kindle 的長處就是讀書很舒服,而且是唯一的優點。 相較之下 iPad 什麼都好,但就是讀書不好。事實上,我認為「電子書閱讀器」跟「平板電腦」是完完全全兩個不同取向的產品,除了外觀都是一塊板子之外,本質完全不同。



說起買 Kindle DX 的原因,因為小弟我的本業需要閱讀很多的原文文件,而且沒意外的話今年是我最後一年學生生涯,也是有閒暇可以大量閱讀的最後機會,於是心一橫就買下去了。買到現在,原本打算讀的專業書籍沒讀幾本,小說倒是一本接一本看了不少。orz

接下來就幾個方面來討論一下

螢幕尺寸:  Kindle DX 螢幕是 9.7 吋,大約是B5尺寸。一般開本的PDF檔看起來相當舒適,頁邊會自動切白,但如果是 A4 的頁面如學術論文,看起來就會嫌字太小。

翻頁速度:  按下翻頁鍵到翻頁完成大約半秒鐘,個人覺得還好。最適合 Kindle 閱讀的讀物是長篇小說,一頁一頁地連續往下讀,根本是絕配,但是如果是需要來回翻閱的書,那這個翻頁速度就會有點兒讓人受不了。

電池續航力:  以我平均一天看兩個小時,不打開3G網路的話,三個禮拜才需要充一次電,表現相當不錯,出外旅行也不用帶變壓器跟插頭。

管理電子書:  傳電子書進 Kindle 不需要什麼特殊軟體,只要一條micro USB線接上電腦,就可以像隨身碟一樣把電子書檔案全部丟進去,內容量是4G。可以看pdf,不能看epub,平常我都用 Calibre 這套軟體把檔案格式轉來轉去,蠻方便的。

重量:  有一次我跟我弟搭長途火車,只有站位,他搶走我的 Kindle 後一手扶著欄杆一手拿Kindle 就這樣站著看了兩個小時的絕代雙驕,個人覺得比一本400頁的小說稍重一些。


最後抱怨一些小毛病,Kindle DX 沒有觸控螢幕,所以只能用五向鍵來控制,打字也只能用下面的小小鍵盤,不太方便。Kindle DX沒有內建的中文字體,所以書目選單上的中文書名都是問號,後來我去抓了一個大陸人寫的補丁,才看的到中文書名。

整體來講,Kindle DX 還未臻完美,但是我用起來已經不錯了,我估計下一代 Kindle 電子閱讀器才會完全成熟。我自己則是已經等不及了,受夠揹著重重的書四處跑,還有一大堆書搬家的痛苦,所以搶先買了,給各位參考看看囉。

Kindle DX的盒子

2011年9月15日 星期四

讀書心得: 撒哈拉的故事

More about 撒哈拉的故事初拿起「撒哈拉的故事」時,我心中想著大概是本以沙漠為背景的美麗幻想般的愛情小說吧,有誰會真的費盡千辛萬苦跑去撒哈拉沙漠,在物質極為缺乏的環境下過著刻苦的生活呢? 沒想到這人就是三毛,只因為一個理由「我要認識沙漠」。

「撒哈拉的故事」是三毛與她的丈夫荷西在撒哈拉沙漠旅遊生活的紀實,生活在沙漠很糟糕,至少我看完最後一篇『白手成家』後認為實在很糟,不過在樂觀又開朗的三毛的筆下,撒哈拉沙漠化為一個有趣又不可思議的國度,說著一個又一個異國的故事。

如果不是三毛,我無法想像原來世界上還有這樣子的一群人,還有這等事情,你能想像沙哈拉威人三四年才洗一次澡嗎? 『觀浴記』裡三毛跑去看沙漠女人洗澡,要先用蒸氣蒸,再用石片刮下身上的泥沙,而且沙漠女人不只洗外面,還洗裡面,讓我看的哈哈大笑。『娃娃新娘』 裡則是三毛的一個沙哈拉威鄰居叫「姑卡」要出嫁了,可是她才十歲呀,結婚習俗更是特別,新郎去迎接新娘時,新娘拼命的抵抗,原來才在沙哈拉威人的觀念裡,打得激烈才叫做「好女人」,不掙扎事後會被取笑的。

沙哈拉威人很少受教育,思想沒有邏輯,通常講道理是講不通的。有次三毛要參加晚宴,遍尋不著自己的漂亮高跟鞋,反倒是鞋櫃上多了一雙破鞋子,原來高跟鞋被鄰居小女孩偷去穿了。事後三毛很生氣地跟她理論,小女孩竟然回嘴「生氣,生氣,你的鞋子在我家,我的鞋子還不是在你家,我比你還要氣。」聽見這種話真的是秀才遇到兵,有理講不清,還好三毛是個灑脫的人,笑笑就過去了。

事實上,生活在沙漠真的需要灑脫,老是計較小事肯定活不下去。除了講不清道理的沙拉哈威鄰居,沙漠也有許多危險,書中至少有兩次三毛差點在沙漠裡丟掉小命。但是每一篇故事裡,我都看見一位勇氣可嘉的中國女孩兒,她不屈不撓,以樂觀的心和智慧面對生活中的困難,盡情的玩,盡情的享受生活,像個瘋狂的孩子般,最後甚至布置了一個號稱撒哈拉沙漠裡最美麗的家,連記者都聞風專程前來拜訪,他們的物質生活雖不富裕,但是精神卻很富足。

說到三毛不能不提她的另一半荷西。三毛書裡這樣子描寫『荷西有一個很大的優點,任何三毛所做的事情,在別人看來也許是瘋狂的行為,在他看來卻是理所當然的』,所以當三毛說要去沙漠時,荷西早她兩個月,就先對著撒哈拉沙漠找工作去了,沙漠裡的瘋狂事也總有荷西的一份。人生能遇見這樣的他,既是羨慕,也是感動。

2011年8月29日 星期一

讀書心得: 禮物

More about 禮物在人生中剛剛好的時刻,遇見一本書,提醒我許多已經忘記的事。溫暖的一本小書,簡短的故事,我在圖書館拿著書直接翻完了,卻比長篇大論更打動人心。

剛好我現在的年紀,開始會對以前做的一些事情懊悔,發現人生沒有那麼簡單,對未來又有一些迷惘和擔憂的時候,有時候就會被這些情緒佔用了我大部分的生活。

今天是上天賜與的禮物,這是為何他被叫作 當下(present) 的理由。這本小故事就是禮物,當你覺得事事不順的時候,就專注在當下的好事上吧,不要為過去自怨自艾,學習過去的失敗的經驗,去創造未來。

簡單再不過的事情,或許有點過於理想,幸福感多到漫出來了,重點是,你去實行了嗎?

2011年8月22日 星期一

讀書心得: The C++ Standard Library : a Tutorial and Reference

More about The C++ Standard Library
Effective C++第一條款就寫明「C++是一個語言聯邦。」 這個語言聯邦由四個次語言組成,分別是 C、 物件導向C++、Template C++、以及標準庫 STL。我去年接了大一程設課助教,每週都要上台教 C++,這份苦差事意外挖出不少自己當年學習上的盲點。其中最大的問題就是我對 C++ 的後兩個部分: Template C++以及 STL 不夠熟悉,只好找上這本書來補足這方面的知識。

STL 是一個相當淺明易用的程式庫,這從我以前亂逛 cplusplus.com,糊里糊塗就能隨便抄幾句 STL 來用就可以得證。本書對我的主要幫助不是學會 STL,而是能夠從宏觀的視野來看待整個 STL,了解當初 STL 設計的時候架構上的取捨,引發的優點以及缺點,能讀到這些設計上的觀點我覺得很難能可貴。就好像我以前都覺得 STL algorithm 異常難用,看了書才知道原來 STL algorithms 要搭配 function object 才能發揮威力。各種 Iterator 的錮中差異,也是看了此書後才有全盤了解。

內容上我認為第五章是整本書的核心精華,清楚說明了 STL 三大組件的關係與腳色
(圖片節錄自書上5.1節)

Container 負責管理物件集合,Algorithm 是操作手法,而 Iterator 則扮演此二者間的黏著劑,讓雙方可以透過抽象手法互相作用,不會有過緊的依賴關係,由此可以看出 STL 設計之初軟體架構就相當軟Q。接下來六 ~ 九章是書本的主力內容,分別對Container、Iterator、Algorithm 做專門深入的探討。

第八章 Function Object 我認為是值得一讀的特別章節,因為坦白說 function object 這東西使用上並不直覺 (我一直覺得只有聰明鬼才能想出替 object 加上operator( ) 來當函數呼叫的餿主意 ),但是要靈活地使用STL Algorithm,就一定要搭配 function object 才行。沒有function object,STL Algorithms 就只是彆腳程式庫。第十章之後還有介紹一些C++的其他標準庫,像是字串、I/O、國際化問題等等。

整體來講,這是一本好書,但是有點無聊。本書安排內容的方式是把 STL 各個部分切開來,每部份分配一章,依照主題中規中矩的逐一的細講下去,這樣寫的優點是以後要查閱很方便,想回顧某特定功能時很直接,但是缺點就是拿來當學習書會有點囉嗦,學習之初較易見樹不見林。不過書名就明顯寫了「a Tutorial and Reference」,除了拿來學習還可以當 reference 用,那難免有點這類弊病。

附帶一提這是德國人寫的英文書,所以文句很容易理解,幾乎沒有複雜難解又充滿詩意的句子,蠻適合當作練習閱讀原文書的材料。

相關文章連結
The C++ Standard Library讀書筆記:  Function Object

2011年8月21日 星期日

C++ Standard Library 讀書筆記: Function Object

我讀 C++ Standard Library: a Tutorial and Reference 後的筆記,主要內容來自 5.9小節,整個第八章,以及一些我自己的感想。

STL Algorithms

C++ STL Algorithms 裡一系列操作容器的函數,我一直以來都覺得這系列函數異常的難用。例如萬年範例 -- for_each 逐一打印容器的元素:
void print_int( int i ) {
    cout << i << endl;
}

for_each(v.begin(), v.end(), print_int); //逐一印出元素

乍看之下簡潔,但是這 for_each 有個致命的缺點,就是沒辦法傳入額外參數。例如我想對集合內的每個數值都加上一個固定值,用 for 迴圈再直覺不過:
int value = 5;
vector<int>::iterator it;
for(it=v.begin(); it!=v.end(); ++it)
    *it = *it + value;

這麼簡單的程式,想要改寫成for_each版本,馬上碰壁:
void add_value( int & i ) {
    i = i + ???;  // add something?
}

int main() {
    vector<int> v;
    for_each(v.begin(), v.end(), add_value);
}
問號的地方只能放常數或者全域變數,而兩個選項都很爛,我真正想要的是從 main 裡面傳入一個變數。所以很長一段時間我把 for_each 封印起來,乖乖自己寫 for 迴圈。

Function Object

直到最近,我才明瞭到 function object 可能是這個惱人的問題的答案。

所謂的 function object 就是一個object,但是實做了operator() 。它實際上是物件,但可以當作函數來呼叫。要發揮整個 STL Algorithms 的威力,就一定要瞭解 function object。萬年打印範例用funciton object 來實作就會長這樣子 :
class PrintInt{
    void operator() (int i) const {
        cout << i;
    }
};

for_each(v.begin(), b.end(), PrintInt());

PrintInt 就是一個 function object,它有實作operator()。 我們可以宣告一個物件變數 PrintInt p;  對他做好像函數呼叫的動作 p(); 而此時實際上呼叫的是 PrintInt::operator() 這個成員函數。 function object 最大的好處就是裡面可以定義成員變數,維護內部的狀態,而一般的函式做不到。我們回頭拿它來解決剛剛的惱人問題,就可以明白我在說什麼。這兒定義了一個很簡單的小物件AddValue,因為AddValue有實作operator() ,所以它是一個function object。
class AddValue {
    int value;
public:
    AddValue(int v) { value = v; }
    void operator()(int &i) { i = i+value; }
};

int main() {
    vector<int> v;
    for_each(v.begin(), v.end(), AddValue(5));
}

把AddValue物件當作參數傳入, 此時 for_each 針對集合元素的每次 function call 實際上是呼叫 AddValue::operator() ,而我們希望加上去的固定值,被當做 function object 的成員變數存起來了。這樣就巧妙的解決了額外參數的問題。

AddValue add10(10), add30(30); //建立許多function object在不同狀況使用
for_each(v.begin(), v.end(), add10);
for_each(v.begin(), v.end(), add30);

求平均值

「求平均值」是比較進階的例子,用 for_each 來計算整數集合的平均值。我們利用了 for_each 最後會回傳該 function object 的特性,把元素的總和(sum) 跟元素個數(num_element) 都紀錄在的function object的成員變數中,最後取平均值 :
class MeanValue {
    int sum;
    int num_element;
public:
    MeanValue() { sum = num_element = 0;}
    void operator() (int i) { sum += i; num_element++; }
    double value() { return (double)sum / (double)num_element); }
};

int main() {
    vecter<int> v;
    MeanValue m = for_each(v.begin(), v.end(), MeanValue());
    cout << m.value();
}

Function Object的優點

Function Object主要有三個優點
  1. Function Object 比一般函數聰明,它可以維護內部的狀態,記錄呼叫過程中發生的事。
  2. 通常 Function Object 的效能比函數指標好,因為比較容易最佳化。
  3. Function Object 可以當作 template 參數使用,一般的函數不行。

預先定義好的Function Object

除了自己寫 function object 以外,STL已經定義好了一系列常用的 function object 。這裡舉兩個簡單的範例,欲知詳情可以參閱 C++ Reference "functional"
int myint[] = {20,30,10,50,40};
vector<int> v(myint, myint+5);

sort( v.begin(), v.end(), less<int>() ); //排序由小到大
sort( v.begin(), v.end(), greater<int>() ); // 排序由大到小

remove_if( v.begin(), v.end(), bind2nd( greater<int>(), 40)); //移除所有大於40的元素

2011年7月31日 星期日

讀書心得: 天涯。明月。刀

More about 天涯明月刀(上)小李飛刀系列雖然有好幾部,但其實小李探花李尋歡只在第一部「多情劍客無情劍」裡有出場,承接故事的「邊城浪子」講的是小李飛刀傳人葉開,和他的好兄弟傅紅雪糾葛不清的故事。邊城浪子之後,故事就叉開成兩條支線,「九月鷹飛」裡葉開出場,「天涯明月刀」的主角就輪到傅紅雪了。

據聞「天涯明月刀」是古龍的實驗性作品,曾經被罵得很慘,所以我剛開始讀的時候格外戰戰競競,以為會讀到什麼驚人之筆,結果讀完之後反而覺得還好嘛,古龍寫小說不都是這個調調嗎? 喜歡就會喜歡。

在「邊城浪子」裡我第一次接觸到傅紅雪這個角色,還挺討厭他的,但是「天涯明月刀」裡面,我對他的印象有改觀不少,我其實很高興看到傅紅雪終於有了一點人性,不再只是個被復仇驅使的機器人。 第十一回「明月何處有」傅紅雪冷冰冰地對卓玉貞說:「這是你第一次看見我的刀,也是最後一次。」,要他亮刀簡直像要他的命一樣,但是到了下一回「生死之間」,傅紅雪不只拔出刀給卓玉珍看,還拿來削人蔘,挖石頭,刀鋒崩出了三個缺口。這是整個故事裡我最喜愛的一個轉折,能讓一個人的個性在這麼短的時間之內徹底改變,是因為傅紅雪當爸爸了。但是故事的衝突就在於他才剛迎接新生命的出生,就面臨整家人被埋在地底下的困境,我認為這是傅紅雪第一次重新思考他的人生意義,以前他的人生就是他的刀,刀是用來殺人的,但是這次傅紅雪看著手裡的刀,聲音中充滿痛恨說:「這是殺人的利器,不是救人的。」巧的是,若刀沒有崩出缺口,他們也不會被燕南飛發現,傅紅雪的改變救了他們自己一命。

然而,就是傅紅雪做出了這麼大的犧牲轉變,接下來的背叛才會更加痛苦與殘酷。一個女人,使得傅紅雪的刀又淪喪為殺人的刀,而另一個女人,使殺人的刀又變回救人的刀,這段的曲折也寫得很深刻,礙於劇透我就不明講了。

我喜歡「天涯明月刀」打鬥場面多,傅紅雪的刀拔不停,很爽快,而且打的精采,不像邊城浪子廢話一堆但是死都不拔刀,看到快睡著。

2011年7月25日 星期一

讀書心得: 邊城浪子

More about 邊城浪子(上)精品集古龍很喜歡寫廢話,例如這樣:『只有一種人不會說話。』『那就是死人!』,一句話硬要分好成幾句來講的廢話,有時候反而會有一種曲折的效果。但是古龍的文風,發展到某個偏執的方向,大概就會變得像邊城浪子一樣。又臭又長,太多陰謀,太多廢話,讀得很累。

邊城浪子,說的是傅紅雪的復仇之旅,但是看完整本書之後,我卻對這個腳色哭笑不得,因為傅紅雪怎麼看都像一個笨蛋。傅紅雪只是魁儡,被周圍的眾人耍著團團轉,傻傻的追著他心目中的仇人。而且劇情一直不斷重複,傅紅雪陷入危機,葉開跳出來出來救他,傅紅雪快要殺錯人了,葉開跳出來點醒他,如此無窮迴圈,所以我覺得傅紅雪是笨蛋。但是另一位主角葉開,我就更搞不懂他了,他好像什麼都知道,但偏偏又什麼都不講,放任事情發展,表現很平面,從頭到尾就是「出一張嘴」葉開,真是愧對小李飛刀傳人的名號。

說到劇情,前半段的萬馬堂內鬥風雲,我覺得不錯,根本可以獨立成一個緊湊的故事了,反而走入傅紅雪的主線劇情後拖泥帶水,可能我對於復仇這檔事沒什麼共鳴吧,打得又不精彩。直到最後一一揭開真相時,我已經沒有看到真相的興奮,只覺得很疲倦,陰謀跟懸疑是古龍的長項,但是邊城浪子陰謀實在太多了,我猜傅紅雪應該比我還疲倦,終於可以結束這堆亂七八糟的事情了。讀到結局時葉開鬆了一口氣,我也鬆了一口氣。

讀書心得: 多情劍客無情劍

More about 多情劍客無情劍最近突然開始瘋狂地看古龍,不知道為什麼一本接著一本的看。講到古龍難免要跟金庸比較一下,不過不是因為我是什麼很厲害的武俠評論家,因為在下我看過的武俠就只有金庸跟古龍兩位而已,哈哈。

我自己感覺,如果用食物來比喻這兩位名家的話,讀金庸的作品就像吃一桌豐盛的大餐,書裡滿滿的人物流派、武功招式、歷史題材,有各樣不同的味道可供品嘗。但是古龍不一樣,古龍的作品味道沒那麼多元,讀起來感覺總是澀澀的又有點苦味,講的是氣氛,內容是人世的無常,大概就像喝酒的感覺吧,雖然我自己還不太明白喝酒的趣味。

有時候一本小說寫得太好看,感想反而難以下筆,因為佳作天成,各方面都是不多不少剛剛好,只好隨便亂聊。到目前為止看完的小李飛刀四部曲,分別是「多情劍客無情劍」、「邊城浪子」、「九月鷹飛」、還有「天涯明月刀」之後,還是覺得以李尋歡為主角的第一部多情劍客無情劍最好看。

在多情劍客無情劍裡面,所謂江湖上的名門正派幾乎無一例外都被描寫成道貌岸然的偽君子,古龍很喜歡使用這種背景設定。明顯的例子如第七章「誤傷故人子」裡,有名的秦重秦大俠為了救自己的兒子縱人行兇,李尋歡酸了兩句:「秦大俠倒也不必太謙,只不過,若在下殺了人,便是冷酷毒辣,閣下殺了人,便是替天行道了。」「今日這孩子若殺了在下,日後傳說出去,必然不會說他是為了要搶大夫而殺人的,必定要說他和秦大俠又為江湖除了一害,是麼?」剛剛好把此種表裡不一的兩面醜態揭的一清二楚。一片灰暗中,反而襯托出李尋歡的真誠率性。而例不虛發的小李飛刀,就儼然化為劃破黑暗的正義化身,出手一刀,必大快人心。

但是另一方面,李尋歡這個腳色本身卻有著矛盾,與林詩音、龍嘯雲理不清的關係,也註定李尋歡這人個性有點彆扭,看自己輕如鴻毛。背負著過去的深重罪惡。一切的悲劇,追溯到最後都是李尋歡自己年輕時犯下的錯,,又是個酒鬼跟浪子,所以李尋歡這腳色充滿衝突,讓人又愛又恨,第五十三章「騙局」龍嘯雲的心情剛好道盡了這種無奈。「人生本就充滿了矛盾,任何人都無可奈何。」

另外書中有個角色我想特別提出來講一講,書中這樣形容「她看來如仙子,卻專門帶男人下地獄。」據說古龍嗜酒嗜色,讀完小說後我完全相信這是事實。因為「傾國傾城」的林仙兒幾乎差不多要把整本書裡的英雄豪傑都要傾光了,而且如果真有女人這樣對待我,我保證一定自己乖乖跳進她的網子裡。古龍的確很了解什麼樣的女人最能令男人拜倒石榴裙下。而且細細一想,書中發生的各種事件插曲,有一大半是因林仙兒而起,表面與李尋歡平起平坐的對頭是上官金虹,但背後的大魔頭、興風作浪的是林仙兒阿。

古龍寫短片段寫得很好,就我認為比長篇架構要亮眼得多。像是「多情劍客」阿飛的出場橋段,前後呼應,讓我拍案叫絕。孫小紅與孫老頭說書一搭一唱,還有孫小紅跟李尋歡的文比拚酒,都是讓我回味再三的橋段,餘韻不絕。

2011年5月23日 星期一

讀書心得: 如何閱讀一本書

More about 如何閱讀一本書
「如何閱讀一本書」就像書名一樣,一本關於讀書技巧的書,不過這裡的「閱讀」兩個字有特別的意義。

我打個譬喻,在台灣爬山是不錯的運動,全家大小一起去風景區走上一個早晨,呼吸呼吸新鮮空氣,是爬山。但是一位專業的登山者,經過周密規畫後,全副武裝的的去挑戰台灣百岳,也是爬山,兩個爬山名詞一樣,但是意思顯然不一樣呀。

這兒也是,閒暇時看看雜誌打發時間是閱讀,挑戰大部頭又難懂的磚頭書也是閱讀。作者開宗明義就寫『這本書是為了把讀書當作是增進理解能力的人而寫的』,用我的話來理解,就是一本讀書界的喜馬拉雅山登山技術指南吧。

作者把閱讀分成四個層次,由低而高分別叫做 -- 基礎閱讀,檢視閱讀,分析閱讀,綜合閱讀。不同的時機要用上不同的閱讀技巧。第一層的基礎閱讀就不必說了,總要先看懂句子才能說其他閱讀技巧吧。第二層的檢視閱讀,目的是教你使用很短的時間,判斷是一本書值不值得繼續深入的技巧。到了第三層的分析閱讀,就是我們俗稱的精讀了。而第四層綜合閱讀的技巧,已經超越單一本書的範圍,進入一整個主題領域的研究了。

我認為分析閱讀是全書最精華、最有價值的部分,分析閱讀裡作者總共提出了16條明確可執行的步驟,告訴你如何把書扒皮拆骨,再加上X光裡裡外外都看個透徹。

怎樣才算讀懂一本書呢? 這個問題不好回答,至少本書訂出了一個相當高的標準。看懂一本書必須抓住三個要點,第一個是從架構方面,能掌握整本書的骨架,第二個是詮釋,能清晰的了解論點的發展,還有支持論點的理由。最後是批判思考,能公正地說出書本好與不好的地方,有憑有據。

雖然本書的目的是教你征服超出理解範圍的書,但很不幸,本書也是一個必須征服的山頭。我第一次遇見這本書後,前後總共挑戰了三次,一直到最近這次才敢說從頭到尾看懂了。我覺得這本書難讀主要原因是例子太少,特別是分析閱讀後半部,論述完整,不厭其煩,但是就是例子不夠,空有原則卻無處施力。後來我只好一邊讀分析閱讀的原則,一邊就把原則應用在當下閱讀的段落本身,來回好幾次才抓到條理。這算不算是作者的陰謀阿?

以前的我是那種書看完之後心得永遠只有兩句,很精彩很好看,或,很有道理,但是要我說出更具體的理由就張口結舌的人。因為以前我習慣用海綿思考,把書的內容當知識一直往腦袋塞。但是現在我了解這不夠,做為一個負責任的讀者,要時時不斷的對書提出問題,為什麼作者要這樣寫? 這樣寫有什麼意義? 這就是書裡強調的主動閱讀的精神,閱讀不應該只是被動的吸收。

最後跟大家分享四個問題作為結尾,這是「如何閱讀一本書」裡強調一位主動負責的讀者,一定要回答的四個問題。而現在這份心得,也就是我回應這四個問題的答案囉。
  1. 整體來說,這本書到底在談些什麼?
  2. 作者細部說了什麼?怎麼說的?
  3. 這本書說得有道理嗎?是全部有道理?還是部分有道理?
  4. 這本書跟我有什麼關係?

2011年5月22日 星期日

讀書筆記: Art of Programming Contest for uva 開始解題之前的提醒

第一章主要是給打算要進入程式競賽的人一些小提醒。
關於解題
  • 新手一開始最好先挑簡單的問題解,並想辦法用短時間快速解掉。
  • 如果花了很多時間也不要氣餒,你只是練習的還不夠。
關於程式
  • 只挑"一個"語言深入鑽研,透徹了解該語言的各種細節,讓它成為你的武器。
  • 高手解題時,思考和規劃會先用掉 45% 的時間,而最後的 45% 時間用來測試和除蟲,實際上只用10%的時間 coding。
  • 學會用 I/O 轉向,就不需要每次都浪費時間用手輸入測資
  • #ifndef ONLINE_JUDGE
    freopen("INPUT_FILE", "r", stdin);
    freopen("OUTPUT_FILE", "w", stdout);
    #endif
    
關於算法
  • 不要只滿足於一個解法,盡量嘗試用多種不同方法來解同一題。這樣你才有機會比較不同演算法之間的差異,或碰著原本不會遇見的錯誤。
  • 演算法是一串解決特定問題的步驟,多學學各種不同的演算法。
  • 比賽時盡量選最簡單的演算法,並且平時作熟,比賽的時候沒有時間設計複雜的演算法。
  • 現在的電腦很快,迴圈跑個一百萬次也不需要多少時間的,不要斤斤計較小地方。
把程式寫的簡明
  • 少用複雜的程式語句、少用動態分派記憶體、少用指標。
  • 把每個變數的名字都命名清楚,像 Right_Most ,不要用縮寫 rm。

2011年5月8日 星期日

讀書心得: 父親的最後30堂哲學課

More about 父親的最後30堂哲學課
想接觸哲學,卻又對哲學一竅不通 ,所以找上了麥田出版的「哲學小徑」系列,只因為哲學小徑系列序文的一小段話打動了我 ---「 內容艱澀的書我們不出版,法國思想家蒙田曾說:『艱澀是學者用來變把戲的銅板,目的就是為了避免洩漏它們徒勞無功的研究』」太好了,打算一本接一本的看下去。

「父親的最後30堂哲學課」作者是一位哲學教授。既然老子是念哲學的,女兒自然也不能太漏氣,於是父親寫了30封信給尚在念國中的女兒,打算循循善誘,誘拐女兒跳入哲學坑。每一封信都具體而微的介紹了一個哲學主題,字裡行間流露出父親對女兒滿滿的溫暖,對象是國中生,內容也很淺白。

「該怎麼念哲學?」本書提到自古以來解答分為兩派 ,一派認為應該從哲學史開始,另一派認為必須從辯論與論證開始。於是本書取其中庸,書裡有一條脈絡是走哲學家路線,介紹他們的生平以及重要思想,從古希臘哲學家蘇格拉底、柏拉圖起,一直到近代哲學家笛卡耳、康德。另一條脈絡是走思辨路線,直接探討自由、宗教、正義等讓人想破頭的問題。

我讀完後覺得有青少年哲學概論的味道,每封信都短短的,每個東西都談一點,但是談不深。至少整本書走完之後,對哲學有一個很淺的輪廓的了解,以後看到哲學名詞或人名不會霧煞煞。但是深度只能是走馬看花,沒辦法有系統的辯證或是思考。

書中一個令我印象深刻的主題就是「自由」,跟我以前讀「QBQ」的觀念不謀而合,自由的意義就是一個人意識到自己有權選擇,並且為自己的決定負責。我舉個例子,學生抱怨「我很想學好C語言,但是都是老師教的太爛我才學不好。」 ( 這種人不少XD ),但是其實學生應該明瞭自己有選擇學習方式的自由,如果真的很想學好C語言,學生可以選擇向老師反映、自修、請教學長姊,或者擺爛給他當掉,不管哪種方式,都不能把責任全部推到老師身上。簡單講,老師教不好,你就必須被迫接受C語言很爛這個事實嗎? 不,學生可以選擇,選擇自學補救或者擺爛,當然你選了自學補救,就必須承擔玩樂時間減少的事實,不管哪個,都是學生自己選的,而且選了你都要為自己的C語言能力好或爛負責,同時付出應付的代價。所以書裡說『自由的最高形式在於﹔清楚明白地接受一切不可避免之事』。

2011年5月3日 星期二

讀書心得: 看懂世界經濟的第一本書

More about 看懂世界經濟的第一本書
瞄到書本的副標題「今天起不再怕看國際財經新聞」,我心想有這麼神? 連我這個經濟零分也行嗎? 看完之後,還真的有點神。

本書的定位是世界經濟的入門書,收錄主題大略分為五大方向,貨幣、能源、糧食、全球化、新興國家。每個主題都用簡短的文章,言簡意賅的解釋了背後的脈絡,對我這個經濟門外漢,算剛剛好容易吸收的難度。

本書的每個主題都以一則新聞時事作為切入點,通常是 2008 年的新聞,比方說最有名的「美國次貸風暴」,接著以這則新聞為基礎,先補足讀者必須了解的基本知識,例如次貸是什麼? 次貸為什麼會出現? 最後才解釋整個次貸對世界的影響。

每篇主題都是這樣三個部分組成: 新聞時事 -- 基本知識 -- 後續影響,讀來相當清楚。而且因為相關事件或多或少都曾經在新聞上瞄過,相當親切,常常有有「哦~原來之前那新聞是這麼回事」的感覺。

比如說我從這本書裡面理解的次貸,什麼是次級房貸? 就是用比較寬鬆的標準把房子賣給低收入,原本買不起房子的人。那銀行怎麼敢把錢借給可能還不起貸款的人呢? 因為當時大家都相信「房價會不斷上漲」,所以萬一未來還不出錢,只要把房子賣掉就好了。其實到此為止,就已經有危險了,次貸有很高的機會收不到錢,而房價也不可能無限上漲。於是銀行把收錢的權利,包裝成證券商品賣出去,流通到全世界。而且經過銀行巧手混拼,證券不但看不出來風險,還拿到很高的信用評價。直到某天終於房價泡沫,碰一聲,全世界都被炸到。

因為作者是日本人,所以書裡許多利益觀點從日本為出發點去探討。不過有一點要注意,談到台灣的小段,都是出版社自己另外附加進去的內容,並非原書的內容 ( 下面偷偷印一行小字【出版社附加內容】,太奸詐了...)。

世界經濟入門書嘛,我一直認為能把困難的主題寫的淺顯,就是好的入門書。看完後對經濟領域的問題輪廓,還有重要議題,心中大略有的底,至少不像以前看經濟新聞如有字天書一樣了。

2011年4月5日 星期二

讀書心得: 隱身魔鬼

More about 隱身魔鬼

書名: 隱身魔鬼 (不知道為什麼"魔鬼"兩個字在chrome上面顯示不出來,就容我加個書名吧)

讀完「密碼」之後,老實說我馬上就把「隱身魔鬼」排入了待讀清單之中,原因當然就是因為這對有趣的小夫妻: 湯米與陶品絲。不過密碼裡頭湯米與陶品絲已經是有三個小孩的老夫老妻了,而隱身魔鬼裡面,湯米跟陶品絲甚至還沒有在一起呢。

湯米與陶品絲兩位天不怕地不怕的年輕人,成立了一個宗旨是「天底下沒有什麼不能幹(只要有錢)」的青年冒險家公司,誤打誤撞地捲入了一樁嚴重的國際政治陰謀中,莫名其妙地成為情報幹員。聽我這樣說,應該就可以感受到這系列跟白羅系列不太一樣,有湯米與陶品絲的故事總是充滿歡樂派,故事線依然維持克嬸嬸拿手的懸疑緊張,但是年輕人生性樂觀,比起白羅那個死老頭子,氣氛就是輕鬆。

整個故事主線都圍繞著兩個問題打轉: 珍。芬恩到底在哪裡? 還有,誰是布朗先生? 同為終極的隱藏反派,我覺得這位布朗先生塑造的比四大天王裡的李長彥要好上太多了,這位布朗先生真的很厲害,真有深藏不出,但是全局都掌控在他手裡的感覺,沒有人知道這位布朗先生到底是誰,但是他卻多次親自出馬,完成關鍵任務後悄然身退。

以下有點劇透,布朗先生的謎團在那位某某夫人昏倒之後,其實就很明顯了,可能性只有二個,而且照克嬸嬸的心理個性推理法,答案幾乎是呼之欲出。接續的故事情節雖然拼命地往反方向誤導,但是我心裡最深處就是覺得另外一位可能性太低。

最後不能免俗地經歷患難之後發現真情,把湯米與陶品絲送作堆,老梗但是讀者就是吃這套阿,我等不及要預約下一本啦。

2011年4月4日 星期一

不再貼完整的 ACM 程式碼囉

Blog 之後都不會再貼出完整的解題程式,原有的程式也會慢慢修正成只提供關鍵片段。

題目寫稍微多一些之後,我發現赤裸裸地丟上程式碼,用處比我想像中要小的多了。為什麼呢? 因為我自己都不會去看別人的程式碼呀,不是說讀程式碼沒用,如果一隻程式沒有遵循良好的規範,又沒有加上註解的話,那我盯著十秒左右發現無法理解就會放棄了。以我自己的經驗,分享解題的想法或者給一個有用的測資,對解題者幫助往往大得多了。

寫 ACM 的樂趣不就是那徘徊在TLE、RE 與 WA 之間的痛苦糾結嗎,我分享 ACM 題目的本意是要人享受 ACM 的樂趣,不是順了抄襲者的意呀。

2011年3月29日 星期二

UVa 594 One Little, Two Little, Three Little Endians.

解題背景

這題是傳說中的Endian問題。我們都知道int占用4 bytes,但是很神奇的這 4 byte 在記憶體中的排列方式並不固定,分為兩派,一派是以 Intel 為首的 little-endian,另一派是網路傳輸使用的 big-endian。

我用例子來說明,有個變數: int x = 11112345; 如果我們從記憶體的角度來看這個變數x,也就是轉換為二進位bit來觀察,那麼會看見以下兩種狀況:

變數 x 的四個 byte 在 big-endian 的機器上做如此排列
00000000 10101001 10001111 10011001
但是在 little-endian 的機器上,卻以這樣的方式儲存
10011001 10001111 10101001 00000000

兩者byte擺放的順序恰好相反,若一個不小心,就會解讀為完全錯誤的數值,因此 Endian 一直是計算機系統必須處理的問題,這兒有個連結談到Endians的歷史由來。本題就是要做 endian 轉換。

解題策略

C語言可以把 int 當作 char array 來操作,髒,但有效。
int big, little;
char * plittle = (char*) &little;
char * pbig = (char*) &big;
pbig[0] = plittle[3];
pbig[1] = plittle[2];
pbig[2] = plittle[1];
pbig[3] = plittle[0];

閒聊

感謝蔡神的大一計概。

2011年3月27日 星期日

讀書心得: 底牌

More about 底牌這整本書,攏系克莉絲蒂的陰謀啦~。

我認為克莉絲蒂的拿手好戲就是在極為有限的場景跟人物裡,以縝密的邏輯創造出意想不到的發展,像東方快車謀殺案的場景只有一個車廂,尼羅河謀殺案的場景只在一艘輪船上。這次「底牌」更是把這拿手好戲發揮到淋漓盡致。

「底牌」謀殺案發生在一個小晚宴上,扣除被謀殺的晚宴主人,參加晚宴的八位來賓,正分坐兩張橋牌桌捉對廝殺。這個克莉絲蒂精心設計出來的場面,就在八位來賓的身份,非常剛好,對半兩分,四位是偵探,另外四位則是嫌疑兇手,而且我覺得最該死的一點是,克嬸嬸非常公平(有點刻意)的給這四位嫌疑犯平等的地位,不但都有動機,下手的機會差不多,同時這四位嫌疑犯各有一段不可告人的往事,掌握在死者手中。

克嬸嬸在一開頭的作者的話就寫道:一般推理小說只要找出最不可能作案的人,十之八九謎底就揭曉了,他不希望讀者這樣嫌惡的草草讀完書,所以他故意讓四位嫌疑犯站在同一個起跑點上,這樣讀者的奸計就沒辦法得逞了。

除了起跑點相同之外,讀完後回頭一看,整個故事情節根本都已經刻意設計好。劇情圍繞著四位嫌疑犯的過去鋪陳,隨著事實真相一一浮現,我就像一尊克嬸嬸手上的魁儡,先懷疑第一個人,再懷疑第二個人,又懷疑第三個人,到最後懷疑目標繞了一圈,把四個人都懷疑了一遍。可是這麼刻意編排的劇情,一口氣讀下來卻是合情合理,生動流暢呀。

書裡有個有趣的角色我一定要講講,就是四位偵探之一的推理小說家,奧利薇夫人。每當奧利薇夫人對自己的工作,也就是寫推理小說抱怨發牢騷時,我都忍不住想是不是克莉絲蒂在影射自己呢,像奧利薇夫人說的:「我筆下的偵探是個芬蘭人,但我其實對芬蘭一無所知,經常有些芬蘭讀者來信,說他的很多言行舉止讓他們感到不可思議...」,也許克嬸嬸也收到很多比利時人的來信呢。

2011年3月21日 星期一

UVa 106 Fermat vs. Pythagoras

解題策略:

勾股定理 A2+B2=C2,或者叫做畢氏定理,符合公式的數對(A,B,C)就叫一組勾股數 (畢氏三元數)。

題目給一個正整數N,要我們找出兩個答案,第一: 0~N之間總共有幾組互質勾股數? 第二: 0~N之間有幾個數完全不屬於任何一組勾股數? 我舉個例子N=10,那麼0~10之間可以找到兩組勾股數(3,4,5)與(6,8,10),其中只有(3,4,5)一組互質,所以第一個答案是1。再來,3,4,5,6,8,10 都屬於某一組勾股數,完全沒用到的數字是1,2,7,9,共四個數,所以第二個答案是4。

解題關鍵在於如何快速找出一堆勾股數。我想就別折騰了,要解這題就要知道勾股數的通解,單純用暴力搜尋鐵定超時。

維基百科的勾股數條目參考來的通解:
給一個任意數對(X,Y),用以下公式代
A = X2 - Y2
B = 2XY
C = X2 + Y2
得出的A,B,C就是一組勾股數。

若 (X,Y) 恰好互質而且一奇一偶,那麼會得到一組(A,B,C)互質的勾股數。
知道通解後,雙層迴圈跑 (X,Y) 就能找出所有互質勾股數。

找出不屬於勾股數的數字,直接開一個 size=1000000 的陣列來記錄所有出現過的數字 (用array或是bitset都成)。別忘了一點,我們上面只列出互質的勾股數,但是勾股數的任意整數倍也都是勾股數,如(3,4,5) (6,8,10) (9,12,15),這些數字也都必須列入紀錄。

閒聊

我知道Fermat是費瑪,不過標題看很久才發現P先生是畢達哥拉斯orz,對於世界第一的先生(Runtime 0.008秒 by Java),感到由衷的敬佩。

2011年3月15日 星期二

UVa 482 Permutation Arrays

解題策略

題目要求依照第一個陣列的值來排列第二個陣列,照著直覺來寫並不困難。
不過我這兒要提另一個比較狡猾的做法。首先我把第一個陣列叫作pos,pos是一個位置的對應表,告訴你元素排列的新位置。比方說 pos[5] = 3 意思是原本陣列第五個元素應該要移到位置三去。

假如我們翻轉陣列 pos 的 key 與 value,例如把 pos[5] = 3 變成了 pos'[3] = 5,意義上沒有變化: 位置三應該擺放未排列前的舊陣列的第五個元素,但是對程式來說就很方便了,因為我們可以直接依據pos'輸出新陣列,而不需要先經過排序:
for(int i=0;i<len;++i){
    cout << data[ pos[i] ] <<'\n';
}

好了,那現在問題就是題目給的測資是pos,我們該怎麼產生這個key/value翻轉的 pos' 對應表呢 ?
int index=0;
int x;
while( cin>>x ) {
    pos[x-1] = index; //index shift
    index++;

    if( cin.get()=='\n')
        break;
}
其中一個好辦法是把key/value翻轉過來讀取,原本的pos[index] = x 變成 pos[x] = index;。那個x-1是因為題目給的測資是1起算,而C語言陣列是0起算。一旦 pos' 建好,資料讀取完畢後就能直接輸出結果了,中間省去一道排序的工作。

注意

雖然題目說第二個陣列是浮點數陣列,但是最好當成字串來處理,省得應付格式麻煩。範例測資 :
------Input------
2

3 1 2
32.0 54.7 -2

1 3 2 4
.004 +5.0e0 0.000007  3
------Output------
54.7
-2
32.0

.004
0.000007
+5.0e0
3
本題讀取時有許多空行,輸出時也要求每個case「之間」要有空行,要小心處理這些空行。

碎碎念

原本我第一次也是乖乖排序,後來在網上看見這招手法,想說非學起來不可。

2011年3月13日 星期日

UVa 10035 Primary Arithmetic

解題策略

計算兩數相加總共需要多少次進位,用一般大數加法的技巧,數一下進位次數就行了。
//big number a + b
int carry_count = 0;

for(int i=0;i<MAX_LEN;++i) {

    a[i] = a[i] + b[i];

    if( a[i] > 9 ){
        a[i] = a[i] - 10;
        a[i+1]++;
        carry_count++; //數數進位幾次...
    }
}

注意

輸出時要注意名詞的單複數,總共有三個狀況0、1、其他,別忘了判斷喔。
if(carry_count == 0)
    printf("No carry operation.\n");
else if (carry_count == 1)
    printf("1 carry operation.\n");
else
    printf("%d carry operations.\n", carry_count);

碎碎念

輸出句子最後忘了打句號所以吃了兩次WA....

2011年3月12日 星期六

UVa 369 Combinations

解題策略

組合公式: C(n,r) = n! / (n-r)!r!
直接使用組合公式來計算結果就可以了。

必須注意的就是階乘的成長速度極快,14! 的值就已經超出long的範圍,更別說第一個範例測資 C(100,6),100!保證爆掉。所以不能分開計算分子分母最後再相除,要在迴圈中邊乘邊除,壓低計算過程中的數字。

注意

要用浮點數,因為除法會產生小數點。ZeroJudge的測資更嚴苛些,想通過最好把變數精確度提高到long double。而long double與printf溝通的代號是%Lf

碎碎念

偷懶寫的遞迴解法,果然製造 Time Limit Exceeded。自己測了一下,C(34,20)要跑個十來秒,數量級成長很恐怖呀。(汗)


UVa 102 Ecological Bin Packing

解題策略

因為瓶子的顏色總共只有三種:B、G、C,所以直接手動將六種排列方式列出,並一一計算每種方法的移動次數即可。

注意

本題的I/O量非常大,所以使用cin/cout與scanf/printf之間的速度差距很明顯。我解這題用cin/cout的執行時間是0.420秒,換為scanf/printf後的執行時間則是0.230秒,幾乎要快上一倍,cin之效能殺手令我印象深刻。

碎碎念

這題花了不少時間debug,找到bug之後只有囧一個字可以形容,就是totalGlasses進迴圈前忘了歸零,栽在這種智障 bug上...。提醒我以後一定要謹守編程的好習慣: 「永遠在變數需要被用到的最內層區塊才宣告並初始化該變數。」


UVa 100 3n+1

解題策略

很多人的第一題ACM,老老實實按照題目指示做就沒問題。把計算cycle length抽出來作一個獨立的函數的話,程式會清晰很多。

注意

這題有個隱陷阱,就是題目給的a,b值不一定是a小於b,也可能a大於b,十個人裡有九個半都是栽在這裡,請跑跑以下關鍵測資:
1  10 結果應該印出 1 10 20
10  1 結果應該印出 10 1 20


2011年3月9日 星期三

讀書心得: 四大天王

More about 四大天王這次『四大天王』阿嘉莎。克莉絲嘗試了新的故事風格,但看完後我實在沒辦法說精彩。

本次白羅老爹的對手是一個呼風喚雨的跨國地下犯罪集團,而白羅則從一個只會動灰色腦細胞的老頭,搖身一變成了詹姆斯龐德,上山下海,拯救世界。看得出來克莉絲蒂想突破以往的格局,寫一個超大背景的故事。

整個劇情也就像一部動作電影一樣,突發事件一個接一個往主角白羅撲來。每個事件單獨來看都很玄奇,但是整體來看關聯卻很薄弱,好像互不相干的獨立事件。書中說這些行動都是由幕後主使「四大天王」策動,但這樣零散缺乏組織的攻擊行動,我真的很懷疑這四大天王的腦袋能力阿。最讓我吐血的一點,最終隱藏大頭目:四大天王中的一號,李長彥,從頭到尾沒有露過臉,結局突然就自殺了。除了四號來去無形,殺人技巧不錯,他兩位沒有什麼特別作為。整個故事就在誇張不合理的事情與差勁的敵人之中莫名其妙的結束了。

其實看到開場白羅與海斯汀重逢的那一小段,我發現這位克莉絲蒂還是我們熟悉的克莉絲蒂,她寫的人際互動非常有魅力,非常有趣,可惜這次故事不巧挑中了一個不擅長的路線。

2011年2月24日 星期四

讀書心得: 射雕英雄傳

More about 射雕英雄傳
我人生的第一部武俠小說就是「射鵰英雄傳」,當然也是第一本金庸的作品。因為書裡如假似真的歷史背景,還有真實而鮮明的人物,令小時候的我對射鵰著迷不已。現在長大了,重讀射鵰,倒是一樣充滿樂趣。

我之所以喜愛『射雕』,是因為射雕裡頭的人。每個人也許個性南轅北轍,但是都有自己的執著、痴迷,每個人用全心活出自己希望的樣子,反派如歐陽鋒、梅超風等等,壞也壞的迷人。

再來說說郭靖與黃蓉小倆口。小時候還沒感覺,現在我覺得郭靖根本是個臭笨蛋。在我看,從來就只有郭靖負黃蓉,沒有黃蓉負郭靖。如果沒有黃蓉聰慧,郭靖不可能學到降龍十八掌,也不可能找出殺害他師父的真正兇手;不是黃蓉處處幫他,也沒這好狗運能當大俠。但是郭靖心中狗屁忠義過剩,太過迂腐,幾次丟下黃蓉,我都很想往郭靖臉上貓下去。

郭靖是檯面上的主角,但我認為黃蓉才是故事裡最亮眼的角色,不僅個性率真,又聰明,好幾次劇情眼見就要拐進死彎,都是靠著黃蓉伶牙俐齒硬生生給轉了回去,歐陽鋒一代大俠,最後也是栽在黃蓉手裡。黃蓉真的是射雕故事中畫龍點睛的一筆。

這次整本射雕英雄傳都是在新敗家的 Kindle DX 上讀完的,相當過癮,一開始還不太習慣橫書的武俠小說呢。國中之後能有機會重讀射雕英雄傳,也是買 Kindle 之初意料不到的。回想射雕人物,世事無奈,掩 Kindle 長嘆。

2011年2月14日 星期一

讀書心得: 密碼 ( N or M? )

More about 密碼原文書名:N or M ?

讀到一半才發現原來克嬸嬸也寫間諜小說,難怪我一直痴痴的等,就是等不到謀殺案發生。故事是講二戰時期的一對英國情報員夫妻,受命追捕滲透到英國的德國臥底間諜的過程。讀完後我上網一查才知道,這對活躍的夫妻:湯米與陶品絲,也是克莉絲蒂筆下有名的主角組合之一。

雖然說是間諜小說與二戰背景,但是故事其實是在一個非戰區的安靜的鄉下渡假小村展開,一開始又沒有死人,所以氣氛蠻歡樂的。英國情報部門懷疑德國要在這個平靜的小村莊佈置登陸基地,派了湯米跟陶品絲去捕捉間諜。雖說是間諜小說吧,不過鄉下小村盡是一些三姑六婆,爺爺伯伯一堆,要在這些人裡抓出哪個是德國間諜也實在不容易,我看克嬸嬸寫不了軍人,但是寫這種市井小民正是她最拿手的項目啦,劇情當中的爾虞我詐,不錯精彩。

最後容我稍微抱怨一下,結尾段是不公平的推理,陶品絲自己暗藏了一手,而讀者卻沒有獲得同等的線索跟資訊! 所以我跟敵人鬥智鬥到一半才發現,怎麼被擺了一道,真的是暗自不爽在心裡阿,奉勸想看本書的各位就當作冒險故事來看就好了,劇情也的確蠻像冒險故事的。