週に一回は書きますよ 月に4つ記事を書けばノルマは満たされます。
上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

1. iGoogle

友人の登録ができません。どうすればいいのか。

  • Opensocial tutorialに従ってiGoogle Developer toolsを入れる。
  • Sandbox FriendsのFriendsの項目に人を足してみる。
  • 友人として確認できない。Your current friends:You don't have any friends yet. Please choose some with the button aboveとか言われる。

なんかありえない所でつまづいている様子。とりあえず無視。

2. mixiアプリ

チュートリアルの挙動がおかしいです。

  • 始めから友人がちゃんといる。すばらしい。
  • Opensocial Tutorial のversion. 2までうまくいく。
  • version. 3のギフトのリストが出ない。調べるとupdateGiftListの中でエラーが起きている。
    • html.push('<li>', friends.getById(i) <- ここがnull.
  • NULLの時は代わりに内部idを表示することに。
    • >mixi.jp:[十六進数]と表示されるのでまちがってはいないはず。getById自体がうまくいっていない。

mixiアプリの準拠具合の問題かそれともtutorialか私が間違っているのか。練習ではあまり気にしないほうが良いかもしれません。

スポンサーサイト

前回列挙したような細かい時間計測はほぼ無理としてあきらめることにしました。

型レベルプログラミングでは計算時間を測るには全く向いていません。そもそもコンパイル時間を計算時間として測るので非常に誤差が大きいです。また、致命的なことに型レベル計算では理論上よりも長い時間がかかることがよくあります。詳しくはC++ Template MetaprogrammingのAppendixを参照。

time cost of PhysicistQueue::push in a rough expt.
これは空のPhysicistQueueに要素をSIZE個pushしたときの時間を計測したものです。10回計測を行い、その平均をとりました。見てのとおり、これだけでは意味のある結果が全くとれません。

次のように、一回のコンパイルの間に何度も同じ計算を行うと意味のある結果が出ます。

time cost of PhysicistQueue::push in a good expt.
このグラフは、空のグラフに要素をSIZE個pushしたときの時間を計測したものです。一回のコンパイル中にこの操作を100回繰り返し、それを10回時間測定しその平均を載せています。そのためSIZE=62,63間でギャップが生じているのは、この間に遅延したサンクを処理しているためです。このギャップについて解説するのが目的なのですが、上に書いたとおり時間計測が不安なので無理です。そもそも直線のはずのグラフが曲がりまくっています。

あと出来るのは既存ライブラリとの比較くらいです。しかしboost mplにqueueはあるのでしょうか。dequeはvectorと同じと書いてあるので使えなそうです。

Monadiusのメモリリークは簡単な方法では解決しませんでした。GlobalVariablesなどの変数を正則判定してみたり、ending の前にMonadiusを初期化してみたりしましたが効果なし。まじめにリークを探す必要がありそうです。

とりあえずupdateMonadius内にSCCタグを付けまくる作業開始。この関数がひどいという話を前にも書きました

Monadiusがメモリリークしていると聞いたので調べてみました。

  • 音が出ない版をダウンロード
  • 展開
  • .hsが全て小文字で始まっているので、それを大文字にリネーム
  • Main.hsのcreateWindowの前の行にgetArgsAndInitializeを足す。
    • glutを初期化してなかった!
  • $ ghc --make -O -prof -auto-all Main.hs
    • 次のエラーが出た場合、libghc6-glut-profパッケージ等プロファイラ用のパッケージを導入する。
Game.hs:5:7:
    Could not find module `Graphics.UI.GLUT.Callbacks.Window':
      Perhaps you haven't installed the profiling libraries for package GLUT-2.1.1.1? 
      Use -v to see a list of the files searched for.

多分データ型がlazyで、それが評価されるまで前のフレームのデータがずっと保持されているのではないかと当て推量しています。どうももっと重篤なバグで不要なオブジェクトが出来ている気もしますが。

プロファイリングオプションの説明が全く理解できなかったので、全部試してみました。画像が多いので全て続きに収容。

ここまでのグラフだとまだqueueの能力を殆ど計測できていない気がします。特に、今使用している構造はthunkを利用しているので、これの優位点が明らかになるような計測をしないと意味がありません。例えば次のようなものを測ればよさそうです。

  • コストのかかる計算をグラフで明らかにする。
  • その計算を直前から繰り返してもコストがかからないことを示す。
  • コストのかかるthunkが生成されている場所をグラフで示す。

あとはpushとpopがどんなパターンで入り乱れても遅くならないことを示せればすばらしいです。しかしどうすればいいのでしょう。全部列挙するというのもできなくはないですが意味のある結果が出せそうにありません。

さらに別のqueueたるBootstrapped Queueを実装し、この速度も見てみました。ソースは例によって続きに。

time cost of handling physicist's queue persistently.
Physicist's queueよりちょっと遅い。まあ誤差の範囲です。

前回書いたとおり、SimpleQueueでは操作にO(1)より長く時間がかかってしまう可能性があります。ならし平均で遅くなるところを何度も実行させられるとまずいです。

一方、Purely functional data structuresの6.4章にあるPhysicistsQueueならその問題はありません。ソースは続きに載せました。このQueueはReverseを早めに、thunkの形で行います。前にある要素より後ろにある要素の方が長くなったらthunkを作ります。こうするとよい感じです。何故良いかは本か論文を見てください。

前回と同じ計算をPhysicistsQueueにやらせた結果が次の図になります。base個の要素をあらかじめ載せたqueueに、「1個の要素をpushしてから先頭の要素を確認する」をSIZE回繰り返しています。Queueに載っている要素の数 base と関係なく、いつでも7 msec程度で操作を終えています。すばらしい。

time cost of handling physicist's queue persistently.

前回のグラフ(下の、log scale)と比較すると速度の差が明らかです。

time cost of handling simple queue persistently (log scale).

5月16日に修正。call by needをthunkに言い換えました。


C++ template metaprogrammingでthunkがちゃんとthunkになっていることを確認してみました。心配だったので。

確認のためのプログラムを書きます。型リストは例によって自作なので雰囲気だけ見てください。

#include <iostream>
#include "tlist.h"
#include "classname.h"
using namespace std;
using namespace TLAZY;  // namespace for my type-level list.

#ifndef SIZE
#define SIZE 10
#endif
#ifndef COUNT
#define COUNT 10
#endif

// Thunk.  Takes O(SIZE) time just to return IntType<SIZE-1>.
template<int n>
struct Lazied {
  typedef
  typename Head<
    typename Reverse<
      typename ListByRange<0, n>::type>::type>::type type;
};

template<typename F>  struct Apply : public F {};
// Evaluate the thunk $COUNT times.
typedef Map<Apply, Replicate<COUNT, Lazied<SIZE> >::type >::type Result;

int main() {
  cout << className(Phantom<Result>()) << endl;
}

計算にO(SIZE)時間かかるサンクをCOUNT回評価しています。SIZEとCOUNTを変化させつつコンパイルし、コンパイル時間を計測します。次のようになれば成功です。

  • COUNT = 0のときは計算時間はSIZEによらず一定。
  • COUNT > 0のときに計算時間はCOUNTによらずSIZEにのみ依存する。

評価に使用したコンパイラはg++4.3.3。Core 2 Duo 2GHzのマシンにUbuntu 9.04を載せたもので計測しました。コンパイラオプションは-DSIZE=xxxと-DCOUNT=xxxの他は-ftemplate-depth-10000のみ。

$ g++ --version
g++ (Ubuntu 4.3.3-5ubuntu4) 4.3.3
Copyright (C) 2008 Free Software Foundation, Inc.
This is free software; see the source for copying conditions.  There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

結果は次のとおり。左のグラフは横軸にCOUNT, 縦軸にコンパイル時間を、右のグラフは横軸にSIZE、縦軸にまたコンパイル時間を表しています。

Time cost of evaluating thunk, depending on how many times it is evaluated.Time cost of evaluating thunk, depending on SIZE.
ちゃんと高々一回だけ評価されているようです。SIZE > 1000で計算時間がSIZEに対して線形に伸びていないように見えるのが気になりますが、call by needの前では些細なことです。

前の記事のSimpleQueueは、このままでは計算量O(1)でPush, Pop, Topを行うことができません。時間のかかる場所はTopやPopでリストを逆転させているところで、ここにリストの要素数Nに比例した時間がかかります。そのため、Frontリストが空でRearリストにN個要素が入っている状態から何度もTopやPopを行うと、それぞれの動作にO(N)の時間がかかってしまいます。

「操作にO(N)時間かかることは稀で、平均すると計算量O(1)で済む」ということになっています。実際、普通の手続き型プログラミングでは、「ある状態からPopを何度も行う」ことはできません。一度Popを呼ぶとQueueの状態が変わり、それ以降の計算では時間がかからなくなります。

しかしC++型レベルプログラミングのような純粋関数型世界はそれほど甘くはありません。単純な実装では、操作にO(N)かかるような状態を使い回すことができてしまいます。何が言いたいかというとだいたい次のような感じ。

// よくある手続き型プログラム
q = ぎりぎりのQueue;
a = q.top();    // 時間がかかる。もうqはぎりぎりのQueueではない。
q.pop();
b = q.top();    // 時間かからない。

-- よくある純粋関数型プログラム
let q = ぎりぎりのQueue
    a = Queue.top q  -- 時間がかかる。
    q' = Queue.pop q -- 時間がかかる。
    b = Queue.top q' -- 時間がかからない。
    -- まだqはq'とは別の,まだぎりぎりのQueueとしてアクセスできる。

実際にこれをやるとどれだけ遅くなるかを実験してみました。BASESIZE個の要素を積んだQueueに、「1個要素を積んでから先頭の要素を取り出す」をSIZE回くりかえしてみました。かかった時間は以下のとおり。左が普通のスケールで、右はy軸を対数スケールにして小さい方も見えるようにしておきました。

time cost of handling simple queue persistently.time cost of handling simple queue persistently (log scale).
要素の積まれたQueueでは操作に時間がかかり、また何回繰り返しても同じように長い時間がかかっていることがわかります。前者はならし平均なら普通ですが、後者は問題です。

SIZEを50回に固定して、積んだ要素の数と計算時間との関係を示すと次のようになります。

time cost of handling simple queue persistently, ver. 2.
用いたプログラムは続きに載せました。

型レベルリストを二つ使用したQueueであるSimpleQueueをリファクタしました。以前の実装(本体遅い部分を直したもの)をベースに、前回のインターフェスを使うように書きなおしました。

// Queue共通のインターフェス。
template<typename Q_, typename A_> struct Push {};
template<typename Q_> struct Top {};
template<typename Q_> struct Pop {};
template<typename Q_> struct IsEmpty {};

// SimpleQueueの実体。
template<typename Front_, typename Rear_>
struct SimpleQueue {};

// 各種メソッドの実装。
template<>
struct IsEmpty<SimpleQueue<NullType, NullType> > {
  enum {value = 1};
};
template<typename Front_, typename Rear_>
struct IsEmpty<SimpleQueue<Front_, Rear_> > {
  enum {value = 0};
};

template<typename Front_, typename Rear_, typename A_>
struct Push<SimpleQueue<Front_, Rear_>, A_> {
  typedef SimpleQueue<Front_, TList<A_, Rear_> > type;
};

template<typename Rear_>
struct Top<SimpleQueue<NullType, Rear_> >
  : public Head<typename Reverse<Rear_>::type> {};
template<typename Hd_, typename Front_, typename Rear_>
struct Top<SimpleQueue<TList<Hd_, Front_>, Rear_> > {
  typedef Hd_ type;
};

template<typename Rear_>
struct Pop<SimpleQueue<NullType, Rear_> > {
  typedef SimpleQueue<typename Tail<typename Reverse<Rear_>::type>::type,
		      NullType> type;
};
template<typename Hd_, typename Front_, typename Rear_>
struct Pop<SimpleQueue<TList<Hd_, Front_>, Rear_> > {
  typedef SimpleQueue<Front_, Rear_> type;
};
// 空のSimpleQueue.
typedef SimpleQueue<NullType, NullType> EmptySimpleQueue;

前よりはるかに短くなりました。mpl方式は偉大です。

前の記事からの続き。

この先、SimpleQueueよりましなQueueの実装をいくつか試して、どれだけ違いが出るか確認する予定です。既に実装は他に二種できてます。ないのはテストコードとかプロファイラとか。あと清書。

Queueのインターフェスはちょっと変えました。struct内のstructを用意する代わりに、templateの特殊化で関数を実装することにしました。具体的にはこんなかんじ。

// Push<Queue, Item>::typeでitemを積んだ新しいQueueを返す。
// Primary templateはなにもなし。
template<typename Q_, typename A_> struct Push {};

// SimpleQueueの実装。
template<typename Front_, typename Rear_, typename A_>
struct Push<SimpleQueue<Front_, Rear_>, A_> {
  typedef SimpleQueue<Front_, TList<A_, Rear_> > type;
};

// Physicist Queue(未だ解説してません)での実装。
template<typename Evaled_, int front_size_, typename Front_,
	 int rear_size_, typename Rear_, typename A_>
struct Push<PhysicistQueue<Evaled_, front_size_, Front_, rear_size_, Rear_>,
	    A_> {
  typedef typename PhyQueue_Check<
      Evaled_, front_size_, Front_, rear_size_ + 1,
      TList<A_, Rear_> >::type type;
};

もちろん実際のコードではSimpleQueue用のコードとPhysicistQueue用のコードがこのように並べて書いてあったりはしません。同じPushの特殊化でも全く別々の場所に置けます。

何のQueueでもPush<Queue, A_>であつかえます。QueueはPush, Top, Pop, IsEmptyを提供します。

この書きかたのままだとうまく書けない関数があります。たとえば、Empty<SimpleQueue>::typeで空のSimpleQueueが得られる"Empty関数"があると良いのですが、これを書けません。

// SimpleQueue用の実装
typedef SimpleQueue<NullType, NullType> EmptySimpleQueue;
template<template<typename, typename> class Q>
struct Empty {
  typedef EmptySimpleQueue type;
};

// PhysicistQueue用の実装
typedef PhysicistQueue<NullType, 0, Id<NullType>,
		       0, NullType> EmptyPhysicistQueue;
template<template<typename, int, typename, int, typename> class Q>
struct Empty {
  typedef EmptyPhysicistQueue type;
};
// 実際にはこのようにEmptyを二回定義することはできません。

今の実装は実装の詳細をQueueのテンプレートに書いているため、それらを同じテンプレートで受けるのは不可能です。そのため上のEmpty関数は書けません。いくつか解決策はあります。

  • SimpleQueue<SimpleQueueImpl<Front, Rear> >のように、実装用のクラスを間にはさむ。すると違うQueueでも見た目のtemplateが同じになって受けられるようになる。
    • ヘッダファイルが長くなる。
  • 実装を全てSimpleQueueImplで行う。別に空のSimpleQueueクラスを用意して、Empty<SimpleQueue>::typeSimpleQueueImpl<NullType, NullType>を返すようにする。
    • ユーザがSimpleQueue用のコードを書こうとしたときにSimpleQueueが来ない。
  • EmptySimpleQueueやEmptyPhysicistQueueをSimpleQueue, PhysicistQueueと名付ける。
    • ユーザがSimpleQueue用のコードを書こうとしたときにSimpleQueueが来ない。
    • Empty*QueueはQueueそのものではない。美しくない。
    • どのQueueでも同じように扱えるので、正直Empty*Queue以外に実装の名前が出てくるところがない。ならここでその名前を使っても構わないと思う。

とりあえず最後のを採用したつもりで、Empty関数も*QueueImplも実装することなく書いています。

通勤中に読む本が無くなってしまったので、連休中は仕方なくBasic Category Theory for Computer Scientistsを読んでいました。この本は薄いので持ち運びに便利です。しかし正直圏論の本を机なしに読むのは無謀と言わざるをえません。というわけで今日から読むものをIntroduction to Information Retrievalのpdf版に変えてみました。さてどうなることやら。

Purely functional data structuresを読み終わりました。10章のbootstrappingがわりと山で、9章10章を読めていればそれ以前の難しいところもそれほど難しくない感じでした。

10章の型はすごく面白いです。なかなか説明するのがむつかしいですが。Bootstrapped QueueやPolymorphic recursionとかが出てきます。例えばGenerics > templatesなところ@d.y.dでちょっと書かれているようなことが出てます。

上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。