Android 指リスト編については、既に
Haskell編、
Python編、
Python編(その2)
が存在しているが、今度は C++ 編である。
が、 C++ では Haskell や Python のように、
interactive shell でお遊びをするあたりはさすがに再現できないので、
代わりに実行速度にこだわってみたい。
実行速度にこだわるというからには、
Python やら Haskell やらがどの程度の実行速度なのかをあらかじめ知っておく必要がある。
以前の記事では interactive shell で遊ぶために全てのパターンを列挙していたが、
今回については単純化のためパターン数の計算のみについて考えることとし、
最初から単純にパターン数を数え上げる方式にプログラムを若干変更の上計測する。
実行時間計測：Python
ベースのプログラムはPython編(その2)を用い、
nextList 関数を数え上げのみに限定しておく。
def nextList(i, rem):
return sum(
(nextList(s, rem - set([s])) for s in candidate(i, rem)),
1 if len(rem) <= 5 else 0)
print(nextList(0, frozenset(range(1, 10))))time コマンドで実行にかかった時間を計測する。
% time python3 flistnum.py
389112
python3 flistnum.py 2.65s user 0.02s system 99% cpu 2.667 total
% time python3 flistnum.py
389112
python3 flistnum.py 2.66s user 0.00s system 99% cpu 2.659 total
% time python3 flistnum.py
389112
python3 flistnum.py 2.65s user 0.01s system 99% cpu 2.657 total2.6秒強程度といったところ。
実行時間計測：Haskell
ベースのプログラムはもちろんHaskell編のものを使用する。
Python のときと同じように nextList 関数を数え上げのみに限定し、
nextList :: Int -> [Int] -> Int
nextList n rem =
foldr (+) (if length rem <= 5 then 1 else 0)
[nextList s (rem \\ [s]) | s <- candidate n rem]
main = print $ nextList 0 [1..9]実行速度最適化オプション -O2 もつけてコンパイル後、計測する。
% time ./flistnum
389112
./flistnum 0.10s user 0.00s system 101% cpu 0.102 total
% time ./flistnum
389112
./flistnum 0.09s user 0.01s system 99% cpu 0.102 total
% time ./flistnum
389112
./flistnum 0.10s user 0.00s system 101% cpu 0.101 totalちょっ…、わずか 0.1 秒…。
やるな、Haskell。
だが今回使うのは何しろ C++ である。コレに勝ってみせねばなるまい。
C++ の本当の実力を見せてやる！
いきなりソースコード全体
#include <boost/mpl/integral_c.hpp>
#include <boost/mpl/vector_c.hpp>
#include <boost/mpl/remove.hpp>
#include <boost/mpl/fold.hpp>
#include <boost/mpl/lambda.hpp>
#include <boost/mpl/if.hpp>
#include <boost/mpl/size.hpp>
#include <boost/mpl/plus.hpp>
#include <boost/mpl/arithmetic.hpp>
namespace mpl = boost::mpl;
template <int, int> struct blocklist { typedef typename mpl::integral_c<int,0> type; };
template <> struct blocklist<1, 2> { typedef mpl::integral_c<int,3> type; };
template <> struct blocklist<1, 4> { typedef mpl::integral_c<int,7> type; };
template <> struct blocklist<1, 5> { typedef mpl::integral_c<int,9> type; };
template <> struct blocklist<2, 5> { typedef mpl::integral_c<int,8> type; };
template <> struct blocklist<3, 2> { typedef mpl::integral_c<int,1> type; };
template <> struct blocklist<3, 5> { typedef mpl::integral_c<int,7> type; };
template <> struct blocklist<3, 6> { typedef mpl::integral_c<int,9> type; };
template <> struct blocklist<4, 5> { typedef mpl::integral_c<int,6> type; };
template <> struct blocklist<6, 5> { typedef mpl::integral_c<int,4> type; };
template <> struct blocklist<7, 4> { typedef mpl::integral_c<int,1> type; };
template <> struct blocklist<7, 5> { typedef mpl::integral_c<int,3> type; };
template <> struct blocklist<7, 8> { typedef mpl::integral_c<int,9> type; };
template <> struct blocklist<8, 5> { typedef mpl::integral_c<int,2> type; };
template <> struct blocklist<9, 5> { typedef mpl::integral_c<int,1> type; };
template <> struct blocklist<9, 6> { typedef mpl::integral_c<int,3> type; };
template <> struct blocklist<9, 8> { typedef mpl::integral_c<int,7> type; };
template <class S, class L, class N> struct candidate_helper {
typedef typename blocklist<S::value, N::value>::type block;
typedef typename mpl::remove<L, block>::type type;
};
template <class S, class R> struct candidate {
typedef typename mpl::fold<
R, R, typename mpl::lambda<candidate_helper<S, mpl::_1, mpl::_2> >
>::type type;
};
template <class S, class R> struct nextcount;
template <class R, class NS> struct nextcount_helper {
typedef typename nextcount<NS, typename mpl::remove<R, NS>::type>::type type;
};
template <class S, class R> struct nextcount {
typedef typename mpl::fold<
typename candidate<S, R>::type,
typename mpl::if_c<mpl::size<R>::value <= 5,
mpl::integral_c<int,1>,
mpl::integral_c<int,0> >::type,
mpl::plus< mpl::_1, nextcount_helper<R, mpl::_2> >
>::type type;
};
typedef nextcount<
mpl::integral_c<int,0>,
mpl::vector_c<int,1,2,3,4,5,6,7,8,9> >::type all_count;
#include <iostream>
int main() {
std::cout << all_count::value << std::endl;
return 0;
}実行時間計測：C++
% time ./flist
389112
./flist 0.00s user 0.00s system 92% cpu 0.003 total
% time ./flist
389112
./flist 0.00s user 0.00s system 93% cpu 0.003 total
% time ./flist
389112
./flist 0.00s user 0.00s system 92% cpu 0.003 totalわずか 3ms ！
みたか！ これが C++ の実力だ！！
オチ
…いや、ごめん。これ一発ネタなんだ。オチはもう分かってると思うけど、
% time make
g++ -O2 -I/usr/local/include flist.cpp -w -o flist
make 1565.43s user 3.20s system 99% cpu 26:13.64 total実行速度の代償としてコンパイルに30分近くかかるという実用性のなさだ。
ついでにメモリも GB 単位で食う。まったくもって酷い話である。
640KB で十分なわけがなかった。
ちなみに、Haskell のコンパイル時間はこのくらい。
% time ghc -O2 flistnum.hs
[1 of 1] Compiling Main ( flistnum.hs, flistnum.o )
Linking flistnum ...
ghc -O2 flistnum.hs 0.87s user 0.15s system 22% cpu 4.615 total圧倒的な差が…。
GHC のドキュメントには「-O2 のコンパイルは物凄く遅いよ！ 考えてから使えよ！」
などと脅し文句が書いてあったような気がするのだが、この規模なら気にするほどでもない。
いや、まあ冷静に考えればこのサイズで 5 秒弱かかるのは確かに遅いが、今ちょっと感覚が狂っていてだね…。
オマケ
最初にソースコードを載せる暴挙をやっているので、わかる人には最初からオチまで全部わかっていたものと思うが、
本記事で行ったのはいわゆる「テンプレートメタプログラミング」という手法である。
そんなわけで、前述プログラム内の all_list::value はコンパイル時に解決される。
どういうことかというと、下記のように記述したものと同等だということだ。
#include <iostream>
int main() {
std::cout << 389112 << std::endl;
return 0;
}実行速度が速いのは当たり前である。定数を出力しているだけなのだから。
しかし考えてみれば、Haskell にも同等の潜在能力があることを忘れてはいけない。
ここでいう潜在能力とは、同じくメタプログラミングを行う Template Haskell のことではない。
通常の Haskell プログラムのことだ。何って、全ての式が参照透過性を満たしていることだ。
参照透過性が成り立っているということは、同じ引数が与えられればその式は「常に」同じ結果を返す。
それはすなわち、「コンパイル時でも」同じ結果だということに他ならない。
だから理論上は、今回扱っているコードであれば、
Haskell コンパイラも「定数を出力するだけ」のコードを生成することが出来るハズなのだ。
しかし、もし最適化によって本当にそれが行われているのであれば、元々のリストを生成してから要素数を調べる方法と、
今回修正した単純な数え上げの方法とで、実行速度は変わらないはずなのだ。
しかし、手元で試す限りではそうはなっていないようだったので、
残念ながらコンパイル時に定数値まで簡約されているというわけではないということになる。
まあもちろん常に簡約すればそれで良いというわけでもないだろうから、その辺は仕方ないのだろう。
それでも 0.1 秒で結果を出していることを考えれば、ある程度のところまではコンパイル時に計算している可能性は高い。
ちなみに、テンプレートメタプログラミングを行わない素朴な C++ での実装(blocklist に std::map を、候補リスト管理に std::set を用いた)では、gcc の -O2 をつけてなお、実行に約 0.18 秒弱を要した。
これは最適化オプションを「つけない」Haskell 数え上げ版とほぼ同等か、ごく僅かに速い程度であり、冒頭で啖呵を切ったにも関わらず、同条件である最適化オプション付きの Haskell には全くかなっていないのである。
もちろん C++ なのでパフォーマンス改善の余地はあるとは思うが、それでも 0.1 秒を切ろうと思ったら相当なレベルでチューニングが必要だろう。
そしてそのことが、Haskell の最適化ではある程度のところまでコンパイル時に計算しているのではないかと予想した根拠でもある。
…いや、正直に言うと、その根拠を求めてわざわざ素朴な C++ での実装を追加で書いた。Haskell がこんなに速くなければ本記事はテンプレートを使ったネタ記事で終わらせるつもりだったのだ。
何が言いたいのかというと、Haskell 遅くないよ！ 超速いよ！
解説…？
本 C++ 版では、 Haskell やら Python やらで行ったようなコード片ごとの解説は行わない。
大体、解説されたって殆どの人は読みたくないだろう、こんなコード…。
Haskell や Python のすっきりしたコードには及ぶべくもない。
とはいうものの、基本方針は Haskell 版、Python 版となんら変更はないので、
興味のある人は Haskell 版の記事を参考にして読み解いてみるのも面白いだろう。
書くには苦労したが(いや、だって、エラーメッセージが懇切丁寧に難読化されてるんだよ…さすがにわけがわからないよ)、
何をしているのか順に追うだけなら、丁寧に読めばどうにかなる範囲のハズである。
＃人気の記事
＃タグ
