例を用いて、シミュレーションモデルの作成をサポートする priority queue のより一般的な使用を説明します。個別のイベント方式のシミュレーションは、一般的なシミュレーション手法です。シミュレーションモデルのオブジェクトは、実際のオブジェクトと可能な限り同じ反応をするようにプログラムが組まれています。priority queue は、発生を待機しているイベントの存在を格納するために使用されます。この待ち行列はイベントの発生予定時間に基づく順序で格納されるため、モデルとなる次のイベントは常に最小要素です。イベントが発生すると、これが他のイベントを発生させることができます。このような後続イベントも待ち行列に配置されます。すべてのイベントが処理されるまで、実行が継続します。
イベントは基底クラスのサブクラスとして表現することができ、これを event と呼びます。基底クラスは、単純にイベントが実行される時刻を記録します。イベントを実行するために、processEvent という名前の純粋な仮想関数が呼び出されます。
class event {
public:
event (unsigned int t) : time(t) { }
const unsigned int time;
virtual void processEvent() = 0;
};
シミュレーション待ち行列は、さまざまな型のイベントのコレクションを維持する必要があり、異種 コレクションと呼ばれることもあります。イベントのそれぞれの形式が event クラスのサブクラスによって表現されますが、全てがまったく同じ型の event ではありません。このため、コレクションは、イベント自体ではなく、 event へのポインタ5 を格納する必要があります。
注: コンテナは、値自体ではなく値へのポインタを維持するため、プログラマは、操作されるオブジェクトのためのメモリーを管理する必要があります。
ポインタの比較はポインタ型を元に特殊化することはできないため、代わりにイベントへのポインタのために新しい比較関数を定義する必要があります。標準 C++ ライブラリでは、適切な形式の関数呼び出し演算子 () を定義することを唯一の目的とする新しい構造を定義することによって、これを実行します。ここの例では、毎回、最大ではなく最小の6 要素を返すために priority queue を使用するので、次のように比較の順序が逆になります。
struct eventComparison {
bool operator () (event * left, event * right) const
{ return left->time > right->time; }
};
以上で、シミュレーションアクティビティの構造を提供するクラス simulation の定義を行う準備が整いました。クラス simulation は 2 つの関数を提供します。1 つは待ち行列に新しいイベントを挿入するために使用され、もう 1 つはシミュレーションを実行します。また、現在のシミュレーション time を保持するためのデータフィールドも提供されます。
class simulation {
public:
simulation () : eventQueue(), time(0) { }
void scheduleEvent (event * newEvent)
{ eventQueue.push (newEvent); }
void run();
unsigned int time;
protected:
priority_queue<event *, vector<event *>, eventComparison> eventQueue;
};
保留状態の event を保持するために使用される priority queue の宣言に注意してください。この場合、vector を配下のコンテナとして使用していますが、簡単に deque を使用することもできます。
シミュレーションの中心は、イベントループを定義するメンバー関数 run() です。この手続きは 5 つの priority queue 演算のうち、top()、pop()、empty() の 3 つを使用します。これは、次のように実行されます。
void simulation::run()
{
while (! eventQueue.empty()) {
event * nextEvent = eventQueue.top();
eventQueue.pop();
time = nextEvent->time;
nextEvent->processEvent();
delete nextEvent; // イベントで使用される空きメモリー
}
}
シミュレーションの枠組みの使用を説明するために、このプログラム例ではアイスクリーム店の単純なシミュレーションを行います。このようなシミュレーションを使用して、たとえば、顧客が来店する頻度、顧客が店で過ごす時間などに基づいて、用意する必要のある椅子の最適数を決定します。
注: 完全なイベントシミュレーションは icecream.cpp ファイルにあります。
店のシミュレーションは、クラス simulation のサブクラスに基づき、次のように定義されます。
class storeSimulation : public simulation {
public:
storeSimulation()
: freeChairs(35), profit(0.0), simulation() { }
bool canSeat (unsigned int numberOfPeople);
void order(unsigned int numberOfScoops);
void leave(unsigned int numberOfPeople);
private:
unsigned int freeChairs;
double profit;
} theSimulation;
3 つの基本的な行動である、来店、注文と飲食、退出が店に関連付けられています。これは、 simulation クラスで定義された 3 つのメンバー関数だけではなく、 event の 3 つの独立したサブクラスにも反映されます。
店に関連付けられたメンバー関数は、単純に実行される行動を記録し、シミュレーションを評価するために後で検証することができるログを作成します。
bool storeSimulation::canSeat (unsigned int numberOfPeople)
// 空席がある場合は、客を席に案内する
{
cout << "Time: " << time;
cout << " group of " << numberOfPeople << " customers arrives";
if (numberOfPeople < freeChairs) {
cout << " is seated" << endl;
freeChairs -= numberOfPeople;
return true;
}
else {
cout << " no room, they leave" << endl;
return false;
}
}
void storeSimulation::order (unsigned int numberOfScoops)
// アイスクリームを販売し、利益を計算する
{
cout << "Time: " << time;
cout << " serviced order for " << numberOfScoops << endl;
profit += 0.35 * numberOfScoops;
}
void storeSimulation::leave (unsigned int numberOfPeople)
// 客が退出し、空席ができる
{
cout << "Time: " << time;
cout << " group of size " << numberOfPeople <<
" leaves" << endl;
freeChairs += numberOfPeople;
}
すでに記述したように、各行動は event のサブクラスと一致します。 event の各サブクラスには、顧客のグループの人数を表す整数のデータフィールドが含まれます。グループが来店すると、来店イベントが発生します。実行されると、来店イベントは注文イベントの新しいインスタンスを作成し、インストールします。関数 randomInteger() は、整数 1 から引数値までの間の整数の乱数を算出するために使用されます (2.2.5 節を参照)。
class arriveEvent : public event {
public:
arriveEvent (unsigned int time, unsigned int groupSize)
: event(time), size(groupSize) { }
virtual void processEvent ();
private:
unsigned int size;
};
void arriveEvent::processEvent()
{ // 全員が着席できるかを確認する
if (theSimulation.canSeat(size))
theSimulation.scheduleEvent
(new orderEvent(time + 1 + randomInteger(4), size));
}
同様に、注文イベントが退出イベントを発生させます。
class orderEvent : public event {
public:
orderEvent (unsigned int time, unsigned int groupSize)
: event(time), size(groupSize) { }
virtual void processEvent ();
private:
unsigned int size;
};
void orderEvent::processEvent()
{ // 顧客 1 人当たりの注文した数
for (int i = 0; i < size; i++)
theSimulation.order(1 + rand(3));
theSimulation.scheduleEvent
(new leaveEvent(time + 1 + randomInteger(10), size));
};
最後に、退出イベントにより空席ができますが、新しいイベントは生成されません。
class leaveEvent : public event {
public:
leaveEvent (unsigned int time, unsigned int groupSize)
: event(time), size(groupSize) { }
virtual void processEvent ();
private:
unsigned int size;
};
void leaveEvent::processEvent ()
{ // 退出し、空席ができる
theSimulation.leave(size);
}
シミュレーションを実行するには、適当な数の初期イベントを単純に作成し (仮に 30 分とする)、run() メンバー関数を呼び出します。
void main() {
// いくつかの最初のイベントの待ち行列を読み込む
unsigned int t = 0;
while (t < 30) {
t += rand(6);
theSimulation.scheduleEvent(
new arriveEvent(t, 1 + randomInteger(4)));
}
// シミュレーションを実行し、利益を出力する
theSimulation.run();
cout << "Total profits " << theSimulation.profit << endl;
}