什麼是日曆隊列？

Question

我正在構建一個離散事件模擬器。維基百科提到，有幾個通用優先級隊列很適合在DES中使用。具體來說，它提到日曆隊列是一個很好的結構。我發現了一個提到日曆隊列的pdf（從1988年開始），但大多數情況下我都找不到關於它們的其他內容。有人會介意解釋日曆隊列是什麼，它們是如何使用的，以及在哪裏可以找到示例實現？

Answer 1

谷歌搜索發現在日曆隊列優化鬥寬度

研究的離散事件仿真

http://pioneer.netserv.chula.ac.th/~achaodit/paper5.pdf

其中描述了第2部分中的日曆隊列。

Answer 2

定義由NIST：

具有快速優先級隊列執行N各自水桶寬度w，或覆蓋瓦特時間。具有比當前優先級更高的項目進入桶（p/w）％N。選擇N並且每個存儲桶中只有少量項目。保持項目在桶內分類。如果項目數量增加或減少很多，則將N加倍或減半並更改w。

Paul E. Black，「日曆隊列」，在Dictionary of Algorithms and Data Structures [在線]，Vreda Pieterse和Paul E.Black，eds。 24 2005年1月（2014年3月10日訪問），可從：http://www.nist.gov/dads/HTML/calendarQueue.html

Answer 3

是的，Brown 1988是我知道的第一篇描述日曆隊列的文章，雖然布朗我在他之前的幾位作者。以下是日曆隊列文獻的相對完整的參考書目以及每篇論文的筆記。如果您想要任何出版物的副本，請給我留言。

• Vaucher 1975比較事件列表算法。介紹三種新算法。啓發布朗1988。
• Henricksen 1977和事件列表算法 - 適應的間隔時間，並用數分佈的基礎上，Vaucher和杜瓦爾
• 烏爾裏希1978 Brown1988聲稱這是O（1），除了溢出列表
• 瓊斯表現良好1986年比較優先級隊列，具有日曆隊列的早期版本
• 布朗1988年推出日曆隊列[又名：分類學科的日曆隊列]
• 戴維森1989年發現的一樣，提到了一些重要的改進，布朗承認在改進同一封信，並有自己的一些想法。 Davison建議Jones 1986提供了一些有價值的日曆機制
• Ronngren 1991 The Lazy Queue。一個擁有近遠遠未來的日曆隊列 - 這可以實現延遲排序，從而在測試中大幅提高速度
• Steinman 1994 Event Horizo​​n。生成的事件發生時具有一定的概率分佈，讓我們用它來確定需要排序的內容。允許並行模擬
• Steinman 1996 Event Horizo​​n第2部分。將Steinman1994應用於事件列表管理。修改用於CQ的其他數據結構。
• Ronngren 1997比較許多不同的日曆隊列。 Lazy Queue表現不錯，但Brown1988經常表現更好。 LazyQ和SCQ的最壞情況表現不好，偏斜堆和Sply樹的最壞情況。
• 哦1997年動態懶惰日曆隊列。通過不均勻事件分佈提高常規CQ的性能
• Oh 1999動態日曆隊列。適用於不均勻分佈
• Cazzolla 1998帶分析功能的Lazy Queue的Java實現（不是學術論文）。
• Tan 2000 SNOOPy：通過最佳運行參數CQ進行統計增強。使用統計測試來製作一個桶。在某些情況下，運行速度比DCQ和CQ快100倍
• Hui論文描述Hui 2002論文的許多細節以及其他日曆隊列實施的利弊
• Hui 2002未來事件不需要現在排序;因此，優先級隊列本身的大小可能會受到限制，從而減少調整大小的開銷。
• Goh 2003 MList。多層鏈接列表消除了調整大小的操作。實驗顯示比Calendar Queue，Dynamic CQ，SNOOPy CQ，兩層動態延遲CQ和三層延遲隊列至少快100％Sangsukone 2003 CQ中優化的剷鬥寬度。演示了剷鬥寬度會對性能產生重大影響。
• Goh 2004 DSplay。消除昂貴的調整大小操作。至少比其他日曆隊列快100％。
• 唐2005梯隊。即使在具有無限變化的隊列分佈下也能提供穩定的O（1）性能。類似於Lazy Queue，但更好。
• 嚴2006年緩慢的日曆隊列。當事件大多按順序插入時，可以使用一些統計屬性來實現2階加速。Himmelspach 2007事件具有持續時間 - 不在主要研究範圍內。需要額外的功能，這種算法提供了它，但可能有限的後續工作。

此外，我們最近完成了描述布朗算法的一個變體，它應該表現更好。描述是，我認爲這篇文章提供了一個實現和示例代碼的充分的充分性。該出版物標題爲雷曼，基恩和巴恩斯的Trading Space for Time: Constant-Speed Algorithms for Managing Future Events in Scientific Simulations，應該在今年秋季的某個時候編入索引。如果您想要一份副本，請發表評論，我會將其發送給您。

要回答問題的不同部分，您可以將日曆隊列視爲優先級隊列，該優先級隊列針對優先級不斷降低的事件進行了優化。通常情況下，事件的優先次序（時間）以某種方式分類，以避免必須觸及所有事件才能插入一個事件（可能會發生在某些形式的堆管理中）。