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

前回書いたとおり、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).

Physicist's queueのソースです。 遅延すべき計算がちゃんと遅延しているのかあまり自信がありませんが。

template<typename Evaled_, int front_size_, typename Front_,
         int rear_size_, typename Rear_>
struct PhysicistsQueue {};

template<typename Evaled_, int front_size_, typename Front_,
         int rear_size_, typename Rear_>
struct PhyQueue_CheckW {
  typedef PhysicistsQueue<Evaled_, front_size_, Front_, rear_size_, Rear_>  type;
};

template<int front_size_, typename Front_,
         int rear_size_, typename Rear_>
struct PhyQueue_CheckW<NullType, front_size_, Front_,
                       rear_size_, Rear_> {
  typedef PhysicistsQueue<typename Front_::type,
                          front_size_, Front_, rear_size_, Rear_> type;
};

template<typename Evaled_, int front_size_, typename Front_,
         int rear_size_, typename Rear_>
struct PhyQueue_Check {
  // Thunk for concat<ls1, reverse<ls2> >.  We should delay reverse.
  // Called by Internal_Flip.
  template<typename Ls1, typename Ls2>
  struct RevConcat : public Concat<Ls1, typename Reverse<Ls2>::type> {};

  // Applied when front_size_ < rear_size_.
  // Should separate this to avoid early evaluation of Front_::type.
  template<int front_size2, typename Front2, int rear_size2, typename Rear2>
  struct Internal_Flip_ :
    public PhyQueue_CheckW<typename Front2::type, front_size2 + rear_size2,
                           RevConcat<typename Front2::type, Rear2>,
                           0, NullType> {};

  // typedef typename Internal<front_size_ >= rear_size_>::type type;
  typedef typename If_<front_size_ >= rear_size_,
    PhyQueue_CheckW<Evaled_, front_size_, Front_, rear_size_, Rear_>,
    Internal_Flip_<front_size_, Front_, rear_size_, Rear_> >::type::type type;
};

template<typename Evaled_, int front_size_, typename Front_,
         int rear_size_, typename Rear_, typename A_>
struct Push<PhysicistsQueue<Evaled_, front_size_, Front_, rear_size_, Rear_>,
            A_> :
   public PhyQueue_Check<Evaled_, front_size_, Front_, rear_size_ + 1,
                         TList<A_, Rear_> > {};

template<typename Head_, typename Tail_, int front_size_, typename Front_,
         int rear_size_, typename Rear_>
struct Top<PhysicistsQueue<TList<Head_, Tail_>, front_size_, Front_,
                           rear_size_, Rear_> > {
  typedef Head_ type;
};

template<typename Head_, typename Tail_, int front_size_, typename Front_,
         int rear_size_, typename Rear_>
struct Pop<PhysicistsQueue<TList<Head_, Tail_>, front_size_, Front_,
                           rear_size_, Rear_> > {
  // Thunk of Tail.
  template<typename Ls_>
  struct DelayTail : public Tail<typename Ls_::type> {};
  typedef typename PhyQueue_Check<Tail_, front_size_ - 1,
                                  DelayTail<Front_>,
                                  rear_size_, Rear_>::type type;
};

typedef PhysicistsQueue<NullType, 0, Id<NullType>,
                        0, NullType> EmptyPhysicistsQueue;

template<typename Q_>
struct IsEmpty<PhysicistsQueue<NullType, 0, Q_, 0, NullType> > {
  enum {value = 1};
};

template<typename Evaled_, int front_size_, typename Front_,
         int rear_size_, typename Rear_>
struct IsEmpty<PhysicistsQueue<Evaled_, front_size_, Front_,
                               rear_size_, Rear_> > {
  enum {value = 0};
};
スポンサーサイト
コメント
この記事へのコメント
コメントを投稿する
URL:
Comment:
Pass:
秘密: 管理者にだけ表示を許可する
 
トラックバック
この記事のトラックバックURL
http://gusmachine.blog49.fc2.com/tb.php/450-330bbb0f
この記事にトラックバックする(FC2ブログユーザー)
この記事へのトラックバック
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。