3

現在、基本的なイベントシミュレーションエンジンでは、イベントオブジェクトのリストを再利用して、シミュレーションのすべてのステップで優先度を更新します。これを行うのは、イベントの更新中に新しいイベントを作成してリストに追加でき、イベントの有効期限が切れたら、パフォーマンスのためにリストの最後のイベントと「スワップアンドポップ」するだけだからです。代わりに2つの優先キューを使用する必要がありますか？すべてのイベントをソートするnlognは、すべてのイベントをデキューする（n log n？）よりもコストがかからない場合でも、少なくとも同じように見えます。有効期限が切れていない各イベントを、次の更新ステップの優先キューに組み込まれている別のリストに入れます。 。

編集：「イベント」を「プロセス」と呼び、全体をプロセススケジューリングシミュレーションと呼ぶ方が適切だと思います。キュー内の各オブジェクトの状態は優先順位に従って更新され、有効期限が切れた（ある種の結論状態に入った）場合にのみ、オブジェクトは破棄され、キューに再挿入されません。これが、優先キューが1つしかないことが問題になる可能性がある方法です。オブジェクトが再挿入された場合でも、優先度は最も低く、再び引き出されます。優先度を考慮せずに、新しく生成されたすべてのプロセスオブジェクトと有効期限が切れていないプロセスオブジェクトを挿入するために2番目のキューを使用することを検討していました。その後、ヒープを構築し、次の更新サイクルの開始前にアクティブキューと交換することができました。

4

1 に答える 1

1

通常、(シーケンシャル) 離散イベント シミュレーターでは1 つのイベント キューを使用する必要があります。「期限切れ」イベントの意味がよくわかりませんが、これらのイベントが無効になったために無視される場合、単純な解決策は、処理する代わりに破棄することです。たとえば、次の疑似 Java コードを参照してください。

 while (!terminationConditionMet() && !eventQueue.isEmpty()) {
   Event currentEvent = eventQueue.getNextEvent();
   if(currentEvent.isExpired())
     continue;
   List<Event> newEvents = currentEvent.process();
   eventQueue.addEvents(newEvents); 
 }

一般に (十分な大きさのイベント セットの場合)、これは、各ステップの後にイベント リストを再ソートするよりもはるかに高速です。

ところで、多くのイベント キューの実装は O(1) でデキューを実現します。一部の操作では、最悪の場合のパフォーマンスが並べ替えよりも優れていない可能性がありますが、実際の実装ははるかにうまく機能します (つまり、定数が小さくなり、平均パフォーマンスが向上します)。Java を使用している場合は、いくつかのイベント キューの実装を提供し、オープン ソースであるJAMES IIを参照することをお勧めします (免責事項: 私は開発者の 1 人です)。

編集（再定式化された質問への対処）：

一般に、プロセスベースの離散イベント シミュレーションを実装する便利な方法はコルーチンです。詳細については、たとえばこのレポートを参照してください。ただし、実装に固執したい場合は、優先度をタプルに変更し(timeStep,processPriority)、上記の疑似コードの適合バージョンを次のように使用できます。

while (!terminationConditionMet() && !queue.isEmpty()) {

 //Read out event
 Tuple minTime = queue.getMinTime();
 ProcessEvent currentEvent = queue.dequeue();

 //Execute event
 List<ProcessEvent> newlySpawnedProcesses = processEvent.process();

 //Re- and enqueue new events
 int nextTimeStep = minTime.getTime() + 1;
 if(!currentEvent.finalStateReached())
   queue.requeue(currentEvent, new Tuple(nextTimeStep, currentEvent.getPriority())); 
 for(ProcessEvent event : newlySpawnedProcesses)
   queue.enqueue(event, new Tuple(nextTimeStep, event.getPriority()));     
}

もちろん、これは、カスタム コンパレータを指定するなどして、独自の種類の時間/優先度の順序を指定できるように十分に汎用的なイベント キューの実装を使用していることを前提としています。

于 2012-07-07T13:59:34.193 に答える