Visual Studio 2015で gflagsを x64/Unicode文字セットのアプリケーションから利用する

google先生の作った gflagsというコマンドライン引数を扱うライブラリを タイトルの環境で使えるようにしたのだけど、とてもつかれた・・・ また同じ思いはしたくないのでメモ。ちなみにまだ簡単なサンプルでしか動作確認していないので注意。

[CMakeのインストール]
・cmakeがインストールされてなければ、CMake公式サイトから win32/x86のバイナリをダウンロードしてインストール

[gflagsのビルド]
1. githubから ソースを入手
2. VS2015の各種ツールのパスの通ったコンソールから、gflagsの CMakeLists.txt があるフォルダに移って、"cmake ."を実行
3. gflags.sln が生成されたはずなので、これをVS2015で開いてビルドすると、ひとまずx86でマルチバイト文字セットのライブラリができる

[gflagsをx64でビルド]
1. gflags.slnを開いた状態で、"ビルド->構成マネージャー"メニューを実行し、右上のアクティブソリューションプラットフォームの欄で新規作成を選び x64プラットフォームを作成する。
2. gflags_staticとgflags_nothred_staticプロジェクトのプロパティを開き、ライブラリアン->その他のオプションの項目で MachineX86オプションが明示的に指定されているのでこれらを除去。
3. これでx64のライブラリがビルドできるはず。

[gflagsをUnicode文字セットのプロジェクトからリンクする]
1. gflagsをUnicode文字セットでビルドするのはソースをガシガシ書き換える必要がありそうなので諦めて、gflags自体はマルチバイト文字セットのままにする。
2. Unicode文字セットのプロジェクトでは普通に gflagsをリンクし、google::ParseCommandLineFlags()で渡す引数をマルチバイトに変換して渡す。
3. これで利用できるはずだが、VS2015ではロケールの扱い周りでバグがあるらしく(?)、std::cout、std::wcoutにどちらかしか日本語出力ができなかったり、mbstowcs系の関数がうまく動かなかったりでハマった。 ひとまず Win32 APIの MultiByteToWideChar()を使ったり, coutへの出力は諦めて対応。コードはざっと以下のような感じ。

#include "../../../gflags/include/gflags/gflags.h"
#pragma comment(lib, "../../../gflags/x64/release/gflags_static.lib")
#pragma comment(lib, "shlwapi.lib") // __imp_PathMatchSpecAのリンクに必要

#include <iostream>
#include <vector>
#include <windows.h>

DEFINE_bool(big_menu, true, "Include 'advanced' options in the menu listing");
DEFINE_string(language, "japanese", "default language");

bool MBS2WCS(const std::string& s, std::wstring& sResult)
{
    int nBufSize = MultiByteToWideChar(CP_ACP, 0, s.c_str(), -1, NULL, 0);
    std::vector<wchar_t> vBuf(nBufSize);
    if (MultiByteToWideChar(CP_ACP, 0, s.c_str(), -1, &vBuf[0], nBufSize) == 0) {
        _ASSERTE(false);
        return false;
    }
    sResult = std::wstring(&vBuf[0]);
    return true;
}
bool WCS2MBS(const std::wstring& s, std::string& sResult)
{
    int nBufSize = WideCharToMultiByte(CP_ACP, 0, s.c_str(), -1, NULL, 0, NULL, NULL);
    std::vector<char> vBuf(nBufSize);
    if (WideCharToMultiByte(CP_ACP, 0, s.c_str(), -1, &vBuf[0], nBufSize, NULL, NULL) == 0) {
        _ASSERTE(false);
        return false;
    }
    sResult = std::string(&vBuf[0]);
    return true;
}

int _tmain(int argc, TCHAR* argv[], TCHAR* envp[])
{
    setlocale(LC_ALL, "");
    std::locale loc("");
    std::wcout.imbue(loc);

    std::vector<char*> argvA(argc);
    std::vector<std::vector<char>> buf(argc);
    for (int i = 0; i < argc; ++i) {
        std::string s;
        WCS2MBS(argv[i], s);
        buf[i].resize(s.size() + 1);
        strcpy_s(&buf[i][0], buf[i].size(), s.c_str());
        argvA[i] = &buf[i][0];
    }

    gflags::SetUsageMessage("gflagsライブラリのテスト");
    char** pA = &argvA[0];
    google::ParseCommandLineFlags(&argc, &pA, true);

    std::wcout << FLAGS_big_menu << std::endl;

    // coutに日本語が出力できないのでwcoutに出力
    std::wstring s;
    MBS2WCS(FLAGS_language, s);
    std::wcout << s << std::endl;

    return 0;
}

実行するとこんな感じ。

>gflag_test.exe -language 日本語
1
日本語

>gflag_test.exe -language English -nobig_menu
0
English

江添亮さんが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の解を求めた人がいるようです! 論文もここでみれます。
更新したのは・・・この動画の最後のクレジットにでてくる関係の人たちみたいですね。