用 C++ Template 建表

(兩年前寫的東西,當時寫在 bbs 上沒公開,最近有空稍微整理一下。)

C++ TMP 可以利用 compile-time 計算一些東西, 凡是 static 資訊都可以算出來, 但如果要 runtime 到才存取呢?想了一個下午, 比較接近的方式是在 class template 裡頭放個 static array,  並且呼叫 value<N>::result 將資料填入表內。

拿 ACM 100 來做例子, 題目是 3n+1 問題, 有個函式定義為

f(n) = f(3n+1) , 若 n 為奇數
f(n) = f(n/2), 若 n 為偶數
f(n) = 1 ,     若 n = 1.

f(n) 在電腦科學裡猜想是不是任意 n 都等於 1,  即使檢驗到了上萬都符合, 但仍無法證明。現在,  求給定 n,  要算幾次才會等於 1, 例如 f(2) = f(1) = 1, 所以結果是 2。

我們可以先將結果放到程式碼中, 減少一些計算量。一般的作法就是先跑過一次程式, 把結果 copy & paste。利用 C++ Template Metaprogram 可以直接編譯的時候把結果算出來放入矩陣中。基本策略是, 分成計算, 跟填表兩個函式:

  • compute<N>::result 即為 f(N) 運算的次數,也就是所求資料
  • table<N>::result[i] 即為 compute<i>::result , i 小於 N

以下是 compute<N> 的原始碼,

template<int N>
struct compute{
enum { result = 1 + compute< (N%2)? (3*N+1) : (N/2) >::result };
};

template<>
struct compute<1>{
enum { result = 1 };
};

這邊跟一般 TMP 拿來展示(or炫耀?)的方法都差不多, 利用類似 1 + compute<N-1> 的方式來記錄遞歸的次數, 結果存在 result 裡頭。接下來是填表,


template<int lev> struct filler; // 向前宣告
template<int lev>
struct table{
static unsigned result[lev];
static void init(){
filler<lev>::init( result );
}
};

將 table 放在 table::result 並且靜態初使化其大小,這也可以在 run-time 才配置記憶體, 之後 init() 函式再負責呼叫 filler<lev>::init() 進來填表。

接下來是填表的函式,

template<int lev>
struct filler {
inline static void init(unsigned* table ) {
table[lev-1] = compute<lev>::result;
filler<lev-1>::init( table );
}
};


template<>
struct filler<1>{
inline static void init(unsigned* table)
{
table[0] = compute<1>::result;
}
};

一樣利用偏特化終止 template 展開, 作的事情也不多, 就只是把 table 傳進來, 在 table[lev-1] 的地方填入計算後的值。如果編譯器有作 inline 展開, 結果會變成


table[lev-1] = compute<lev>::result;
table[lev-2] = compute<lev-1>::result;
table[lev-3] = compute<lev-2>::result;
...
table[0] = compute<1>::result;

最後我們只要決定要產生多大的表格, 假設是 1000, 就是寫成:

table<1000>::init();

那麼 table<1000>::result 會是一個矩陣包含 compute(1) 到 compute(1000) 的資料。

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s