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

表題のとおり、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を使えば速いのではないか。

Queueの実装は次のとおり。プログラム中のNullType, TList, ReverseListは手製の型リストクラス、classNameはtypeid().name()のラッパーです。

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;
  };

  typedef typename front::car head;
  typedef SimpleQueue<typename front::cdr, rear> tail;
};

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

  template<typename N>
  struct snoc {
    typedef SimpleQueue<front, TList<N, rear> > type;
  };
  typedef typename ReverseList<rear>::type::car head;
  typedef SimpleQueue<typename ReverseList<rear>::type::cdr, NullType> tail;
};

template<>
struct SimpleQueue<NullType, NullType> {
  typedef NullType front;
  typedef NullType rear;
  enum { empty = 1 };

  template<typename N>
  struct snoc {
    typedef SimpleQueue<front, TList<N, rear> > type;
  };
};

typedef SimpleQueue<NullType, NullType> EmptyQueue;

template<typename Q_>
void printQueue(Phantom<Q_> qt) {
  (void)qt;
  std::cout << className(Phantom<typename Q_::head>()) << std::endl;
  printQueue(Phantom<typename Q_::tail>());
}

void printQueue(Phantom<EmptyQueue> qt) {
  (void)qt;
}

測定用プログラムは次のとおり。ListByRange<a, b>は、IntType<a>からIntType<b-1>までの(b-a)要素のリストを作る型関数です。SIZE要素を持つリストを作って、FoldRightで全てQueueにつっこんで、printQueueで頭から表示しています。

#include "tbase.h"
#include "tqueue.h"

#ifndef SIZE
#define SIZE 10
#endif

template<typename Item_, typename Q_>
class SnocFn {
public:
  typedef typename Q_::template snoc<Item_>::type type;
};

typedef FoldRight<SnocFn, EmptyQueue, ListByRange<0, SIZE>::type>::type Result;

int main(int argc, char* argv[]) {
  printQueue(Phantom<Result>());
}
スポンサーサイト
コメント
この記事へのコメント
グラフ見られない。なんでだろ -_-;

SimpleQueue<NullType, TL>
に要素をつっこむと、
SimpleQueue<NullType, TList<HD, TL> >
になってLazyじゃないからListReverseが毎回評価されるような。。。でもまだ2乗???
2009/04/21(火) 00:14 | URL | phoenix #z8Ev11P6[ 編集]
fc2だとリファラがおかしいと画像見られないかも。ここからだとwgetでも見えるのでちょっと謎ですが。

原因はそれっぽい。headをLazyにしないといけないのかな。面倒。
2009/04/21(火) 00:29 | URL | Gus #-[ 編集]
正解でした。Thanks。
2009/04/21(火) 00:34 | URL | Gus #-[ 編集]
コメントを投稿する
URL:
Comment:
Pass:
秘密: 管理者にだけ表示を許可する
 
トラックバック
この記事のトラックバックURL
http://gusmachine.blog49.fc2.com/tb.php/440-0d3fcd42
この記事にトラックバックする(FC2ブログユーザー)
この記事へのトラックバック
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。