sorting - 事件模拟是否需要优先级队列？

Question

现在，在我的基本事件模拟引擎中，我只是简单地诉诸事件对象列表，以根据模拟的每个步骤的优先级进行更新。我这样做是因为可以在事件更新期间创建新事件并将其添加到列表中，并且当事件过期时，我只是将其与列表中的最后一个事件“交换并弹出”以提高性能。我应该只使用两个优先级队列吗？似乎对每个步骤进行排序的n log n至少与使所有事件出队列(n log n？)花费相同，如果不比将所有未过期事件放入另一个列表中的花费更低，该列表将内置到下一个更新步骤的优先级队列中。

编辑:我认为将“事件”称为“流程”更合适，然后将整个事件更多地称为流程调度模拟。队列中的每个对象都具有按优先级顺序更新的状态，然后仅当它已过期(进入某种结论状态)时，它才会被丢弃并且不会重新插入队列中。这就是仅拥有一个优先级队列的问题。重新插入对象时，它的优先级仍然最低，只会再次被拉出。我正在考虑使用第二个队列来插入所有新产生的过程对象以及未过期的对象，而不考虑优先级，那么我可以在下一个更新周期开始之前构建堆并将其与 Activity 队列交换。

Answer 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，它提供了几种事件队列实现，并且是开源的(免责声明:我是开发人员之一)。

编辑(解决重新制定的问题):

通常，实现基于过程的离散事件模拟的便捷方法是 coroutines，有关详细信息，请参见 this report。但是，如果您想坚持自己的实现，仍然可以将优先级更改为元组 (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()));     
}

当然，这假设您使用的事件队列实现足够通用，可以让您指定自己的时间/优先级排序，例如通过指定自定义比较器。