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

前の記事の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.
用いたプログラムは続きに載せました。

今回の計測に用いたプログラムです。このBASESIZEやSIZEをコマンドラインで変化させて、コンパイル時間の変化を見ていました。

#include <iostream>
#include <string>
#include "tqueue.h"    // Type Queue.
#include "classname.h" // For className function.

#ifndef BASESIZE
#define BASESIZE 10
#endif
#ifndef SIZE
#define SIZE 10
#endif
#ifndef QUEUE
#define QUEUE EmptySimpleQueue
#endif

// Queue with n numbers.
// ListByRange<0, N>::type = TList<0, TLIST<1, ..., N-1, NullType> > .. >.
typedef FoldLeft<Push, QUEUE, ListByRange<0, BASESIZE>::type>::type InitialQueue;

template<typename Item_>
struct PushAndTop {
  typedef typename Top<typename Push<InitialQueue, Item_>::type>::type type;
};

// listのmap関数。これで繰り返す。
typedef Map<PushAndTop, ListByRange<0, SIZE>::type>::type Result;

using namespace std;
int main(int argc, char* argv[]) {
  cout << className(Phantom<Result>()) << endl;
  return 0;
}
スポンサーサイト
コメント
この記事へのコメント
コメントを投稿する
URL:
Comment:
Pass:
秘密: 管理者にだけ表示を許可する
 
トラックバック
この記事のトラックバックURL
http://gusmachine.blog49.fc2.com/tb.php/448-7b5912b2
この記事にトラックバックする(FC2ブログユーザー)
この記事へのトラックバック
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。