事件模擬是否需要優先隊列？

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

當然，這是假定你是使用足夠通用的事件隊列實現，以允許您指定自己的時間/優先級順序，例如通過指定自定義比較器。