情報科学苦手の会に参加してきました
今年の情報科学若手の会には参加できなかったので、情報科学苦手の会の方に参加してきました。
幹事のみずしまさん、運営周りをいろいろサポートしていたsyuuさん（ハンドルネーム）、会場提供たけおかさん、その他発表者のみなさん、参加者のみなさん、ありがとうございました。
自分はC++が苦手なので、templateでコンパイル時に素数を数え上げるプログラムを作成して自習勉強してみました。苦手な法律の話も勉強したのですが、ピザ到着の時間が近かったので今回は発表をパスさせていただきました。
■ C++テンプレートでコンパイル時に静的に素数を計算する
元ネタ：
- C++テンプレートでFizzBuzz - おびなたん☆
- Kazuho@Cybozu Labs: C++ テンプレートで(いまさら)FizzBuzz
- C++のテンプレートで素数計算 - 西尾泰和のはてなダイアリー
ちょっと古い話題ですが、enumを使うテクニックをherumiさんから教えてもらったので、書いてみました。
#include <stdio.h>
template<int N, int n=N-1, int m=N%n> struct isPrime {
enum { ok = isPrime<N, n-1>::ok };
};
template<int N, int n> struct isPrime<N, n, 0> {
enum { ok = 0 };
};
template<int N> struct isPrime<N, 1, 0> {
enum { ok = 1 };
};
template<int N> struct printPrime {
printPrime() {
printPrime<N-1>();
isPrime<N>::ok && printf("%d\n", N);
}
};
template<> struct printPrime<1> {};
int main()
{
printPrime<MAX>();
}
コンパイルするときに -DMAX=100 のオプションをつけて #define MAX 100 してあげます。
■ 計測スクリプト
さきほどのC++のソースコードを prime.cpp に保存して #define MAX の値を変えて g++ のコンパイル時間を計測してみます。
#!/bin/bash
n="10 20 30 40 50 60 70 80 90 100 110 120 130 140 150 160 170 180 190 200"
for i in $n
do
echo -n "$i, "
/usr/bin/time -f "%U" g++ -DMAX=$i prime.cpp
done
■ 実行結果
以下の環境でベンチマークをとってみましたが、MAXの値が大きくなると結構な時間がかかるようです。
Athlon1640B 2.7GHz Memory8GB Ubuntu8.10(AMD64)
gcc version 4.3.2 (Ubuntu 4.3.2-1ubuntu12)
10, 0.17
20, 0.19
30, 0.23
40, 0.30
50, 0.44
60, 0.60
70, 0.69
80, 0.73
90, 1.17
100, 1.87
110, 2.81
120, 4.00
130, 5.59
140, 7.54
150, 9.97
160, 12.52
170, 16.58
180, 20.55
190, 25.74
200, 32.17
グラフにするとこんな感じになりました。MAX=1000を予想すると絶望的です。
結論：C++コンパイラは頑張り屋さん
ToDo：もっと早く計算させる方法を勉強する
enum じゃなくって typedef 使えば早くなるのかなぁ。。。
苦手なので誰か教えてください（＞＜）
