其實程式之美這本書，根本就是現代版的名題百則。我大概在八九年前，參加高中生資訊比賽時讀過這本 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#一個很大的評價，也說明了函數編程，必然是未來的趨勢。
2008年5月28日 星期三
[Note] MSP430 interrupt vector
DACDMA_VECTOR
PORT2_VECTOR
USART1TX_VECTOR
USART1RX_VECTOR
PORT1_VECTOR
TIMERA1_VECTOR
TIMERA0_VECTOR
ADC12_VECTOR
USART0TX_VECTOR
USART0RX_VECTOR
WDT_VECTOR
COMPARATORA_VECTOR
TIMERB1_VECTOR
TIMERB0_VECTOR
NMI_VECTOR
PORT2_VECTOR
USART1TX_VECTOR
USART1RX_VECTOR
PORT1_VECTOR
TIMERA1_VECTOR
TIMERA0_VECTOR
ADC12_VECTOR
USART0TX_VECTOR
USART0RX_VECTOR
WDT_VECTOR
COMPARATORA_VECTOR
TIMERB1_VECTOR
TIMERB0_VECTOR
NMI_VECTOR
2008年5月19日 星期一
[note] 數位電視規格
資料來源
1. 美規 ATSC 8-VSB 用於 6MHz 電視頻道。
2. 歐規 DVB-T COFDM 用於 6/7/8 MHz 電視頻道，目前台灣採用的是歐規 DVB-T 6MHz 。
3. 日規 ISDB-T COFDM 用於 6MHz 電視頻道 ( 屬歐規改良型 ) 。
歐規（ DVB-T ）傳輸系統功能特色
1. 可以行動接收。
2. 可建立單頻網路（ SFN ），解決收視不良地區，改善轉播站之頻譜分配。
3. 室內接收能力較佳。以前電波碰到牆壁會反射，且會產生許多干擾波，對主要訊號造成干擾，以致無法 收看，在歐規系統，干擾波可當主訊號使用，甚至 有加分效果，將來在室內只要加裝天線即可接收。台 灣有線電視蓬勃發展的原因在於一般觀眾只會接收老三台，而不知如何接收公視、民視；公寓天線老 舊 沒有更新，加上大樓阻擋，及原有社區天線的被破壞，因此無線數位電視推出的理念著重在容易接收。
4. 抗多路徑（Multipath ）干擾能力強，也就是來自四面八方的訊號，透過偵測，只要在可允許範圍內，干 擾源皆可當做接收的訊號。
5. 與衛星、有線系統相容性佳。
6. 發射與接收端各種相關配套系統完備，產品技術穩定成熟。
7. 除美國、加拿大、韓國外，採用國家佔絕對多數。
電視數位化後之效益
1. 多頻道 現有 6 兆赫 (MHz) 的電視頻道中，可播出 4-6 個標準畫質 (SDTV) 節目，或播 1 個高畫質 (HDTV)
節目。
2. 提升服務品質 改善收視區訊號水準，提升影像畫質，增加音響與視訊服務。
3. 多媒體服務 整合通信與電腦，開闢多元化的業務與商機。觀眾可透過電話與數位電視相互溝通，達成如 購物、選片等雙向互動功能，也可接網際網路等數位裝備。
4. 提高頻譜使用效率 傳輸數位化後，頻譜效率提高。新建數位台使用 UHF 頻道，釋出現有 VHF 頻道，供 給公眾通信使用，充分有效運用頻譜資源。
1. 美規 ATSC 8-VSB 用於 6MHz 電視頻道。
2. 歐規 DVB-T COFDM 用於 6/7/8 MHz 電視頻道，目前台灣採用的是歐規 DVB-T 6MHz 。
3. 日規 ISDB-T COFDM 用於 6MHz 電視頻道 ( 屬歐規改良型 ) 。
歐規（ DVB-T ）傳輸系統功能特色
1. 可以行動接收。
2. 可建立單頻網路（ SFN ），解決收視不良地區，改善轉播站之頻譜分配。
3. 室內接收能力較佳。以前電波碰到牆壁會反射，且會產生許多干擾波，對主要訊號造成干擾，以致無法 收看，在歐規系統，干擾波可當主訊號使用，甚至 有加分效果，將來在室內只要加裝天線即可接收。台 灣有線電視蓬勃發展的原因在於一般觀眾只會接收老三台，而不知如何接收公視、民視；公寓天線老 舊 沒有更新，加上大樓阻擋，及原有社區天線的被破壞，因此無線數位電視推出的理念著重在容易接收。
4. 抗多路徑（Multipath ）干擾能力強，也就是來自四面八方的訊號，透過偵測，只要在可允許範圍內，干 擾源皆可當做接收的訊號。
5. 與衛星、有線系統相容性佳。
6. 發射與接收端各種相關配套系統完備，產品技術穩定成熟。
7. 除美國、加拿大、韓國外，採用國家佔絕對多數。
電視數位化後之效益
1. 多頻道 現有 6 兆赫 (MHz) 的電視頻道中，可播出 4-6 個標準畫質 (SDTV) 節目，或播 1 個高畫質 (HDTV)
節目。
2. 提升服務品質 改善收視區訊號水準，提升影像畫質，增加音響與視訊服務。
3. 多媒體服務 整合通信與電腦，開闢多元化的業務與商機。觀眾可透過電話與數位電視相互溝通，達成如 購物、選片等雙向互動功能，也可接網際網路等數位裝備。
4. 提高頻譜使用效率 傳輸數位化後，頻譜效率提高。新建數位台使用 UHF 頻道，釋出現有 VHF 頻道，供 給公眾通信使用，充分有效運用頻譜資源。
2008年5月13日 星期二
.NET 的 Task Parallel Library
近幾年來多核心CPU日漸普及，從雙核心、四核心到八核心，意味著現在的CPU可以一次執行多道指令，但計算機結構教科書上所提及的pileline三大hazard，與軟體設計的不良，卻使得多核心CPU效能無法被完全發揮。而就軟體來看，雖然設計了multi-threads，但若沒有搭配平行處理的函式庫，程式多半還是以單一核心在執行。在C++中，有著著名的OpenMP函式庫可供使用，但在.NET平台上CLR與Threading類別庫的設計，卻沒考慮到多核心的問題，以致效能不彰。但微軟也發現了這個大問題，成立了平行運算部門來開發新的CLR，並在去年年底發表了 Task Parallel Library測試版本，但這個library的用法必需手動地指明要平行運算的方式，與OpenMP只要指明那個指令想平行運算，compiler就會自動幫你規畫不太一樣，雖然要改寫的code不多，但若能自動的偵測，似乎比較完善。
訂閱：
文章 (Atom)