什么是日历队列？

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，应该在今年秋季的某个时候编入索引。如果您想要一份副本，请发表评论，我会将其发送给您。

要回答问题的不同部分，您可以将日历队列视为优先级队列，该优先级队列针对优先级不断降低的事件进行了优化。通常情况下，事件的优先次序（时间）以某种方式分类，以避免必须触及所有事件才能插入一个事件（可能会发生在某些形式的堆管理中）。