C++0x でスリープソート

C++

某 KUIS の院試でスリープソートが出題されたらしいので，以前話題になったときに書きかけてそのままにしていた C++0x での実装を晒しておきます．
まず sleep.cpp がこちら．

constexpr int f(int x, int y, int n)
{
    return y == 0 ? 0 : f(x * 2, y - 1, n) + f(x * 2 + 1, y - 1, n);
}

constexpr int g(int n)
{
    return n == 0 ? 0 : f(0, 16, n) + g(n - 1);
}

#define PP_STR(x) PP_STR_I(x)
#define PP_STR_I(x) #x

static_assert(g(N), PP_STR(N));

これを #define N 10 としてコンパイルし，時間を計ります．

$ time g++ -std=c++0x -DN=10 sleep.cpp
sleep.cpp:14:1: error: static assertion failed: "10"

real    0m5.208s
user    0m0.000s
sys     0m0.031s

約 5 秒後に，"10" がエラーメッセージとして出力されました．N の値を変えて，時間を計ります．

N real (s) N real (s)
1 0.624 11 5.476
2 1.139 12 6.349
3 1.732 13 6.786
4 2.246 14 7.207
5 2.777 15 7.644
6 3.510 16 8.112
7 3.791 17 8.627
8 4.056 18 9.141
9 4.492 19 9.626
10 4.930 20 10.030

正の相関があるような気がしますね．では sleepsort.sh を書きましょう．

#!/bin/bash
function f() {
    g++ -std=c++0x -DN="$1" sleep.cpp
}
while [ -n "$1" ]
do
    f "$1" &
    shift
done
wait

整数列を与えて実行します．

$ ./sleepsort.sh 2 3 5 3
sleep.cpp:14:1: error: static assertion failed: "2"
sleep.cpp:14:1: error: static assertion failed: "3"
sleep.cpp:14:1: error: static assertion failed: "3"
sleep.cpp:14:1: error: static assertion failed: "5"

要素数以上のプロセッサがあれば，それなりに動くんじゃないでしょうか (たぶん)．
アイデアはこちらから．

これを通じて知ったのですが，GCC は constexpr 関数の実行結果をメモ化するようです．