發表文章

目前顯示的是 2014的文章

Reduce C++ code size

如果拿程式執行速度和code size二者來比的話,我個人會先偏好較小的code size,而不會特別先去關注較快的執行速度,除非效能問題是個問題。很多時候,較小的code size,也意謂著較快的速度。C++程式最讓人經常誤解的一點是,會產生較大的code size,較慢的執行速度是另一個常見的迷思。不過事實上,在使用STL之類的template library或template class時,的確使用不當的話是特別容易產生較大的code size。下面提供幾個簡單的要點,可以幫忙稍減code size。 使用compiler的最佳化選項。一般分為針對執行速度最佳化或code size最佳化。以Visual Studio為例,/O1是minimize size對code size最佳化,/O2是maximize speed對執行速度作最佳化。 避免重複。把common code抽出來,作成function,library或之類的東西。減少source size也減少code size,也減少bug發生的可能性。 砍掉沒用的code。整支程式裡面若是包含了大量的無用程式,除了增加code size外,也可能會隱藏潛在的bug。花點時間,整理一個你的程式把無用的程式碼,短期內或可見的未來內用不到的程式碼清一清。不要過早加入用不到的功能,減少code size也減少bug。 不要include <iostream> ,假如你沒有用使用cin/cout/cerr/clog之類的內建物件。用include < iosfwd> 來取代 ,避免包含使用不到的物件來減少code size。 避免類似型別參數的template類。例如:vector<int> ,vector <unsigned int> 等,這些類別的參數可以替換成同一種型別,例如vector<unsigned int> 。使用同一類別的template容器,也能減少code size。 減少使用exception及RTTI。沒必要的話,減少使用exception及RTTI也能減少code size。 以上是幾個大方向上,如何減少code size的要點。當然還有一些手法,但都是較細節的小技巧,不一定有什麼幫助。就好像在作最佳

HTML5 互動式象棋譜

圖片
十多年前在舊書攤上挖到寶,發現一本曾經在某處讀到得到高度評價的棋譜”佈局津梁”,雖然只有下集,立刻把它買下來,印象中花了100塊左右,現在倒是漲了不少,可惜的是一直找不到上集...不過和許多買過的書的下場同樣,後來大多變成收藏用,只有有時候心血來潮會把它拿出來翻看。因為這本書的年紀比我大,怕把它給翻壞了,事實上封面皮都快掉了,好像隨時都要碎掉的感覺,所以後來花了不少時間將內容手工輸入電腦建檔。最近因為玩些HTML5的東西,所以順便就把它作成網頁版本,實作一個簡易版的互動式棋盤幫助看譜,順便當作練習題。程式很簡單,倒是花了非常大量的時間在校對棋譜內容改正原書的錯誤,不過因為個人能力有限還是有許多錯誤還沒更正... 這個程式主要在Chrome及Firefox測過,手機版viewport寬限定為320。 ( 玩玩看 ) 整個程式很簡單,因為棋譜格式是制式的,所以只需要利用幾個簡單的re的幫忙,很簡單的可以用來找出那一段是文字那一段是棋譜,然後再parse出棋譜內容走步。基本上棋譜還是以字串方式作處理,只要棋譜格式及內容沒有錯誤,都能正確演示。有任何顯示錯誤,則表示棋譜格式或內容有誤,因為我並沒有多作錯誤的檢查。 實際實作時在Chrome及Firefox有二個地方需要特別注意。 Firefox不支援innerText的用法,需改用textContent。實作上可以簡單以a = p.innerText || p.textContent解決。 Firefox不支援mouse event的offsetX/offsetY,我們可以另外包裝一個getOffset的函式解決: function getOffset(e) { if (e.offsetX) { return {x:e.offsetX, y:e.offsetY}; } var el = e.target; var offset = {x:0, y:0}; while (el.offsetParent) { offset.x += el.offsetLeft; offset.y += el.offsetTop; el = el.offsetParent; } offset.x = e.pageX - offset.x; offs

HTML5 WebSocket 多人連線麻將

圖片
之前以java實作了 多人連線的麻將 Client及Server,現在加上使用HTML5 WebSocket的client端,經最新版的FireFox及Chrome測試。這同樣只是一個Demo,由簡單AI打麻將。現在二種不同平台不同網路協定的Client,可以連線對打麻將了。 ; 底下對於WebSocket的Server及Client實作作一個重點摘要。 1,依據 RFC6455 完成WebSocket的Handshake,網路上有很多資料細節這裡就不多作說明。需要注意的是,對於"Connection: "這條內容,Client送給Server什麼,Server就需要回同樣的東西給Client。例如:Chrome送給Server的是" Connection: Upgrade", 而Firefox送給Server的是" Connection: keep-alive, Upgrade"。Server端對Handshake的回應也是以HTTP response形式,之後就可作一般的socket讀寫。 2,Server端的讀寫,需要特別注意的是Payload len的處理:如果小於等於125,那就是原始資料長度;如果等於126,則實際資料長度為接下來的二個byte指定的16bits數字;如果等於127,則實際資料長度為接下來的八個byte指定64bits數字。 3,Client端的onmessage事件中,如果處理的資料是binary,需對傳入的物件作型別檢查。 ws.onmessage = function (evt) {   if (evt.data instanceof ArrayBuffer) {   } else if (evt.data instanceof Blob) {   } else if (typeof evt.data === "string") {   } else {   } }

深奧又愚蠢的問題

前陣子有同仁發現我們的系統中有一支driver會造成系統當機,因為這支driver目前的負責人換我接手了,所以問題就轉到我手上,直到最近把手上幾個比較重要的項目告一段落後才抽空來看這個問題。 一開始先只看一下source,程式看起來不複雜,可能有問題的點都是很簡單易懂的標準程式寫法,看起來沒什麼破綻,看不出問題來。這支driver主要的程式註冊了一個event callback,在這個event callback裡面又會觸發另一個event,而這個event又會讓別支driver註冊的event callback執行,然後啟動一個service。看起來好像很複雜,其實並不複雜,就把它當成只連續call了幾次function就行。 我把driver打開執行看看,果然在我的環境也會發生系統當機的問題,是可以複製的問題,所以不是環境平台不同的問題。再把這支driver關閉,果然就沒有系統當機的問題,所以應該很有可能是這支driver造成的問題。接著我試著調整這支driver的執行次序看看,結果發現如果我讓它提早一些執行,結果就不會當機了。是那邊的記憶體有問題嗎?因為發現問題的同仁也說過,我們release的程式裡面,有幾個版本不會造成當機,但有的版本又會當機。現在我調整次序後又不會當機了?看來應該和記憶體有關係,是這支driver前面的driver造成的嗎?我又去看看前面的driver,看起來也是很簡單的程式,完全看不出來有什麼點是有可能會發生問題的。 光是作了以上幾個測試就花了我不少時間,因為我們的系統每次修改程式到重新編譯程式準備好環境作測試就會花不少時間。debug的方式主要是丟除錯訊息,因為這是最便捷的方法,當然也能支援source level debug,只是因為設定太麻煩以致於平常都習慣靠除錯訊息除錯。最後實在不行了,既然已經花了那麼多時間測試了,不如再多花點時間把source level debugger架起來吧。 source level debugger架起來後,我當然直接在driver的event callback裡面下一個breakpoint,然後執行看看。結果發生詭異的事情!第一次執行,程式並沒有中斷,這就奇怪了,我斷點是下在程式必經之路,怎麼不會斷呢?第二次程式是中斷了,但是居然斷在另外一支driver的callback裡面!我比

路徑搜尋之演化論

圖片
我現在要作一個實驗,模擬一個虛擬的世界,這個世界的構造很簡單,是一張10乘10的地圖,總共100個格子所組成。在這個世界裡面,會隨機產生金幣,機率是一半一半,也就是說大約在這100個格子裡面,平均會有50個金幣。還要模擬某種生物,這種生物的生存目的很簡單,就是儘可能的吃金幣,因為這個世界的食物只有金幣。能夠吃愈多金幣的生物就愈能夠生存下來並把它的基因繼續傳播下去。生活在這個世界的生物就把它命名為吃金幣的人...吃金幣的人在這個世界能作的事情很有限,除了吃金幣外,他只能作上下左右四種方向的移動,每次只能移動一個格子。 這個實驗的目的是想辨法找到一個最佳的路徑搜尋方法,讓吃金幣的人儘可能吃愈到愈多的金幣。為了評估吃金幣的人的路徑搜尋方法有多好,需要有一個可以量化的方法。所以就很簡單的設定,如果吃金幣的人每吃到一個金幣就能獲得10分,分數愈高就表示它的路徑搜尋方法愈好。當然也不能讓吃金幣的人任意的作無限次移動,因為這樣一來就沒有意義了,因為吃金幣的人一定可以吃光世界上所有金幣。所以我們要限制移動次數,比如說200次,每200次移動後再來作評分。 我們將會使用基因算法(genetic algorithm),讓吃金幣的人自行進化,得到一個認為最棒的路徑搜尋方法。 基因算法的主要精神是,對於所要解決的問題以模擬生物界物競天擇適者生存的自然法則,讓所摸擬的人工生物自行進化出在模擬世界中的優勢物種,也就是得到所求的最佳解。不過這裡講到的進化這二個字有誤導的嫌疑,實際上這也是大多數人對於進化及演化之間的誤解。進化這二字裡面隱含了方向性,而事實上演化是沒有方向性的,演化是生物對生存環境的適應。生物會演化成什麼樣子,沒有任何的目的性和方向性,這裡面帶有隨機性,主要取決於環境變因。 自然選擇和變異再加上時間是演化的基本原則,所以我們將要模擬的程式也是使用到這幾個基本原則。雖然實際上的細節,和真實世界生物界的演化並不相同,但因為我們利用這幾個演化的基本原則來模擬我們的世界,結果也會得到類似的結果。我們可以看到我們所模擬的吃金幣的人果真在這個金幣世界裡面,慢慢的演化出愈來愈聰明的路徑搜尋方法。而同自然界的生物演化一樣,你甚至無法知道也無法分析它到底是怎麼辨到的。 前面提到這個世界是個10x10的地圖,共有100個格子,在這個世界面裡有會隨機產生的金幣。如果一個格子上

永恆的OLG ~ 2

圖片
把十年前的作品拿出來,試著build看看。其實很早就想這樣作了,這樣作的目的很單純,因為這是一個具體而微的on-line game,可以以它為基礎繼續作研究實驗。

快速組合算法(Fast Combination Algorithm)

在 猜數字遊戲 (電腦猜人) 這篇文章裡,最後提到怎麼從10個數字裡面挑出4個數字的組合的方法。 這個方法很簡單,0x3ff這個數字共有10個位元1(bit),我們可以把這10個位元和0-9這10個數字作一一對應。用一個迴圈來找從1到0x3ff這些數字裡面,有那些數字是包含4個位元1,也就是要找的。例如0xf這個數字,2進制是0000 0000 0000 1111,最右邊4個bit都是1,根據1的位置轉換後變成3210這個數字。同理0x17這個數,2進制是0000 0000 0001 0111也是4個bits為1,轉換後為4210這個數字。依此類推。 這個方法用來選取小範圍數的組合還可以,可是一但數字大了,效能就太慘不忍睹了。例如以今彩539的可能組合為例,全部1-39共39個數字裡面挑出5個,全部共有575757種組合。雖然57萬多種組合看起來不大,但是以上面的方法來找,則要搜尋的迴圈範圍一下暴漲為2^39才能得到這57萬組結果,這是一個天文數字。所以這個方法就不可行了,勢必要使用更有效率的演算法才行。 稍微研究後,很幸運的不到10鐘就讓我找到了一個看來可行的演算法,很快的寫了一支小程式來測試。測試結果果然很理想,以C(39,5)作計算測試,不到1秒鐘的時間就得到正確結果! ; 底下是演算法的概述,同樣以10個數字取組合為例: * 考慮最簡單的情況,作10取1組合 0 1 2 3 4 5 6 7 8 9 10個數字共有10個位置可以放入數字1,從最左邊的位置開始,共有10個位置可選擇,所以總共有10種可能。 用計算組合的公式驗算一下,C(10,1)=10!/1!(10-1)!=10!/1!9!=10 * 考慮10取2的情形 因為第一個1有0-9共10個位置可以選擇,如果第一個1選擇放入位置0,則第二個1有1-9共9種位置可以選擇放入。因為位置0的情況已經考慮過,所以接下來只要往後看不再往前看,需要排除掉已考慮過的位置。接著考慮如果第一個1選擇放入位置1,則第二個1排除位置0和1後還有2-9共8種選擇。依此類推,根據第一個1的位置選擇不同,則有9(p0), 8(p1), 7(p2), 6(p3), 5(p4), 4(p5), 3(p6), 2(p7), 1(p8), 0(p9)種選擇,小括號內的p0-9為第一個1的選擇位置