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

Queueが遅くなる原因がわかったので、それを直します。SimpleQueue::head, SimpleQueue::tailが呼びもしないのに実行されているのが原因なので、呼ぶまで実行されないようなコードに変更します。元のコードのhead, tailをstructで囲めば終了。

template<typename Front_, typename Rear_>
struct SimpleQueue {
  typedef Front_ front;
  typedef Rear_ rear;
  enum { empty = 0 };

  template<typename N>
  struct snoc {
    typedef SimpleQueue<front, TList<N, rear> > type;
  };
  struct head {
    typedef typename front::car type;
  };
  struct tail {
    typedef SimpleQueue<typename front::cdr, rear> type;
  };
};
// 以下特殊化部分も同様に変更。

計算結果。ちゃんと高速で動いています。

timequeue_foldright_fast.png

スポンサーサイト

前回の記事のコメントの通り、Queue::headがLazyじゃないのが原因でした。先頭リストが空のQueueが作られる度に、Queue::headが自動的に呼ばれていました。これを確認するには、あらかじめ先頭リストに何か物を入れてから同じプログラムを走らせればよいです。

typedef EmptyQueue::
          snoc<IntType<-1> >::type::
          snoc<IntType<-2> >::type::
          tail OneQueue;
typedef FoldRight<SnocFn, OneQueue, ListByRange<0, SIZE>::type>::type Result;

int main(int argc, char* argv[]) {
  printQueue(Phantom<Result>());
}

結果は次のとおり。今回のグラフが左/上、以前のが右/下です。

time const of handling queue correctly.Time cost of handling queue.
グラフの形が違うとかそれ以前に時間が圧倒的に違います。100倍の高速化に成功しました^^);

昨日の記事のつづき。とりあえずlistが遅くないことを確認します。まずはListByRange操作の速度を確認。コードは追記に載せました。

time cost of handling a list.
SIZE<250では線形に見えます。ちょっと歪んでいる気もしますが。

ところでSIZE>250でグラフが変です。実はここから先はテンプレートの再帰の深さ制限に引っかかっていて、コンパイルが通っていません。

$ g++ -DSIZE=250 testlist.cc
tlist.h:24: error: template instantiation depth exceeds maximum of 500 (use -ftemplate-depth-NN to increase the maximum) instantiating ‘struct ListByRange<250, 250>’
tlist.h:24:   instantiated from ‘ListByRangeWrap<false, 249, 250>’
tlist.h:19:   instantiated from ‘ListByRange<249, 250>’
tlist.h:24:   instantiated from ‘ListByRangeWrap<false, 248, 250>’

(snip)

tlist.h:24:   instantiated from ‘ListByRangeWrap<false, 0, 250>’
tlist.h:19:   instantiated from ‘ListByRange<0, 250>’
testlist.cc:13:   instantiated from here

tlist.h:24: error: invalid use of incomplete type ‘struct ListByRange<250, 250>’
tlist.h:18: error: declaration of ‘struct ListByRange<250, 250>’
testlist.cc: In function ‘int main(int, char**)’:
testlist.cc:16: error: ‘Result’ was not declared in this scope
testlist.cc:16: error: template argument 1 is invalid

gccのオプション -ftemplate-depth-"$SIZE"を使えばもっと再帰できます。デフォルトは500段。

さらにfoldrとreverseの速度を確認。こちらも遅くはなさそうです。foldrは中身が簡素すぎてうまく時間が計測できていませんが。

time cost of reversing a list.time cost of foldrighting a list.

表題のとおり、C++で型レベルQueueを作ってみたところ、操作にO(N^3)倍くらい余計に時間がかかっています。原因が全く不明。

Queueはリストを二つ使えば作れます。プログラムは追記にあります。これにN個の要素を積み、前から順に全ての要素を取り出して出力するという操作を行い、その時間を計測しました。正しくQueueが実装されていれば、全ての操作はならし定数時間で行われ、全体としてO(N)時間かかるはずです。

結果は次の通り。

Time cost of handling queue.Time cost of handling a queue (log scale).
左の図が普通のscale, 右のは両対数グラフです。サイズの4乗に比例する線でだいたいフィッティングできました。フィッティングが適当なのであまり強いことは言えませんが、最低でもこれは線形とは言いがたいです。何がここまで時間をかけているのでしょうか。

環境は次のとおり。

  • Intel(R) Core(TM)2 CPU T7200 @ 2.00GHz x 2
  • Linux version 2.6.28-11-generic
  • g++ (Ubuntu 4.3.3-5ubuntu4) 4.3.3
  • amd64

遅くなった原因を調べてみます。最低でも以下のことは確認する必要があります。

  • TListの実装はまともなのか。ここで遅くなってはいないのか。
    • TList生成過程で遅くなってないか。
    • TListをreverseするのに時間がかかってないか。
  • TQueueのどの操作で遅くなっているのか。
  • boost::mplを使えば速いのではないか。

型レベルプログラミングの会にいってきました。何度もコンパイラに整数計算を強制させるアツい会でした。

C++の可変長テンプレートを使うと型リストが異常に定義しやすくなっていて衝撃でした。cons cell定義しなくても型リストが使えます。どうしたC++。

template <typename... Args>
class Hoge {};  // Primary template.

template <>
class Hoge<> {};  // template with [].

template <typename Head, typename... Tail>
class Hoge<Head, Tail...>  {};  // template with cons.

パターンマッチさえあればcons cellは不要でしたの巻。

さらに、"..."で自明な繰り返しを表現できます。そのため、再帰せずにmapが定義できます。ちなみにこの...の使い方は他の何かの言語でもあった覚えがあります。どの言語か忘れてしまいましたが、...を複数使った時にどのようにループするかの定義があったはず。

scalaはとりあえずインストールしてみないといけないと思いました。それから正直Haskellの型レは私が慣れてなさすぎるのか全くついていけませんでした。ちょっといろいろ読まないといけない。FunDepsの何故型チェック通らないのかの下りとかが掴めませんでした。Prologと違って型がバックトラック無しに単一に解決できないといけないからかしら。

Purely functional data structuresを読んでいます。はるか昔に買ったものの、半分も読まずに中断していました。一部理解できなかったところを飛ばしつつ、9章の半分まで読んだところです。

6章以降は感動の嵐でした。この手のデータ構造は普通思いつきません。ちょっとこれはプログラマとして読んでおいたほうが良い本リストのtop 10に入ると思います。詳しい解説はまた今度。

9章のredundant binary numbersが完全にFinger Treeの基礎と同じでした。ならしO(1)でpush, popができて、O(log N)でindex accessができます。ここまで読めていれば、Finger Treeも、「Lazyにしておくと嬉しい」も簡単に理解できます。

6章のphysicist method based amortization with persistenceがまだ良く理解できていません。p. 70のBinomial Heapsは次のように理解すれば良いのでしょうか。

  • insertはいくらでも遅らせてよい。少なくともfindmin, deletemin, mergeが来るか、次のポテンシャル0まで遅らせてよい。insertの際に評価を強制する必要は全くない。
  • findmin, deletemin, mergeはどうせO(log N)かかるので、ついでにinsertの評価を行なってもO(log N)は変わらない。
  • emptyはあらかじめ結果を保存しておくことでO(1)を実現できる。

これは実は今日の帰りの電車で思いつきました。これで良さそうなら、他のphysicist methodの話を読んでから先に進みます。

mplを理解しようとして自作でTListを書いてみました。

template<typename CAR_, typename CDR_>
class TList {
public:
  typedef CAR_ car;
  typedef CDR_ cdr;
};

class NullType {
};

template<int N>
class IntType {
public:
  enum {value = N};
};

template<int n, int m> class ListByRange;
template<bool b, int n, int m> class ListByRangeWrap;

template<int n, int m>
class ListByRange {
public:
  typedef typename ListByRangeWrap<m == n, n, m>::type type;
};

template<int n, int m>
class ListByRangeWrap<false, n, m> {
public:
  typedef typename TList<IntType<n>,  // 34
			 typename ListByRange <n + 1, m>::type> type; //35
};

template<int n, int m>
class ListByRangeWrap<true, n, m> {
public:
  typedef NullType type;
};

これに対して次のエラーが出ます。34行と35行は上にコメントを書きました。

tlist.h:34: error: expected nested-name-specifier
tlist.h:35: error: invalid declarator before ‘type’

これ何だったかしら。全然思い出せないのであとで調べます。ちなみに当該行の型全ての手前に::を付けても無駄でした。

この日記のテンプレートを変更しました。

いままでのテンプレートはプログラムの貼り付けに向いていませんでした。

  • 長い<pre>行の右側を容赦なく切る。
  • 固定長で、どれだけ横幅を広げても決まった範囲しか見えない。

これはプログラムブログ向きではありません。

テンプレートを改造してもよいのですが、他のテンプレートを探してくることで妥協しました。条件は以下のとおり。

  • 2カラムでよい。
  • できれば可変長。
  • CSSを切ったときにも適切に見えるようにする。

fc2テンプレートリストから適当に見つけてきました。[2カラム(|左|右), 画像無し]で探したらわりとましなものが見つかったので採用。上の条件のほとんどをクリアしていました。手直しは一箇所だけ。firebugで観察したところ、無駄なtableタグがあったので消去してdivに変更しました。

見たところちょっと字が詰まりすぎかもしれません。また適当に手直しします。

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