CODEWITHSUNDEEP
sortingheapsimulationpriority-queueheapsort
abr
abr

Reputation: 33

Is a priority queue necessary for event simulation?

Right now in my basic event simulation engine, I simply just resort the list of event objects to update by their priorities every step of the simulation. I do this because new events can be created during event updates and are appended to the list and when an event expires, I just "swap and pop" it with the last event in the list for performance. Should I just be using two priority queues instead? It seems like the n log n of sorting every step is at least the same if not less costly than dequeing all the events (n log n?) putting each unexpired one in another list that is built into the priority queue for the next update step.

EDIT: I think it would be more apt to refer to the 'events' as 'processes' instead and the whole thing as more of a process scheduling simulation then. Each object in the queue has it's state updated in priority order and then only if it has expired (entered some sort of conclusion state) does it get discarded and not reinserted into the queue. This is how having just a single priority queue could be a problem; when an object is reinserted, it will still have the lowest priority and would just be pulled out again. I was considering using a second queue to insert all newly spawned process objects and ones that did not expire into, not considering priority, then I could just build heap and swap it with the active queue before the start of the next update cycle.

Upvotes: 3

Views: 2815

Answers (1)

Roland Ewald
Roland Ewald

Reputation: 4614

Typically, you should use one event queue in a (sequential) discrete-event simulator. I am not quite sure what you mean with 'expired' events, but if these events shall be ignored because they are not valid anymore, a simple solution would be to just discard them instead of processing them, e.g. see this pseudo Java code:

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

Generally (for large enough event sets), this should be much faster than re-sorting the event list after each step.

BTW many event queue implementations achieve a dequeue in O(1), and even though for some operations their worst case performance might not be better than sorting, the actual implementations work much better (i.e. they have smaller constants/better average performance). If you are working with Java, you might want to look at JAMES II, which offers several event queue implementations and is open source (disclaimer: I am one of the devs).

EDIT (addressing re-formulated question):

In general, a convenient way of implementing a process-based discrete-event simulation are coroutines, see for example this report for details. If you want to stick to your implementation, however, you could still change the priority to a tuple (timeStep,processPriority) and use an adapted version of the above pseudo-code as follows:

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

Of course, this assumes that you are using an event queue implementation that is generic enough to allow you to specify your own kind of time/priority ordering, e.g. by specifying a custom comparator.

Upvotes: 1

Related Questions