江添亮さんがC++11の解説本を公開してくれました!

C++標準化委員会のメンバーで、最近はクッキーを増やすゲームのおそらく日本で一番面白いレビューを書いてくれた江添さんが、C++11の解説本をなんとコピーレフトで公開してくれました。

http://ezoeryou.github.io/cpp-book/C++11-Syntax-and-Feature.xhtml で見ることができます。

まだ途中までしか見ていませんが、簡潔で、かつ、プログラマの視点で重要な部分の説明に重点を置いた本ですね。
さらには仕様の背景にある考えも説明してくれていてありがたいです。

重要で知っておくべきなのに、複雑だしあまり面白くないのがADLのあたりだと思いますが、この本ではかなり分りやすく書いてあるのでC++プログラマは必見だと思います。
「オーバーロードの解決があいまいです」ってエラーがでてウガーッ!!!ってなると思いますが、ADLの仕様を知っておくと対処が楽になりますね。

とりあえず、auto、ラムダ式はあたりは当然ですが、地味なところでscoped enumと生文字列リテラルを一刻もはやく使って幸せになりたいです(;_;)

elevatedで使われている技術

2009年にスペインのiq氏がelavatedという衝撃的なデモを発表した。
わずか4KBのプログラムで、リアルな山岳地帯の風景を3Dでリアルタイム描画し、音楽も鳴らすというものだ。


「たった4KBでこんなことができるわけがない! チートだ!」と叫びたくなるプログラムだが、製作者(iq氏)がいろんな資料を公開してくれていて、 それを読むと「天才ならこのぐらいはできるかもな」ぐらいには思えるようになる。

iq氏の資料はココにまとまっている。

elavatedの概要のpdfを読むと、

• 地形は2D格子で、各格子点の高さはパーリンノイズで求める。(パーリンノイズについての詳細)
• 通常のポリゴンベースの描画ではなく、ピクセルシェーダを使ったレイマーチン法でレンダリング。(地形とのレイマーチン法についての詳細)
• カメラの位置、方向、パスもピクセルシェーダ内で算出
• 地形の法線ベクトルは隣のピクセルとの差分から算出するのではなく、パーリンノイズの式を微分して解析的に求める。
• 影はフェイクで、ローパスフィルタをかけた地形の拡散光を影の成分とする。

といった手法を使っているようだ。

さらにはelevatedのShaderToy版もあり、簡易版ながらコードを見たり、いじることもできる。
魔法がとけてよかった。

しばらくみないうちにライフゲームもすごいことになってるんだな

全9回のライフゲームの紹介動画。全部で1時間弱の素晴らしい動画だ。

シリーズ後半の8回、9回あたりは見ていて鳥肌が立った。
ライフゲームがチューリング完全とは聞いていたが実例を見ると、その機能美と、それを生み出した人間の知恵に感動して言葉を失う。

MSXML6のgettext()が異常に遅い件

MSXML6をXMLの読み込みに使っているが、国土地理院のページで配布されている標高メッシュのXMLを読み込ませたところ、これがとにかく遅い！

問題のXMLは以下のように values要素が約84万個大量に並んでいるもので、容量はおよそ100MB程度である。

<jps:CV_GridValuesMatrix>
  <jps:values>
    <jps:memberValue>
      <type>その他</type>
      <alti>-9999.00</alti>
    </jps:memberValue>
  </jps:values>

  <jps:values>
    <jps:memberValue>
      <type>その他</type>
      <alti>-9999.00</alti>
    </jps:memberValue>
  </jps:values>
    ...
</jps:CV_GridValuesMatrix>

これを以下のようなコードで読み込ませてみると、数10分かかっても処理が終わらない。

MSXML2::IXMLDOMNodePtr p = pCV_GridValuesMatrix->firstChild;
while (p) {
  if (p->GetnodeName() == _bstr_t(L"jps:values")) {
    MSXML2::IXMLDOMNodePtr pAlti = p->firstChild->firstChild;
    double d = _wtof(pAlti->Gettext());
  }

  p = p->nextSibling;
}

プロファイルをとってみると、Gettext()関数が処理の大半を占めている。
同じフォーマットで10MB程度のXMLは数秒で終わることから、どうやらGettext()がファイルサイズに対してO(N^2)のような処理オーダーになっている印象を受ける。
これは奇妙だ。Gettext()の処理内容を想像すると定数時間で済みそうなものなのに!

試行錯誤して、Gettext()の変わりにfirstChild->nodeValue を呼ぶようにしたら処理は数秒で終わるようになった。たったこれだけで数千倍も処理時間が違う。

MSXML2::IXMLDOMNodePtr p = pCV_GridValuesMatrix->firstChild;
while (p) {
  if (p->GetnodeName() == _bstr_t(L"jps:values")) {
    MSXML2::IXMLDOMNodePtr pAlti = p->firstChild->firstChild;
    double d = static_cast(pAlti->firstChild->nodeValue);
  }

  p = p->nextSibling;
}

ってことで、いまいち理由がわからないが巨大なXMLを扱うときには Gettext()は呼び出したらアウトのようだ。

ちなみに今回の現象で悩んだ際にMSXML関連の情報をあさってみたが、以下のようなコードで遅いと言っている人もいた。

MSXML2::IXMLDOMNodeListPtr l = pCV_GridValuesMatrix->GetchildNodes();
for (int i = 0; i < l->Getlength(); ++i) {
  MSXML2::IXMLDOMNodePtr p = l->Getitem(i);
  ...
}

これを上記のXMLでやると、このトラバースだけで数10分かかっても終わらない。
これはおそらく DOMNodeListは線形リストの実装になっていて、ランダムアクセスにO(N)の時間がかかるためだろう。
MS公式のFAQにも「こういうトラバースはしないで!」という情報があったが、だったら初めからGetitem()なんて関数用意しなきゃいいのに。

猿でも分かった～型消去技法とは

ひさびさにC++の話。

C++の技法に型消去(Type Erasure)というものがありますね。なんかかっこいい名前だし、いろんなすごいライブラリで使われてるっぽい話はよく聞くので、「Type Erasure? なにそれ? やだ、こわーい」となる人もいるでしょう。(ぼくもそう)
でも型消去はトモダチ、怖くない!

唐突ですが、継承関係はないけどとにかく"f"という関数を持ったクラス群があったとしましょう。

struct A {
  void f() { cout << "A!"; }
};
struct B {
  void f() { cout << "B!"; }
};

役にたつかどうかは分からんけど、こういったものを保持しておいて後からfを呼び出すことができるクラスholderが作れるか考えてみましょう。
これは簡単で、テンプレートを使って以下のように書けますね。

template<typename T>
struct holder {
  holder(const T& obj) : m_obj(obj) {}

  void f() { m_obj.f(); }

  T m_obj;
};

holder<A> a(A());
holder<B> b(B());
a.f();
b.f();

さてここでholderはテンプレートクラスですが、テンプレートでないクラスにすることはできるでしょうか? もしこれができれば、以下のようにとにかくfという関数をもったあらゆるオブジェクトをobjsという配列に溜め込んで、その後適切にfを呼び出すようなことができます。

vector<holder> objs;

...

for (size_t i = 0; i < objs.size(); ++i) {
  objs[i].f();
}

驚くべきことに、これが実に単純な方法で実現できます。仮想関数とテンプレートを組み合わせて使って型に関する情報を派生クラス側に追い出すだけです。

struct holder {
  virtual void f() = 0;
};

template<typename T>
struct holder_sub : public holder {
  holder_sub(const T& obj) : m_obj(obj) {}

  virtual void f() { m_obj.f(); }

  T m_obj;
};

使ってみましょう。

vector<shared_ptr<holder> > objs;
objs.push_back(new holder_sub<A>(A());
objs.push_back(new holder_sub<B>(B());

for (size_t i = 0; i < objs.size(); ++i) {
  objs[i]->f();
}

ついでに、使うときに派生クラスを見せるのはかっこ悪いので以下のようなラッパーをかませましょう。

struct anyf
{
  template<typename T> anyf(const T& a) { m_p.reset(new holder_sub<T>(a)); }

  void f() { m_p->f(); }

  shared_ptr<holder> m_p;
};

するとこんな風に使えます。

vector<anyf> objs;
objs.push_back(A());
objs.push_back(B());

for (size_t i = 0; i < objs.size(); ++i) {
  objs[i].f();
}

anyfにはfをもった要素ならなんでも突っ込めるし、そうでなければちゃんとコンパイルエラーになってくれます。
これが型消去技法です。きわめて単純なコードなのに、魔法みたいな挙動が実現できてますね!

これまでのサンプルの関数fは非常につまらない関数でしたが、元の型にキャストするような関数に適用するとどうでしょうか?
そう、boostの超便利クラスanyみたいなものが出来そうです。anyも基本的にはこの単純な型消去技法を使って実装されているようです。

組み合わせ爆発を説明した動画がいろんな意味で面白い

日本科学未来館が作成した、組み合わせ数が急速に増える様子を説明した動画。
某所では「公共が病気」とか「人類には早すぎる動画」とか「謎の感動」とか言われているが、面白いので見てない人はぜひ見てほしい。結末は衝撃的だ。


おねえさんの狂気っぷりと子供のドン引きさが、なんかツボにはまる。

さて、最短経路(つまり右か下にしか進まない)のケースでは高校のときに確率の授業で習っている。
NxNのときには 2N個の中からN個を選ぶ組み合わせを計算すればよい。
実際に数え上げる必要はなく、Nがいくら大きくなっても単に公式「C(2N,N)=(2N)!/(N!*N!)」を計算すれば簡単に解くことができる。

ではこの動画のお姉さんのように、最短でない経路も数えないといけない場合はどうなのだろう?

これはSelf-avoiding walkと呼ばれる問題らしく、解析的に解くことはできない。つまり答えを求める公式は存在しないので、正確な答えを求めるには数え上げるしかない。
そのうえNP困難といわれる部類の非常に難しい問題ではないかと推測されている。もしそうなら、どんなに工夫しようと効率的に数え上げる方法は存在しないということだ。

それでもこの動画の最後で言われているように、おねえさんのように総当たりで数えるよりもマシな数え方は考えられている。
これまでのところは19x19までは解が求まっているようだ。
意外だったのは、プログラマには神のような存在のクヌース先生もこの問題に取り組んだことがあるようで、1995年に12x12のときを解いている。

このように経路の総数を求めるということは非常に難しい問題であるが、この問題自体に何の意味があるのか?高速に数え上げたところで何の役に立つのか? という疑問は当然湧いてくる。
税金使って変な動画作りやがってというツッコミもあるようだ。

この動画を作った日本科学未来館のページをみると、この問題そのままではないが、例えば電気の送電網でどのような経路で電気を送るともっとも電力のロスが少ないか?といったテーマでその応用例をあげている。

子供向けの動画のようだが、大人が見てもいろいろと深くて面白い背景があることに気づかせてくれる素晴らしい動画だと思う。

2012.09.27追記
最近記録を更新して21x21の解を求めた人がいるようです! 論文もここでみれます。
更新したのは・・・この動画の最後のクレジットにでてくる関係の人たちみたいですね。

麻三斤(Masagin)

A monk asked Tozan: "What is Buddha?"
Tozan said: "Masagin!"

たまたま洞山守禅師が麻の目方を計っているところに僧がやってきて、「仏とは何ですか?」と質問した。洞山は、「麻三斤」と答えた。

Farbrausch & Neuro - Masagin


2:10～4:40あたりまでの展開が大好き。2Dグラフィックでもこんなにインパクトのある映像を作れるものだとは。

麻薬のような中毒性のあるデモであるが、タイトルであり、曲名であり、冒頭のシーンで登場する"麻三斤"は大麻という意味ではないらしい。
有名な禅問答なんだそうである。意味を調べてみたが、いろんな解釈があるようでよくわからない。主に以下の2通りの解釈があるようだ。

• 麻三斤は衣が一着つくれるだけの量の麻であり、「仏なんてそんな特別なものではないよ。私もあなたも着ている衣、つまり日常の中にこそほんとうに大切なものがある」
• 仏法の大事なところを文字で解釈するんではない、頭で理解しようとするでない

後者のほうがカッコイイ解釈であるが、果たしてどちらが正しいのかな?

なんて思っていたら、麻三斤の言葉の意味にこだわり、理屈をこねるようなことをやっていては、とうてい“麻三斤”の真意は得られないというメタ(?)な 意味もあるそうです。(仏教における外道はこれらの見解に執着するかららしい...)

難しくて頭が痛くなった。禅って深いですねえ。