Tuesday, November 13, 2012

Word Frequency Counter Using Heap

This is an assignment from our Data Structure class. However, the deadline was passed already, and here I post my code and the report. This may be an example code for heap algorithm.

The original problem of the assignment is to count the word in an article to see the frequency of each word. And show out the first k in the rank.


            Heap is used in this program, so that we don’t have to sort the strings by their frequencies before showing the result.
            There are two main operations for heap in this program. One is “add_if_exists()”, another is “add()”. “add_if_exists()” checks if the new input word is already in the heap or not. If yes, this function adds one on its frequency and bubble up this node so that the heap tree remain correct; if no, it returns false, and the program will call “add()”. On the other hand, “add()” is the function to add new word in the heap, which is not seem before.
            To implement the heap in this program, I built an array of structure nodes. For each node, there is a word (character array) and an integer, which records the frequency of the word.

Program Structure

Pseudo code as below,
while( read one word, exits if end of file ){
            if( input word is empty ) skip
            if( input word exists already ){
                        add input word to the current heap
            add input word as a new node in the heap
while( k times ){
            remove the max node from the heap and show it as the result


  • For adding the new word which is not in the heap yet, we don’t have to reheap, because the new word must come with frequency = 1 which becomes the smallest node in the heap.
  • Time Complexity: say n is the amount of words in the text file, in the worst case (all the n words is not the same), time complexity is O(n2). Most of the time spends on searching if the word is already in the heap or not. However, this can be improved be adding “hash table” in the program, which is not done yet my code.
  • Space Complexity: space used in this code is fixed. Adjust the size in the head of the code to different usage. Depends on the amount of words in the article, and the longest characters in one word.

Program Elements

Functions relates to the heap:
  • add_if_exist() Search the heap array to see if the new input word is already in the heap or not. If yes, add one on its frequency, then reheap and return TRUE; if no, return FALSE. 
  • add() Add the new input word at the end of the heap when it is sure that the word is not in the heap yet.
  • reheap() Recheck the heap tree. If it’s not correct, then fix it.
  • reheap_from()After adding one on the frequency of a curtain node, we bubble up the node to make sure the heap is correct.
  • remove_max()To move the root, we exchange the root with the smallest node then reheap the heap tree. Return the original root node. 
Functions relates to the heap tree in array:
  • int heap_left(int root) {return (root*2+1);} 
  • int heap_right(int root) {return (root*2+2);} 
  • int heap_parent(int child) {return (child-1)/2;}


  • Test on Darwin Kernel Version 12.2.0, GCC 4.8.0. 
  • The test text file is downloaded for the assignment.

  • Testing on school’s Linux machine, FreeBSD 8.3-RELEASE-p3, GCC 4.2.2.
  • The test text file contains 33705 words, which is larger than the last one.


  • To make the program run faster, we can add “-O3” as the argument of GCC, which ask the complier to do some optimisations for speed. Some versions of GCC even offer “-Ofast” selection. 
  • In the future improvement, the searching part, it can be done by using hash table, which tells the location of a word in the heap tree in the constant of time. Just like the “dictionary” in some programming languages, which is not built-in in C.


 * Program    : Word Frequency Counter 
 * Author    : Heron Yang @ NCTU 
 * Class    : Data Structure 
 * Date        : 2012/11/06 
 * By using the heap tree in array, we can calculate 
 * the frequency on words in an article in a short 
 * time. 

#include <stdio.h> 
#include <string.h> 
#include <stdlib.h> 
#include <time.h> 

#define FALSE    0
#define TRUE    1

#define LENGTH    100 
#define NODES    1000000 

 * Structure Declaration 
 * Word_node structure includes the original word, 
 * and its frequency in the article so far. 
struct Word_node{ 
    char word[LENGTH]; 
    int freq; 

int node_ind = 0; 

// Character Operation Related Functions 
int isDigit(char c); 
int isAlpha(char c); 
char toLower(char c); 

// Self-Completed Function Declarations 
int add_if_exists(char *input);
void add(char *input); 
void reheap_from(int child);
void reheap(int root); 
void swap_node(int a, int b);

// Functions for Heap Operations 
int heap_left(int root)        {return (root*2+1);} 
int heap_right(int root)    {return (root*2+2);} 
int heap_parent(int child)    {return (child-1)/2;} 

// I/O Related Functions 
int read_one_word(char *input);
void output_result(int k); 
void output_debug(int k); 
struct Word_node remove_max(); 

// main 
int main(int argc, char **argv){ 

    // setup file reading 
    FILE *fin = freopen(argv[1], "r", stdin); 
    int k = atoi(argv[2]);

    // read the words from file into the heap 
    char input[LENGTH] = {0};
        // if the length is zero, skip it 
        if( !strlen(input) )    continue; 
        // add into the heap 
        if( !add_if_exists(input) ) 

    // output the result here 

    // output time information 
    float elapsed = (float) (clock()) / CLOCKS_PER_SEC;   
    printf("%f sec\n", elapsed); 

    // end here 
    return 0; 

 * Function : output_result 
 * Output the whole result here. 
 * Also, to output the all the same rank nodes, we 
 * have to check if there still have nodes need to  
 * be poped out. 
void output_result(int k){ 
    int t = 0; 
    struct Word_node out; 
        out = remove_max(); 
        t = out.freq; 
        printf("(%s,%d)\n", out.word, out.freq); 
    out = remove_max(); 
    while(t == out.freq && node_ind){ 
        printf("(%s,%d)\n", out.word, out.freq); 
        out = remove_max(); 

 * Function : output_debug 
 * Output the heap for debug purpose 
void output_debug(int k){ 
    int i, t=0; 
    for(i=0 ; i<k ; i++){ 
        printf("(%s,%d)\n", heap[i].word, heap[i].freq); 
        t = heap[i].freq; 
    while(t == heap[i].freq && t){ 
        printf("(%s,%d)\n", heap[i].word, heap[i].freq); 

 * Function : swap_node 
 * Swap two nodes in the heap structure. 
void swap_node(int a, int b){ 
    int t; 
    char t_c[LENGTH]; 
    // swapping frequency 
    t = heap[a].freq; 
    heap[a].freq = heap[b].freq; 
    heap[b].freq = t; 

    // swapping word 
    strcpy(t_c, heap[a].word); 
    strcpy(heap[a].word, heap[b].word); 
    strcpy(heap[b].word, t_c); 

 * Function : add 
 * After making sure that this word hasn't appeared, 
 * add this word into the structure array. 
void add(char *input){ 
    heap[node_ind].freq = 1; 
    strcpy(heap[node_ind].word, input); 

 * Function : add_if_exists 
 * Search the existing structure array, add one on 
 * its frequency if the word is already in the array. 
int add_if_exists(char *input){ 
    int i; 
    for(i=0 ; i<node_ind ; i++){ 
        if(!strcmp(heap[i].word, input)){ 
            heap[i].freq ++; 
            return TRUE; 
    return FALSE; 

 * Function : reheap_from 
 * After adding one on frequency on one node, we have  
 * to bubble up the node to make sure the heap is right. 
void reheap_from(int child){ 
    int root = heap_parent(child); 
    if( heap[root].freq >= heap[child].freq || root <0 )    return; 
    swap_node(root, child); 


 * Function :  
 * Most important part of these program, which rebuild 
 * or check the heap is in the right condition or not. 
void reheap(int root){ 
    int child = heap_left(root); 
    if( child >= node_ind )    return; 
    if( (heap[child].freq < heap[child+1].freq) && 
            (child < (node_ind-1)) )    child++; 
    if( heap[root].freq >= heap[child].freq )    return; 
    swap_node(root, child); 

 * Function : remove_max 
 * Pop out the max node in the heap. 
 * Method : Exchange the last one and the root, then 
 * reheap the tree to make the exchanged root to its 
 * right position. 
struct Word_node remove_max(){ 
    node_ind --; 
    if(node_ind != 0){ 
        swap_node(0, node_ind); 
    return heap[node_ind]; 

 * Function : read_one_word 
 * Read in one word form the file, and store in the 
 * char array, input. 
int read_one_word(char *input){ 
    char c; 
    int ind = 0; 
    while(scanf("%c", &c) != EOF){ 
        if( !isAlpha(c) && !isDigit(c) ){ 
            input[ind] = '\0'; 
            return TRUE; 
        input[ind++] = toLower(c); 
    return FALSE; 

 * Function : isDigit 
 * Determine whether the character c is a digit. 
int isDigit(char c){ 
    if( c>='0' && c<='9')    return TRUE;
    return FALSE; 

/* Function : isAlpha 
 * Determine whether the character c is a alphabet. 
int isAlpha(char c){ 
    if((c>='a' && c<='z')||(c>='A' && c<='Z'))    return TRUE;
    return FALSE; 

 * Function : toLower 
 * Return the lower case of the input character. 
 * Method : By modifying the 6th bit of the character to zero, 
 * we obtain the lower case. (0010 0000)2 = (1<<5) 
char toLower(char c){ 
    if(!isAlpha(c))    return c; 
    return (c|(1<<5)); 

Wednesday, October 31, 2012

Continuation Passing Style(CPS) using Scheme

針對近期學習的Scheme中的Continuation Passing Style(CPS)查詢相關資料,做了筆記。


Continuation Passing Style is a formed for expressions such that no function ever returns, instead they pass control onto a continuation.
"A data structure represents what is left to do."


  • return early
  • exceptions and failure can be signalled
    • pass in a continuation for success
    • pass in another continuation for fail
  • suspend
  • CPS quickly fills the stack or has to be given hand-coded infrastructure in languages that don't support the automatic merging of unneeded stack frames.

To Complement:
  • every function takes an extra argument, its continuation
  • every argument in a function call must be either a variable or a lambda expression (not a more complex expression)
  • There's no implicit continuation - every call  is a tail call.
  • There's no magic there, every continuation is simply explicitly passed.
  • For using CPS without tail call optimisation will cause not only the constructed continuation potentially grow during recursion, but also the call stack.
Another Topic, Call-with-current-continuation:
  • Scheme allows the continuation of a computation to be captured by call/cc.
  • (call/cc proc), where proc is a one-parameter function.
  • (define get-back 'any), usage: (get-back k)
  • (exit 0), escaping from deep recursion.
My Review:
Quite hard to read Scheme code especially with lots for function calls and recursion. This might because I am more familiar with basic imperative programming languages.

Friday, September 28, 2012

iTerm 2 v.s. Terminal (on Mac)

學長提到在Mac底下很多人會使用iTerm 2而非原本的Terminal加上screen,於是乎我便自己安裝了的iTerm 2看看差異在哪裡。

以下幾點是iTerm 2內建的功能,也是我個人認為這些是大家會選擇iTerm 2的原因:
  1. 分割畫面:可以水平和垂直分割出不同的畫面,由於是內健在iTerm 2裡面操作上與快捷鍵的設定普遍順暢合理。
  2. 系統叫出iTerm 2的全域快捷鍵:可以設定在系統任何處叫出iTerm 2的快捷鍵,然而,需要先設定iTerm 2為"Open At Login",這樣它才會在使用者登入後開始等待讀設定好的快捷鍵。
  3. 更接近*unix:雖然大家都說Mac就是從BSD來的,command應該不會差太多,但是個人在使用本來的Terminal上,發現仍有一些小地方很不順手(與*unix差異較大處),其中值得一提的是,我使用Terminal時進入Downloads/,輸入"ls"指令,有時不會出現任何東西,有時會當掉,而我查看資料夾權限時發現,Mac的部分檔案權限比*unix多一個欄位,暫時推測是如此不同的權限設定導致我在Downloads/底下無法正常"ls"。另外,更多快捷鍵的設定是跟*unix一樣的,如ctrl+D會登出並結束,但是Ternimal底下必須command+D而且並沒有幫你關掉Terminal。
  4. 支援全螢幕:Mountain Lion開始,Mac OS X程式有無支援全螢幕模式成為大家在意的事情,或許不能說是非常重要的一件事情,但表示iTerm 2更新和維護的頻率是高的。

Sunday, August 5, 2012

Commands of Appengine

dev_appserver.py <folder path>
demo on local machine

appcfg.py update <folder path>
upload folder to Google server

Tuesday, June 19, 2012


期末考時遇到雙颱,大家都紛紛在問隔天會不會考試... 於是用程式碼解釋這個現象,不過裡面有個有趣的BUG,能發現嗎?

Saturday, June 16, 2012

Facebook Chat-room Image ( Facebook 聊天室圖案製作 )



[[119853858155674]] [[406381676079369]] [[405569136151638]] [[123046641168163]] [[351541474918594]] [[350116605059320]]
[[330262407053149]] [[119515894855852]] [[248128375300088]] [[251189481647356]] [[252104128229413]] [[404711332904212]]
[[315426835210887]] [[358358740897499]] [[144806638987969]] [[330205803723974]] [[400975169955496]] [[309864779103545]]
[[433440300023950]] [[395893770456168]] [[162290537236794]] [[253404078092844]] [[345436568858428]] [[441776292507972]]
[[453347648010473]] [[473114889368633]] [[310365985721855]] [[221169918003673]] [[294436837320086]] [[244573498991442]]
[[459915707353191]] [[409172655792153]] [[372764052783133]] [[432841633416823]] [[460590967285763]] [[146421248826697]]




把所有粉絲專頁的ID(可以從網址裡面讀出)記錄下來,套入[[ ]]中,排序成M*N的形式後就可以在聊天室貼給朋友分享了!

ex. [[395893770456168]]


  1. 過程中圖片和粉絲專頁名稱一定要標好,且可以從中讀出影像的位置(幾之幾)
  2. 使用Photoimpact分割圖片與創立數十個粉絲專頁,比想像還要費時,往後若要操作可以寫自動化的程式運作,讓全部程序自動化
  3. 粉絲專頁在太短的時間內建立太多會被偵測到,Facebook可能會把該使用者封鎖(我連續創立約20個就遇到警告訊息)


Friday, June 8, 2012

Google Blockly

今天在WIRED(http://www.wired.com/wiredenterprise/2012/06/google-blockly/)上頭看的Google Blocky,說是視覺化的程式語言,於是玩了他的名叫Maze的DEMO(http://blockly-demo.appspot.com/blockly/demos/maze/index.html)。



Tuesday, May 29, 2012







Wednesday, May 16, 2012



溫度 - 海洋大學



Friday, May 4, 2012

Stanford Karel

Wiki: http://en.wikipedia.org/wiki/Karel_(programming_language)

Stanford的CS106A Programming Methodology是頗大的一門課,不論當時在實際在Stanford修課,或是回來後看Coursera(Online Course)和iPad上的iTunes U都有這門課,裡頭的內容也很完善。

這門課的是設計給Computer Science學生的第一門課,第一週裡,他不和你談論真正的程式,而是給出一個只有四個指令的軟體機器人Karel,它只會「前進」、「左轉」、「撿東西」、「放東西」,然後教材一路教導你怎麼讓Karel變聰明,一週內,它學會蓋房子、撿垃圾、...

當時和助教聊天,它說以前CS106A是以C語言為主,但是現在則是教Java (this means that most of Stanford Computer students learn Java as their first programming language),Keral也是用Java寫出來,然後包裝好,不讓一開始學習的初學者看到裡頭複雜的程式,而只有那四個指令。



  • 以了解概念為主導,課程非常強調學生寫程式要如何思考、如何有一個正確的習慣
  • 它限制了給學生的東西,與一般學校授課的方式不同,過程中由簡入深,把比較深的內容包裝起來不被你看到,讓初學者不會一開始就陷入茫然
  • 很有趣!教材都很完整的教學,修完課讓學生自己有能力可以寫很多東西
  • 製作GUI
  • 自撰教材或是翻譯教材
  • 分享給需要的人

Wednesday, April 25, 2012




Linux Keyboard Shortcuts



  • X Window System
    • ctrl + alt + + :zoom in,即放大螢幕上文字
    • ctrl + alt + - :zoom out,即縮寫螢幕上的文字
    • 滑鼠中間鍵:在一般gnome的Linux環境中,滑鼠中間鍵可以把你目前有在任何一處圈選(反白)的文字複製貼上
  • Command Line <input>
    • Home or ctrl+a:跳至句首
    • End or ctrl+e:跳至句尾
    • * alt + b:跳到上一個單字首(word, 以空白分開者)
    • * alt + f:跳到下一個單字首(word, 以空白分開者)
    • tab太重要了!它可以在你沒打完單字的時候自動補上剩餘的字元,若是沒有辦法找到唯一的對應,多按一下tab,會列出所有可能對應的選項
    • ctrl + u:刪掉現在這行
    • ctrl + k:從當前的位置,往後刪除到行底
    • ctrl + w:從當前的位置,往前刪除一個單字
  • Command Line <output>
    • shift + page up:往上檢視
    • shift + page down:往下檢視
    • clear or ctrl+l:清空目前頁面
    • reset:清空、類似於重新開啟這個terminal。比如你cat一個binary檔案,在你之後輸入command時不斷有字元跑出來煩你時可以用(根據該網頁的講法)
  • Command Line <history> 翻閱先前打過的command
    • history:查用近期的command紀錄(可以用pipeline配合grep, more等指令使用)
    • 上方向鍵 or ctrl + p:顯示上一個執行過的指令(查閱history)
    • 下方向鍵 or ctrl + n:顯示下一個執行過的指令(查閱history)
    • ctrl + r:透過類似於搜尋的功能,邊打邊搜尋對應history裡的紀錄
  • Command Line <其他>
    • ctrl + c:強至中止當前的process
    • ctrl + z:讓目前的process(前景)到後景運作,透過fg指令可以喚回,ps可以查看背景process有哪些
    • ctrl + d:寄送出已經沒有輸入的訊息。可用來寄送EOF訊息給一般process,或是直接按下後便log out當前的terminal
    • ctrl + alt + del:當機時候可以使用,至於對應的反應可能因系統而不同,可以/etc/inittab設定
p.s. 加'*'者表示該指令不一定能在圖形化界面的terminal操作,因為該shortcut往往已經被map到系統的其他地方


Tuesday, April 24, 2012

Learning VIM

接續上回VIM - That's Why Linux,學習VIM的方法很多。



Monday, April 23, 2012

Sharing IPMI IP with the host

以下連結的網頁是針對 IPMI 板子與 host 共用 IP 的問題所作的討論:


  • Sharing Ethernet means that LAN1 appears to have 2 MAC addresses(the IPMI interface, the standard Broadcom NIC)
    • 公用同一條網路線表示LAN1會有兩個對應到的MAC位址(IPMI和原本的網路卡)
  • Traffic to the IPMI interface is magically intercepted below the operating system level and never seen by whatever OS is running.
    • 原本到 IPMI 介面的流量會跑到作業系統底下,而不論使用什麼作業系統都將無法看到

Downsides for sharing the IP for IPMI and OS host
  • It's particularly difficult to partition the IPMI interface onto a separate subnet in a secure manner.
    • 很難做到將兩者分開成不同子網路以保證安全
  • The latest IPMI cards now support assigning a VLAN to the IPMI NIC, so you can get some semblance of separation - but the underlying OS could always sniff the traffic for that VLAN.
    • 最新的IPMI卡可以支持把VLAN轉到IPMI NIC的功能,所以你可以得到一個「看似」兩者區分開來的樣子,但是OS仍然可以監視到該通訊流
  • Older BMC controllers don't allow changing the VLAN at all, although tools like ipmitool or ipmicfg will ostensibly let you change it, it just doesn't work.
    • 比較舊的BMC控制器不允許你更便VLAN,雖然有像是ipmitool或ipmicfg等工具,但是就是辦不到
  • You're centralizing your failure points on the system. Doing configuration on a switch and manage to cut yourself off somehow? And, you've now cut off the primary network connection to your server AND the backup via IPMI. NIC hardware fail? Same problem,
    • 你把所有可能失敗的地方都集中在系統,要怎麼設定一個開關,然後要他關掉自己?你關掉最重要的到伺服器的網路連線和透過IPMI備份的機制。至於NIC硬體問題也會遇到一樣的狀況
照這份文章的解釋,不建議我們設法把 IPMI 和 host IP共用。

Chrome Theme Creator

在Chrome Store逛逛,看到一個叫做My Chrome Theme的App,可以製作自己的Chrome Theme,頗有趣的,於是自己做了一個,也有提供別人下載、安裝的功能:

然而一般放在Chrome Theme選單裡面的Theme應當不是用這樣的方法做成的,這個App的顏色選擇太少了,實在不能製作出比較精緻的設計。

Friday, April 20, 2012

VIM - That's Why Linux!




Thursday, April 19, 2012

Reference in C++

Reference : A simple reference datatype that is less powerful but safer than the pointer type inherited form C. (from Wiki)

Comparing to "Pointers"
  1. It's not possible to refer directly to a reference object after it is defined; any occurrence of its name refers directly to the object it references. (cannot be "reseated", which is often done with pointers) 
    • 在初次定義過後不能再指向其他物件(但pointer常常被用來做這件事情),故命名中會表達所指向的物件為何。
  2. References cannot be "null", whereas pointers can. (Note, containers of references are not allowed)
    • reference不能存「空」的值,也表示,一個「裝references」的容器是不被允許的。
  3. References cannot be uninitialized. Because it is impossible to reinitialize a reference, they must be initialized as soon as they are created.
    • 基於reference一定要在初次定義時候初始化(分配指向的物件),所以沒有「重新初始化」或是「消去初始值」類的東西。
Things About References
  1. [運作]不論上述三項目的不同之外,References與Pointer都是用「傳位址」的方法實現。
    • 當作函數參數值時,函數改變該參數內容,原本呼叫函數的地方,該參數對應的變數,值也會被更改。
    • 非「傳值」的方式,所以沒有傳送太大資料量的問題。
  2. [使用]作為函式傳入值使用的時候:
    • 呼叫函式的地方值用一般變數方法:int square( x, result ); // int result, int x=3;
    • 接傳入值的函數定義處要加"&":int square( int x, int &result ) {}
    • 函式內部使用該傳入值時,用一般變數的方法:result = x*x;

Wednesday, April 11, 2012

"unget" Function in C++

  • 只一個char透漏的資訊並不多
  • 沒有效率

Tuesday, April 10, 2012

Simple Web Server (nweb.c) Running On Windows


Class Website : http://people.cs.nctu.edu.tw/~cjtsai/courses/ics/index.html
Simple C code (nweb.c) here : http://people.cs.nctu.edu.tw/~cjtsai/courses/ics/homework/nweb.c

以下以Dev-C++為IDE的例子,直接把nweb.c打開按下F9(compile and run)會出現以下的情況:


  1. Link Library
  2. Create C:\public_html Directory
  3. Create index.html and favicon.ico

1. Link Library

先解決變數沒有定義的問題我們必須連結這份C code需要的函式庫(WS2_32.lib),一般使用令命列gcc的人可以很清楚的了解,只要在gcc command後面加上"-lws2_32"就好了,在Dev-C++(或是其他類似的IDE)也只要稍微設定一下即可。Dev-C++方法如下:

  • 選最上方的"Tools"
  • 選"Compiler Options"
  • 將"Add these commands to the linker command line"打勾
  • 該下方的輸入方格中輸入" -lws2_32 "
  • 按下"Ok"按鍵,完成設定

2. Create C:\public_html Directory


>> cd Desktop
>> nweb.exe



3. Create index.html and favicon.ico

懂html甚至可以用「記事本」依照html語法寫好之後即可(就可以用網頁瀏覽器開啟);不懂的人在這裡也可以隨意找一份完成的html檔案放在該資料夾底下即可(也可用我的HelloWorld HTML檔:http://dl.dropbox.com/u/20358682/index.html,按右鍵另存檔案下載)。


程式剛跑起來的時候會出現以上三行文字後停滯,此時用網頁瀏覽器(chrome, firefox, IE, etc.)開啟localhost(在網址列打localhost),會發現瀏覽器可以順利載入我們放置好的index.html檔案。

但是!同時也發現cmd這邊的程式在瀏覽器開啟網站時也結束了,這跟我們期待的不同,server應當處理多次個服務,所以可以讓第二個、第三個、...使用者也可以讀取到index.html才對。這份C code會產生一份log檔案(nweb.syslog)在同資料夾底下,此份log中會紀錄程式運行的狀況或是問題,開起來看看發生什麼事情吧(選用記事本開啟即可,這也是一份文字檔罷了了):

最後一個SORRY寫到"failed to open file:favicon.ico"得知原來我們缺少favicon.ico檔案!

favicon.ico即是網頁載入時上頭的小icon,可以到這個網頁:http://www.favicon.cc/ 畫一個可愛的圖案、下載後放到C:\public_html就好囉!


Linux 內建 C 函式庫 Manual

Linux中,對於不了解的command可以直接打"man <command>"即可得到該command的使用手冊,而其實對於 C 語言函式也可以,如"man printf"。

若發現有些明明是常見的 C 函式卻得到"No manual entry for <command>"的回覆,可以嘗試安裝"manpages",方法如下:

$sudo apt-get install manpages-dev manpages-posix-dev
$sudo yum install man-pages


Sunday, April 8, 2012

Lua Programming Language


$sudo yum install lua
Package lua-5.1.4-7.fc14.x86_64 already installed and latest version

然後vim helloworld.lua
print ("Hello World!")

$chmod +x helloworld.lua

Saturday, April 7, 2012

Can't connect to local MySQL server through socket '/var/lib/mysql/mysql.sock'

設定MySQL on Fedora時候,當mysql.sock不存在時,嘗試登入mysql root(mysql -u root -p)時候會出現:
Can't connect to local MySQL server through socket '/var/lib/mysql/mysql.sock'(2)
 即使touch該檔案(sudo touch /var/lib/mysql/mysql.sock)還是會出現:

Can't connect to local MySQL server through socket '/var/lib/mysql/mysql.sock'(111)
sudo /etc/init.d/mysqld start

DocumentRoot does not exist

在Fedora底下,我嘗試把apache某個網頁設定檔的DocumentRoot指向home目錄的工作位置,可是在restart apache(sudo /etc/init.d/httpd restart)時候,得到Warning,寫著DocumentRoot [PATH/IS/HERE] does not exist,發現是SELinux把apache擋住了。


  1. 安裝policycoreutils-gui:sudo yum install -y policycoreutils-gui
  2. 執行system-config-selinux:system-config-selinux
  3. 點選左側"Boolean"選單
  4. 將"Allow httpd to read home directories"(httpd_enable_homedirs)的選項打勾(立即生效)
如此的方法不論之後重新開機也會保持設定,但是要注意安全問題,在測試的個人電腦可以如此操作,不建議在真的Web Server這麼做

Wednesday, April 4, 2012

Basic Linux Command Line Tutorial



Thursday, March 29, 2012

Let's Match!開發心得和紀錄

Let’s Match!開發心得和紀錄
Heron Yang @ NCTU.CS
Site Link:

2012年寒假,認識一位系上同學,專研於server-side相關事務,擅長Perl語言,於是找他合作;分工上,我負責client-side(那時我也只會HTML/CSS, JavaScript),他負責server-side,從假期最後一週開始,預計一週是足夠的,事實證明的確足夠「完成」,但並沒辦法真的發表。
client-side的資料送到後端,他使用Perl/CGI的方式去讀取,且將配對資料直接以檔案的方式存在系統裡面,對於有心人要去盜取是十分容易,所以這個方法不能被接受;同時,十分明顯地,欲解決此類問題應該使用一個具有安全性的資料庫,如php+mySQL。提出這個方式去解決時,與我合作的同學表示他不會也沒有意願去學,我也不曾接觸過,於是就這樣Let’s Match!被擱置了約一個多月。
剛開學的時候課業上比較輕鬆,便突然興起,在宿舍架設server,如此一來就可以把自己一些小作品分享到網際網路上頭,陸續我寫了Life TimerDoodle Events Calendar,分享出去之後,我看著Google Analytics的動態圖表,試想著使用者的行為和心理,沒多久,我把Let’s Match!移到這台server,捨棄了之前同學Perl/CGI的code,改用php+mySQL的方法,那時我完全不會,就邊學邊做!
不到一週的時間,功能差不多完成,找了人幫忙設計版面和圖案。當時看到Facebook上頭開始流傳要開始提供「暗戀」這個功能,跟Let’s Match!可以說是一模一樣的東西,一時我有點緊張也有點興奮,變加速開發的進度,不著兩週就在一個週日晚上發表了!

  • 沒有測試足夠的平台
  • 沒有預料到所有可能的使用情況
當天半夜詢問該位使用者,發現是當初他在登入App時候,有部份權限勾選不允許導致,我把這個使用上的可能造成的疏失,寫到網頁的訊息中,繼續經營Let’s Match!

  • 只有把App分享出去,才能提升自己Match的成功率
    • 使用者希望跟「那個人」Match,故應該至少分享給一個人,所以此級數 r>=1 必不收斂(每個人都有心上人、網路使用人口不限的情況下)
  • 看到頁面Match成功次數,讓使用者躍躍欲試

個人架設server的經驗頗短,只有區區幾周的時間,Let’s Match!中使用到的apache, ssh, php, mySQL, etc.都是現學現賣,意識到使用者比預計多的時候,頓時感覺壓力頗大,來自於:
  • 對使用者使用經驗的責任
  • 對資料安全的責任
  • 對自己作品的要求

  • 開發流程完整,釋出前應有少數人的測試階段
  • server端的安全問題要了解且下功夫
  • 了解server能夠承受的量
  • 文字(包括中文與英文)都應該要多與人討論
  • 延攬同興趣的人進行分工,目前需要「設計」、「文字」、「宣傳」,可增加一位programmer

  • 已經蒐集使用者的建議,可以添加上去
    • 增加VOID選項
    • 搜尋朋友功能
  • server管理、維護和安全問題改進
  • 防止惡意使用行為
  • 增加完整度、提升使用品質、增加趣味性,方可以延攬更多使用者
  • 文字修飾、宣傳

  • 此程式對自己的意義和目的?
  • 資料安全產生的法律問題我承擔?
  • 此程式發展與自己原先計畫的不同,本應該沒有要花這麼多時間相對犧牲掉所謂的「本業」,是否應該停止?

Saturday, February 18, 2012



  • function templates
  • class templates

Function Templates

類似於overload functions

  • overload functions用於相似或是相同的情況
  • function templates則用於完全相同而只有資料型態差異的情況下
  • template< typename T >
  • template< class ElementType >
在<>符號中間的為template parameters,超過一個用逗號分開,型態有class或typename。

#include <iostream>
using namespace std;

// function template
template< typename T>
void printArray(const T * const array, int size){
 for(int i=0 ; i<size ; i++){
  cout << array[i] << " ";
 cout << endl;

int main(){

 int a[4] = {1,2,4,3};
 char b[3] = {'b', 'c', 'a'};
 double c[5] = {1.23, 12.3, 0.12, 1.233, 0.11};

 printArray(a, 4);
 printArray(b, 3);
 printArray(c, 5);

 return 0;

範例中,當int a[]傳進來的時候T就會變成int,char進來則是char,以此類推。

"The compiler uses its overload resolution capabilities to find a definition of function printArray the best matched the function call."
compiler使用類似於overload的解法處理printArray中的T,會自動找尋最合適的function call。


  • 若是自訂的資料型態,要記得有沒有先overload該型態的operators(for example, ==, >=, ...)
  • 同一個template definition裡頭names of template parameters不能重複;不同template definition則可以重複
  • template的處理在compile time

Class Templates

另一種template為class templates,加在class definition的前面:欲達到的效果和function templates一樣,希望可以產生一個「通用」的方式,避免撰寫重複的程式碼。

#include <iostream>

using namespace std;

template<typename T>
class Stack{
  Stack(int = 10); // default constructor
  ~Stack(){ // destructor
   delete [] stackPtr;
  bool push(const T &);
  bool pop(T &);

  bool isEmpty() const{
   return top == - 1;
  bool isFull() const{
   return top == size - 1;

  int size;
  int top;
  T *stackPtr;

template<typename T>
Stack< T >::Stack(int s):
 size(s>0 ? s : 10),
 stackPtr( new T[size] ){

template<typename T>
bool Stack< T >::push(const T &pushValue){
  stackPtr[++top] = pushValue;
  return true;
 return false;

template<typename T>
bool Stack<T>::pop(T &popValue){
  popValue = stackPtr[top--];
  return true;
 return false;

#include <iostream>
#include "Stack.h"
using namespace std;

int main(){

 /* int */
 Stack<int> intStack(5);
 int intValue = 1;

 // push
  cout << intValue << " ";
  intValue += 2;
 cout << endl;

 // pop
  cout << intValue << " ";
 cout << endl;

 /* double */
 Stack<double> doubleStack(6);
 double doubleValue = 1.0;

 // push
  cout << doubleValue << " ";
  doubleValue *= 1.1;
 cout << endl;

 // pop
  cout << doubleValue << " ";
 cout << endl;

 return 0;


其一non-type template parameters,我們可以透過以下的方式使用template parameters達到一般argument的效果,其中template definition:
template<typename T, int elements>
Stack<int, 13> helloStack;

其二,default type,當使用時沒有給予資料型態時賦予,則預設資料型態,用以下方法定義:
template<typename T = int>
Stack<> scores;


Friday, February 17, 2012

overload functions

C++語言中支持overload function的功能,即是同一個名稱的function可以定義很多次,每一次都可以有

  • 不同數量  和
  • 資料型態
  • 輸入參數
  • 傳回值

Wiki 中提供很易懂的C++例子:http://en.wikipedia.org/wiki/Function_overloading

Monday, February 13, 2012



在繼承之後,各個derived class的object往往會需要執行同一個base class裡的函式,然而在不同的derived class裡,執行該函式的方法可能不同;讓base class的函式得以在不同derived class裡有不同的方式其實現則稱Polymorphism。

舉例,base class為「圖形」,derived class有「方形」、「圓形」,「圖形」這class裡有draw()這個函式,「方形」、「圓形」雖都繼承了這個函式,但是要draw出圖形的方法卻不同,這問題則是Polymorphism要討論。



#include <iostream>
#include <iomanip>
#include "GodStudent.h"

using namespace std;

int main(){

 Student people("People", 60);
 Student *ppeople = &people;

 GodStudent heron("Heron", 100, 90);
 GodStudent *pheron = &heron;

 // base-class object
 people.print(); // static binding
 ppeople->print(); // dynamic binding

 // derive-class object
 heron.print(); // static binging
 pheron->print(); // dynamic binding

 // pheron = &people; // this can not work
 ppeople = &heron;

 return 0;


  1. base-class pointer可以指向derive-class object,但derive-class pointer不能指向base-class object。因為derive-class object "is-a" base-class object,所以第一句敘述是對的,C++中會依照宣告的資料型態去操作資料,所以透過base-class pointer指向derive-class object的方法只能使用base-class中有定義的函式,而derive-class中新定義的函式便沒有辦法操控(像是這例子的getBaseScore()/setBaseScore())
  2. object後面加"."讀取函式的方法為static binding,透過pointer/reference的方法為dynamic binding。static binding可以在compile的時候即知道有無錯誤,dynamic binding則要到程式執行時才能知道有沒有問題。
為了解決能讓base-class pointer指向derive-class object也能使用derive-class中的函式之問題,我們要介紹"virtual"。
  • virtual,在base class中在某函式定義前面加virtual,往後base-class pointer指向derive-class object時,仍可以呼叫到derive-class object的函式,例如print(),他即可呼叫derive-class的print(),得以印出baseScore。撰寫derive-class時,寫覆蓋過base-class中的virtual函式的動作稱為override。
  • pure virtual,此方法只在base class中寫該函式的interface(header中的prototype),不寫inplementation,且在prototype最後、分號前加"= 0"。此方法達到兩件事情:
    • 含有pure virtual函式的class稱為abstract class(反義為concrete class),只有抽象意義,不能產生instance。例如「二維」是abstract class,底下繼承的「方形」、「圓形」才是concrete class。
    • 在直接或間接的derive class中要能生成instance(concrete class),必須完成所有pure virtual函式的implementation
如此一來,在上層的base class中定義pure virtual函式,待不同的derive class來implement,得以解決本文最初提出的問題。同時也架構起了OOP。

Sunday, February 12, 2012


在物件導向的程式語言中含有「繼承」的概念,最主要的效果為避免撰寫重複的程式碼。操作上,我們讓某個class所定義的object繼承另一個class,前者稱為base classes,後者稱為derived classes(C++語言中的叫法),derived classes可以繼承base classes裡面的屬性(attributes)和行為(behavior),換句話說,繼承的classes可以直接使用被繼承classes中的變數和函式,達到避免重複撰寫相同程式碼的效果。


  1. 繼承的方式:public, private, protected
  2. base classes中的不同類型(public, private ,protected)變數可以被derived classes使用的權限
繼承的方式:public, private, protected

最常用的是public繼承,他建立了derived classes和base classes的「is-a relationship」,例如:derived classes是car,base classes是vehicle,即car "is-a" vehicle。

定義derived classes時候,程式碼這麼寫:
class Car : public Vehicle{};

base classes中的不同類型(public, private ,protected)變數可以被derived classes使用的權限

在public形式繼承中,base classes的public變數可以被derived classes使用,private則不行,pretected變數則是設計給繼承使用的,可以被derived classes使用。

在OOP概念中,希望東西一層層分離、封裝,透過給予使用介面(interface)的方式連結,而不希望使用者(這裡指derived classes)去更變內部的資料,於是,上述的public, protected變數可以直接被derived classes使用就不會是一個好的方法,最好的方式是透過private變數再使用public的set/get函式去使用變數


  1. set的函式中往往會檢查輸入值是否為有效值,或是一些客製化的處理,若是繞過set/get函式去更變變數,可能導致該變數儲存了無效值
  2. 若是base classes改變內部的設置(程式碼),直接讀取、使用base classes的public, protected變數的方式,derived classes的程式碼也可能要跟著更變,導致整份程式變得複雜麻煩,而使用set/get的方式可以避免這樣的問題,即是「封裝」的概念
  • base classes的程式碼是不需要因為繼承而有任何更改的
  • derived classes程式碼中要include base classes存放的header檔
  • derived classes程式碼中要使用base classes中的變數或函式可以直接使用,但若是該變數或函式已經被另一個相同名稱的變數或函式覆蓋,可以在前面加上"base clesses name::"的方式讀取使用,例如:Vehicle::drive()
  • 若是base classes已經有的東西盡量避免重複撰寫,善用base classes提供的函式

Example Code
以下範例是用Student當作base class,每個Student object有自己的名字、分數,然後有一個叫做GodStudent的class當作derived class,繼承Student,GodStudent "is-a" Student,但是GodStudent與其他Student不同的是,他對於自己有一個最低標準分數(baseScore)。

base class的header (Student.h)
#include <string>
using namespace std;

class Student{
  Student(const string &, int = 0);

  void setName(const string &);
  string getName() const;

  void setScore(int);
  int getScore() const;

  void print() const;

  string name;
  int score;

base class的implementation (Student.cpp)
#include <iostream>
#include <string>
#include "Student.h"

using namespace std;

Student::Student(const string &_name, int _score){
 name = _name;
 score = _score;

// name, set/get
void Student::setName(const string &_name){
 name = _name;

string Student::getName() const{
 return name;

// score, set/get
void Student::setScore(int _score){
 score = _score;

int Student::getScore() const{
 return score;

// print
void Student::print() const{
 cout << "Name >> " << name << "\tScore >> " << score << endl;

derived class的header (GodStudent.h)
#include <string>
#include "Student.h"
using namespace std;

class GodStudent : public Student{
  GodStudent(const string &, int = 0, int = 90);

  void setBaseScore(int);
  int getBaseScore() const;

  void print() const;
  int baseScore;

derived class的implementation (GodStudent.cpp)
#include <iostream>
#include "GodStudent.h"

using namespace std;

GodStudent::GodStudent(const string &_name, int _score, int _baseScore)
 :Student(_name, _score){

void GodStudent::setBaseScore(int _baseScore){
 baseScore = _baseScore;

int GodStudent::getBaseScore() const{
 return baseScore;

void GodStudent::print() const{
 // accessing protected variables
 cout << "Protected Variables" << endl;
 cout << "Name >> " << name << "\tScore >> " << score;
 cout << "\tBaseScore >> " << baseScore << endl;

 // accessing private variables
 cout << "\nPrivate Variables" << endl;
 cout << "BaseScore >> " << baseScore << endl;

使用者的主程式 (main.cpp)
#include <iostream>
#include <iomanip>
#include "GodStudent.h"

using namespace std;

int main(){
 GodStudent heron("Heron", 100, 90);

 cout << "getName >> " << heron.getName() << endl;
 cout << "getScore >> " << heron.getScore() << endl;
 cout << "getBaseScore >> " << heron.getBaseScore() << endl;


 return 0;