Thursday, May 29, 2008

[C/C++] Word Separating

  • Word Separating
  • word separating是筆者我在兩年前製作程式語言講義裡的其中一個範例,其中的演算規則不難,主要是善用字串處理,只是整個程式使用了linked-list的結構來撰寫,所以程式碼會長一點。

    Download:sepWord.c

    雖然這只是一個不到兩百行的小程式,但是其中還有一些重要的環節要介紹一下。

    函式的原型如下:

    output():將分離好的單字儲存到文字檔裡。

    delDuplicate():刪除重複以及長度不及的單字。

    initNode():初始化linked-list的node。

    sort():使用改良後的bubble sort來排序linked-list。

    separate():整個程式的核心函式,裡面實做如何分離單字。

    freeList():清除linked-list。

    定義了一個叫做word的structue,裡面包含了兩個變數,keyword是用來儲存單字用的,而next則是結構體指標,指向word這個結構體型態。


    在main()程式碼裡有一行程式(如下圖),這個宣告是特別用在head,tail這兩個word結構體的變數初始化用的,為了要讓後面的sort程式能夠正常排序且不會調動到head,tail這兩個結構體裡的keyword(也就是不要讓任何單字跟這兩個變數內的keyword做交換,否則我們想要留下的單字可能會被放在tail的keyword裡。)這只是筆者我比較習慣的處理方式,處理這類的方法還可以在排序的演算法其他函式上動手腳。

    下圖是改良後的bubble sort,但是有別於一般的bubble sort,這個版本不會有任何for loop,因為linked-list本身就是以指標的型態做串連,所以沒有index可以使用,所以這個時候要善用head,tail這兩個node。(如果看不懂這個sort怎麼寫,姑且可以先跳過。)

    接下來的就是整個程式的核心,separate(),程式碼不長,佔用了30行而已,

    在separate()函式一開始就宣告了一個叫做token的陣列,裡面已經預先定義好要去除哪些字元,但是其中有兩個數字可能會讓讀者困惑,那就是10跟13,這兩個數字轉換成ascii之後分別代表著new line, carriage return,其中以10最需要被過濾掉,否則分離後會有一堆不需要的空白字元。

    宣告完token之後,還要做一些資訊的讀取,例如程式碼157~159是在讀取檔案的byte數,162~163是在動態宣告一個char 陣列,並一次將所有要處理的文字讀取到buffer,這樣的作法會比筆者原先以一個一個字元讀取的方法來得更有效率。

    終於我們要進入最核心的演算部份,我使用了兩個迴圈,外部迴圈(程式碼171)是一直做到整個buffer的最後一個字元,而內部迴圈(程式碼173)是不斷對每個字元去比對我們設定的token,如果比對成功(程式碼174),會接著去比對是否是空白字元或者是跳行字元(程式碼175),如果很幸運的又成功了,這時候我們可以確定程式已經讀到了一個單字,我們要為這個單字做收尾的工作(程式碼176),並且再新增一個node(程式碼178)給下一個單字儲存使用,只是這一個過程式linked-list的型態,所以程式碼177~180之間我們要將現有的單字跟新的node串接起來,否則list 就斷掉了。

    而程式碼183~186是一個特殊處理的環節,程式碼183是在判斷是否已經處理到最後一個字元了,如果是個化同樣也要做收尾的動作,比且跳開這個內部while loop,如果還有字元要做處理,就遞增buffIndex的值,並且將tokenIndex給歸零(程式碼187),如此一來我們就可以繼續從程式碼173繼續做判斷,而不需要離開內部迴圈在繞一大圈進來。

    如果目前要比對的字元跟我們設定好的token字元不符合(例如'a'),那程式碼就會執行到190行,並將'a'這個字元儲存起來,繼續再往下一個字元做判斷,不斷地重複上述的動作直到所有buffer裡的字元都已經分離完畢程式碼就會執行到192行做最後的收尾動作,也許這個時候你會有疑問為什麼程式碼176跟184都已經做了收尾的動作,程式碼192為什麼還要再寫一遍,原因是因為我們文字的結尾很有可能不是要過濾的符號,例如來源文件檔裡就只有一句話"this is a simple program",他最後一個字元是m完全不會進入到程式碼174裡的判斷,所以這個時候我們還要為這種情況額外收尾。

    依照所要分析的文字結構不同,視情況去決定碰到什麼字元要做收尾並且產生新node的動作。

    所以整個文字分離程式概念雖簡單,但是要仔細去設想各種狀況,否則一有缺失就會出錯。

  • Demo

    測試用的短文(article.txt),特別加了許多符號來將句子給複雜化

  • 執行使用的指令:

    • ./sepWord article.txt sepWords.txt 5
    • 其中5代表著小於5個字母的單字都刪除掉。

    輸出的結果(sepWords.txt)

    輸出結果很理想的把我們所要的單字給分離出來,並且依造大小寫與字母給排序好,重複的單字以及不要的字元也已經消除。

    本程式已由筆者重新校正過,我想程式應該是不會有錯誤了,除非讀者您使用了一些違反我程式所設定的token字元結構才有可能分析出不正常的單字。

Monday, May 26, 2008

[C/C++] Borland C++ Compiler Installation

  • Borland C++ Compiler Installation
  • 雖然Borland C/C++ Compiler很少使用,但是還是特別寫出這一篇

    Compiler可以從下面的網頁來下載:

    http://www.codegear.com/downloads

    安裝完畢之後還要做一下簡單的設定,將bcc32.cfg 和 ilink32.cfg這兩檔案放置到"c:\Borland\Bcc55\Bin\"裡,也許你會問這兩個檔案從哪裡來,我們可以自行建立這個檔案

    • 將以下文字存成bcc32.cfg
    • -I"c:\Borland\Bcc55\include"

      -L"c:\Borland\Bcc55\lib"

    • 將以下文字存成ilink32.cfg
    • -L"c:\Borland\Bcc55\lib"

    設定完上面的步驟之後,最後我們還要設定一下系統變數,控制台->系統->進階,在系統變數的地方找一個變數名稱為"path",在他的數值增加C:\Borland\BCC55\Bin; 如此一來你在console底下就可以使用bcc32來編譯。

    以下是Borland C++ Compiler的基本編譯方式,假使我們有一個檔案叫做hello.c。

    • bcc32 -c hello.c
    • bcc32 hello.obj

    簡單透過上面兩行指令就可以編譯出hello.exe的執行檔了。

Monday, May 19, 2008

[C/C++] GCC/MinGW Optimization

  • GCC/MinGW Optimization
  • 一個程式運作的快慢除了取決於系統的硬體環境、演算法設計之外,程式的最佳化也是一個重要的課題,大部分的人常常會忽略掉編譯器的最佳化部份,導致整個程式一經編譯後效能極慢。一個標準的編譯流程如下:

    Source Code->Preprocessor->Compiler->Assembler->Object Code/Machine Code->Linker->Executables。

    所以在整個編譯過程中,一個很大的環節就發生在Source Code to Assembly Language,一個好的編譯器會幫你將你的原始碼轉成最少行數或者最少Machine Cycle的組合語言,以提昇程式的執行或者記憶空間的效能,反之,則會降低程式的執行效率。GCC/MinGW本身提供了5種等級的最佳化,如下:

    • -O0 or no -O option (default)
    • At this optimization level GCC does not perform any optimization and compiles the source code in the most straightforward way possible. Each command in the source code is converted directly to the corresponding instructions in the executable file, without rearrangement. This is the best option to use when debugging a program and is the default if no optimization level option is specified.

    • -O1 or -O
    • This level turns on the most common forms of optimization that do not require any speed-space tradeoffs. With this option the resulting executables should be smaller and faster than with -O0. The more expensive optimizations, such as instruction scheduling, are not used at this level. Compiling with the option -O1 can often take less time than compiling with -O0, due to the reduced amounts of data that need to be processed after simple optimizations.

    • -O2
    • This option turns on further optimizations, in addition to those used by -O1. These additional optimizations include instruction scheduling. Only optimizations that do not require any speed-space tradeoffs are used, so the executable should not increase in size. The compiler will take longer to compile programs and require more memory than with -O1. This option is generally the best choice for deployment of a program, because it provides maximum optimization without increasing the executable size. It is the default optimization level for releases of GNU packages.

    • -O3
    • This option turns on more expensive optimizations, such as function inlining, in addition to all the optimizations of the lower levels -O2 and -O1. The -O3 optimization level may increase the speed of the resulting executable, but can also increase its size. Under some circumstances where these optimizations are not favorable, this option might actually make a program slower.

    • -Os
    • This option selects optimizations which reduce the size of an executable. The aim of this option is to produce the smallest possible executable, for systems constrained by memory or disk space. In some cases a smaller executable will also run faster, due to better cache usage.

    一般來講都用使用-O2 level,得到的效能換比較好,但還是得視你的程式碼的撰寫方向而定。

    Reference:

    http://www.linuxjournal.com/node/7269/print

Sunday, May 11, 2008

[C/C++] __int64 vs long long

  • __int64 vs long long
  • 在一些大數值運算的需求中,我們可能會需要用到長整數的型態(也就是超過4byte能表達的整數),以int64為例,可以表達的signed範圍從2e63-1(9,223,372,036,854,775,807) to -2e63(-9,223,372,036,854,775,808)在各開發環境下的使用方法略顯不同。如下:

  • Visual C++
  • MinGW
  • GCC/G++
  • 輸出結果:
  • 各開發環境下的寫法各有些微的差距,其中以VC的寫法最為簡便,這部份Microsoft實做的很好,使用者不需要花太多心思去思考如何運作。而在linux底下則是使用long long 的型態來宣告,上面所有的程式輸出結果皆如上圖。

Saturday, May 10, 2008

[Flash] 3D Ball

  • 3D Ball
  • Download:3DBall.zip

    對於許多Flash設計者來說,3D設計一直是設計者感到缺憾的地方,雖然到目前為止Flash CS3依舊是2D座標繪圖系統,但我們還是可以透過一些小技巧製造出3D的效果。以下是我的虛擬座標系統:

    我們自行定義了z axis,才足以構成3D Coordinate。

    以下程式片段介紹僅講核心部份,可以看到程式碼35~36是直接對著ball_mc的x,y數值做更新,而z軸則是一個變數,球體的放大縮小由我們自行建立的z軸數值做放大比例依據。解主要的核心程式碼:

    function motion():Void {
    _root.ball_mc._x += x_dir*xSpeed;
    _root.ball_mc._y += y_dir*ySpeed;
    _z += z_dir*zSpeed;
    _root.ball_mc._xscale = ballScale-ballScale/100*50*_z/stageDepth;
    _root.ball_mc._yscale = ballScale-ballScale/100*50*_z/stageDepth;
    if (_root.ball_mc._x>(stageWidth-stageWidth*0.25*_z/stageDepth)-int(ballScale/100*34)) {
    x_dir = -1;
    }
    if (_root.ball_mc._x<0+stageWidth*0.25*_z/stageDepth) {
    x_dir = 1;
    }
    if (_root.ball_mc._y>(stageHeight-stageHeight*0.25*_z/stageDepth)-int(ballScale/100*34)) {
    y_dir = -1;
    }
    if (_root.ball_mc._y<0+stageHeight*0.25*_z/stageDepth) {
    y_dir = 1;
    }
    if (_z<0) {
    z_dir = 1;
    }
    if (_z>stageDepth) {
    z_dir = -1;
    }
    _root.x_txt.text = ball_mc._x;
    _root.y_txt.text = ball_mc._y;
    _root.z_txt.text = int(_z*10)/10;
    }

    可以看到motion()一開始是直接對著ball_mc的x,y數值做更新,而z軸則是一個變數,球體的放大縮小由我們自行建立的z軸數值做放大比例依據。

    接著的if判斷是在更新球體各分量的速度方向,z軸的部份很單純,只需簡單判斷是否超過我們自訂的邊界即可,但是x與y軸必須隨著z軸去更新他們各自的邊界大小。

    最後將各軸的數據輸出到螢幕上顯示即完成我們的motion()函式。

    看完之後你會發現似乎3D立體視覺沒有那麼難處裡,但是別忘了目前只是最基本的球體運動,且參考點座標是固定的,一旦要做切換視角的效果時就不是那麼簡單了。

Wednesday, May 07, 2008

[C/C++] Building DLL with MinGW

  • Buding DLL with MinGW
  • 在windows底下要建立dll檔時通常會使用Visual C++,這裡提供一個使用MinGW的方式來產生dll。

    ==================================

    /* mydll.c */

    使用以下兩個指令將mydll.c編譯成dll檔

    • gcc -c mydll.c
    • gcc -shared -o mydll.dll mydll.o

    ==================================

    /* test.c */

    把編譯好的dll檔連結到我們要測試的程式(test.c)

    • gcc -o test test.c -L./ -lmydll

      執行範例畫面如下:

      上面是一個比較簡便的方式,不只是MinGW可用,GCC也可以透過上述的程式馬來產生library,以下的方法適用於Win32環境下的dll,有需求的人可以不訪學起來。

      ==================================

      /* mydll.h */

      透過__declspec來決定我們有哪些functions或variables要被列為可供動態連結調用

      /* mydll.c*/

      程式的功能很簡單,要注意的是printMsg回傳型態前面並沒有加上EXPORT,如此一來,你就無法透過使用mydll.dll來調用printMsg,只有mydll.dll本身的函式可以使用printMsg函式。

      我們可以透過下面兩個指令來編譯這個dll。

      • gcc -c -D__MYDLL_H__ mydll.c
      • gcc -shared -o mydll.dll mydll.o

      產生完dll之後我們還要測試是否能夠正常運作。

      =========================================

      /* test.c */

      可以透過下面的指令編譯:

      • gcc -o test test.c -L./ -lmydll

      如果將成是碼第5行的註解拿掉將會編譯錯誤,原因如同上面所提的。

      範例輸出畫面如下:

      =================================

      上面的都還只是靜態的連結,動態的連結方式如下:

      /* fib.h */

      /* fib.c */

      /* test.c *

      編譯的過程並沒有什麼差別:

      • gcc -c -D__FIBDLL_H__ fib.c
      • gcc -shared -o fib.dll fib.o
      • gcc -o test test.c

      只是變成dll由test.c裡面呼叫使用。

    Saturday, May 03, 2008

    [Flash] Drawing API: Rose Curve

    • Drawing API: Rose Curve
    • Rose Curve是筆者當初在修微積分的Polar Graph時,心血來潮所寫的Flash小程式。

      Download: rose.zip

      程式一開始一樣要先初始化變數,縱使actionscript 2容許不宣告變數即可使用,但是一旦轉移到actionscript 3裡整個程式格式就不能這樣了。

      在Flash裡面按鈕的狀態偵測必須完全由自己去設計,不然會有重疊movieClip,或者影片速度不均等不正常的問題,進而導致控制失靈。

      在Flash裡面的繪圖座標系統是Cartesian Coordinate,所以要把Polar Coordinate轉成Cartesian Coordinate,本範例畫的是rose curve: r(t)=a*sin(5*t),透過以下的函式做轉換:

      • x(t)=r(t)*cos(t)
      • y(t)=r(t)*sin(t)

      其實本例子只是簡單的運用幾個基本的Drawing API的函式來完成動態畫圖的效果,特過這樣的一個小技巧,你可以使用guideline來完成更複雜的圖形。