其實程式之美這本書，根本就是現代版的名題百則。我大概在八九年前，參加高中生資訊比賽時讀過這本 C 語言名題百則，而且也只看了前半部吧，記得高一時有學長拿第一題 "最長平台" (Plateau) (註) 來問我，當時我只會直觀地以暴力法解之，當他告訴我裡面的所謂正解後，我才明瞭原來解題可以這麼漂亮、這麼有趣，之後即讓我對 programming 產生很大的興趣。這本名題百則對當時參加比賽的眾學生而言，幾乎是人手一本，但我居然沒有，至今我無法成為個頂尖的程式員，大概是這個原因吧 (笑)。而程式之美這本書呢，他的全名為 "程式之美－微軟技術面試心得"，雖然如此，但它並不是一本教人如何面試微軟，或是面試任何軟體公司的攻略，而是一本以許多的資訊及數學的問題為例，引導讀者如何思考一個問題，並列出各種解法的題庫，正如其名，探索程式之美麗。
註：已知一串由小排到大的陣列；平台的定義：是由一串連續相同元素所組成，而連續範圍也是有限制，不可能無止盡的。EX：1、2、2、3、3、3、4、5 其中 "1"、"2、2"、"3、3、3"、"4"、"5" 都是平台，寫程式讀入一串陣列，並找出最長平台 (上例中 "3" 就是最長平台)
2008年7月27日 星期日
A sample of template meta-programming
C++ template 的發展動機其實很簡單，就是要增進程式碼的重覆利用性以及讓我們得以建立型別安全的容器，研究後最後發現，C++ template 機制本身是一部完整的 Turing-complete，可以被用來計算任何可以計算的值，進而衍生出 meta-programming 的概念。簡單說來，meta-programming 就是寫程式來產生程式碼 (由compiler產生，稱為俱現化，instantiation)，再編譯成機器碼，這樣的好處就是可以把一些計算提到編譯時期處理，提高程式的效率也提早發現錯誤。通常拿來當作學習 C++ meta-programming 的程式大概就是階乘的計算，傳統上計算階乘的方法不是迭代法就是遞迴法，但這兩種方法都是在程式的執行時期才計算，以下簡單地給了非 meta-programming 版本以及 meta-programming 的版本，欣賞在編譯時就將數值計算完畢的神奇，也給對 meta-programming 有興趣的程式員一個入門的動力：
傳統版：
meta-programming 版：
傳統版：
unsigned int Factorial (unsigned int n)
{
{
if ( n<=1 ) return 1 ;
else return n*Factorial(n-1);
else return n*Factorial(n-1);
}
int main()
{
{
cout << Factorial (10) << endl ;
return 0 ;
return 0 ;
}
meta-programming 版：
template<unsigned n>
struct Factorial
{
struct Factorial
{
enum { value = n * Factorial<n-1>::value } ;
};
template<>
struct Factorial<0>
{
struct Factorial<0>
{
enum { value = 1 } ;
};
int main()
{
{
cout << Factorial<10>::value << endl ;
return 0 ;
return 0 ;
}
用 traits classes 以表現型別的資訊
Traits classes 是一種在 STL 中廣泛應用的型別辨視技術，考慮以下情境，我們有四種自定型別 ClassA, ClassB, ClassC, ClassD，以及一個 function template F 如下：
雖然 F 可以對這四種型別做運算，但有時候可能因為此四種型別的實作方式不一，某些型別對於 F 運算，可以有更有效率的作法 (或是不同的作法)，例如 STL 中，對於某種 iterator 的運算，會因為 iterator 的不同類型 (STL 有五種 iterators：input, output, forward, bidirectional, random access) 而有不一樣的方法，所以我們希望能在 template 中辨視型別。
首先我們建立一些 tag struct 用以表示型別的特徵：
然後在目的型別中，利用 typedef 定義一個子型別
接著，建立 traits class template：
此時我們的 function template F 大概變成這樣：
但是這樣的程式碼在編譯時可能會有問題 (因為 operating for ClassA 當中的所有敘述，必需被 ClassT 型別所支援，既使這些敘述不會被執行到)，但此時有件更重要的事要解決，ClassT 也就是 myType 的型別在編譯時期就可以決定，而myTraits<ClassT>::category 也是在編譯時期就可以決定，但 if else 卻是執行期才會執行的語句，因此我們必須將 if else 提到編譯時期確定，做法即是使用 function overloading。我們 overload 兩個 function template F如下：
最後，我們就可以將 F 改寫如下：
完工。
template<typename ClassT>
void F( ClassT myType)
{
void F( ClassT myType)
{
if ( myType is ClassA)
{
{
// operating for ClassA
}
else
{
else
{
// operaing for ClassB, C, D
}
}
雖然 F 可以對這四種型別做運算，但有時候可能因為此四種型別的實作方式不一，某些型別對於 F 運算，可以有更有效率的作法 (或是不同的作法)，例如 STL 中，對於某種 iterator 的運算，會因為 iterator 的不同類型 (STL 有五種 iterators：input, output, forward, bidirectional, random access) 而有不一樣的方法，所以我們希望能在 template 中辨視型別。
首先我們建立一些 tag struct 用以表示型別的特徵：
struct classA_tag {} ;
struct classBCD_tag {} ;
然後在目的型別中，利用 typedef 定義一個子型別
class ClassA
{
{
public:
typedef classA_tag category ;
};
class ClassB
{
{
public:
typedef classBCD_tag category ;
};
class ClassC
{
{
public:
typedef classBCD_tag category ;
};
class ClassD
{
{
public:
typedef classBCD_tag category ;
};
接著，建立 traits class template：
template<typename ClassT>
struct MyTraits
{
struct MyTraits
{
typedef typename ClassT::category category;
};
此時我們的 function template F 大概變成這樣：
template<typename ClassT>
void F( ClassT myType)
{
void F( ClassT myType)
{
if ( typeid (typename myTraits<ClassT>::category ) == typeid (classA_tag ) )
{
{
// operating for ClassA
}
else
{
else
{
// operaing for ClassB, C, D
}
}
但是這樣的程式碼在編譯時可能會有問題 (因為 operating for ClassA 當中的所有敘述，必需被 ClassT 型別所支援，既使這些敘述不會被執行到)，但此時有件更重要的事要解決，ClassT 也就是 myType 的型別在編譯時期就可以決定，而myTraits<ClassT>::category 也是在編譯時期就可以決定，但 if else 卻是執行期才會執行的語句，因此我們必須將 if else 提到編譯時期確定，做法即是使用 function overloading。我們 overload 兩個 function template F如下：
template<typename ClassT>
void doF( ClassT myType, classA_tag)
{
void doF( ClassT myType, classA_tag)
{
// operaing for ClassA
}
template<typename ClassT>
void doF( ClassT myType, classBCD_tag)
{
void doF( ClassT myType, classBCD_tag)
{
// operaing for ClassB, C, D
}
最後，我們就可以將 F 改寫如下：
template<typename ClassT>
void F( ClassT myType)
{
void F( ClassT myType)
{
doF ( myType , typename MyTraits<ClassT>::category( ) );
}
完工。
2008年7月21日 星期一
新書推薦：程式之美, 重構-向範式前進
程式之美這本書是由微軟亞洲研究所的一個小組所撰寫，內容包含了六十多道的程式與演算法題目，主要都偏向於腦力激盪的類型，對於資訊科系的學生，是一本很有挑戰的習題本，而對熱愛編程的程式員，也是一本激發腦力的好書。
重構-向範式前進，這是侯捷的新作，雖然是翻譯書 (原：Refactoring to Patterns )，不過如同以往侯捷作品的風格，也是一本高品質的好書。早些年前已有 重構-改善既有程式的設計 (原：Refactoring: Improving the Design of Existing Code) 在討論如何重構程式碼，而這本書不同之處在於，他是介紹如何重構至某些 design patterns，或者說，當需求符合某些 patterns 時，如何將既有的程式碼重構至那些 patterns，這對於資深的程式員，是一本必備良書。
2008年7月17日 星期四
WinAPI型別與.NET型別的對照表
http://www.codeproject.com/KB/dotnet/Win32APICPlusPlustoDotNET.aspx
http://msdn.microsoft.com/zh-tw/library/hfa3fa08(VS.80).aspx
雖然.NET的函式庫已經應有儘用，但有時還是會到別人給的dll檔，而這些dll檔通常都是用VC++所寫的，要使用的話，就必須自已依C++標頭檔重新宣告函式。這個表就是在作型別轉換時必備的資訊。
http://msdn.microsoft.com/zh-tw/library/hfa3fa08(VS.80).aspx
雖然.NET的函式庫已經應有儘用，但有時還是會到別人給的dll檔，而這些dll檔通常都是用VC++所寫的，要使用的話，就必須自已依C++標頭檔重新宣告函式。這個表就是在作型別轉換時必備的資訊。
2008年7月16日 星期三
F# Programming Language
http://research.microsoft.com/fsharp/fsharp.aspx
F# 是微軟新推出的程式語言，最大的特色就是他是函數式程式語言(Functional Programming Language)，以往函數編程最大的缺點就是效率太差，但今日硬體的進步與多核心CPU的流行，反而讓函數編程佔了優勢，所以微軟立即推出F#以吸引程式員。微軟在官方首頁上形容F#為：
Combining the efficiency, scripting, strong typing and productivity of ML with the stability, libraries, cross-language working and tools of .NET.
給了F#一個很大的評價，也說明了函數編程，必然是未來的趨勢。
F# 是微軟新推出的程式語言，最大的特色就是他是函數式程式語言(Functional Programming Language)，以往函數編程最大的缺點就是效率太差，但今日硬體的進步與多核心CPU的流行，反而讓函數編程佔了優勢，所以微軟立即推出F#以吸引程式員。微軟在官方首頁上形容F#為：
Combining the efficiency, scripting, strong typing and productivity of ML with the stability, libraries, cross-language working and tools of .NET.
給了F#一個很大的評價，也說明了函數編程，必然是未來的趨勢。
訂閱：
文章 (Atom)