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

Question

现在，在我的基本事件模拟引擎中，我只需简单地使用事件对象的列表来根据每个模拟步骤的优先级更新它们。我这样做是因为新事件可以在事件更新期间创建，并附加到列表中，当事件到期时，我只需使用列表中的最后一个事件“交换并弹出”它以获得性能。我应该只使用两个优先级队列吗？看起来像每个步骤排序的n日志至少是相同的，如果不低于分出所有事件（n log n？）的成本，则将每个未到期的日志放入另一个列表中，该列表内置于下一个更新步骤的优先级队列中。

编辑：我认为这会更倾向于将“事件”称为“过程”，而将整个过程称为进程调度模拟。队列中的每个对象都会按照优先级顺序更新状态，并且只有当它已经过期（进入某种结束状态）时才会被丢弃并且不会重新插入到队列中。这就是如何拥有一个优先队列可能成为一个问题;当一个对象被重新插入时，它仍然具有最低的优先级，并且会被重新拔出。我正在考虑使用第二个队列来插入所有新生成的进程对象和没有过期的进程对象，而不考虑优先级，然后我可以在下一个更新周期开始之前构建堆并将其与活动队列交换。

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

EDIT（寻址重新配制问题）：

一般而言，实施过程基于离散事件模拟的一种方便的方法是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()));  
} 

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