什么是日历队列？

Question

什么是日历队列？

algorithmlanguage-agnosticdata-structuressimulationpriority-queue

11

我正在开发一个离散事件模拟器。维基百科提到有几种通用的优先队列适用于离散事件模拟器。具体来说，它提到了日历队列是一种很好的数据结构。我找到了一份1988年的pdf文件提到了日历队列，但大多数情况下我找不到其他相关信息。请问有人可以解释一下什么是日历队列，它们如何使用以及我在哪里可以找到样例实现？

- fbl

3个回答

8

通过谷歌搜索，找到了一篇名为“离散事件模拟器中日历队列优化桶宽度的研究”的论文。

链接如下：http://pioneer.netserv.chula.ac.th/~achaodit/paper5.pdf

其中第二部分介绍了日历队列。

- Rob Raisch

谢谢 - 尽管从那个描述来看，它似乎只是一堆均匀间隔的优先队列。 - fbl

4

NIST定义：

一种快速优先队列实现，每个桶的宽度为w，或覆盖w时间。具有比当前优先级p更高的项目进入桶（p/w）％N。选择N和w使每个桶中的项目较少。保持桶内项目排序。如果项目数量增加或减少，则将N加倍或减半并更改w。

Paul E. Black，“calendar queue”，收录于《算法和数据结构词典》[在线]，Vreda Pieterse和Paul E. Black编辑，2005年1月24日。（访问日期：2014-03-10）可从http://www.nist.gov/dads/HTML/calendarQueue.html获取。

- pintxo

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Richard · Accepted Answer

是的，Brown 1988 是我所知道的第一篇描述日历队列的论文，尽管Brown提到了几位先于他的作者。以下是一个相对完整的日历队列文献目录以及每篇论文的笔记。如果您需要任何出版物的副本，请给我留言。

Vaucher 1975 活动列表算法比较。同时介绍了三个新算法。Brown1988受此启发。
Henricksen 1977 活动列表算法-适应间隔时间，与多种分布表现良好，基于Vaucher和Duval。
Ulrich 1978 Brown1988声称这是O（1），除了溢出列表。
Jones 1986 比较优先级队列，有一个早期版本的日历队列。
Brown 1988 引入日历队列[又称：排序学科日历队列]
Davison 1989 发现相同的事情，并提到了一些重要改进，Brown在同一封信中承认了这些改进，并有自己的想法。 Davison认为Jones 1986提供了一些有价值的日历机制。
Ronngren 1991 懒队列。一种日历队列，具有接近、远期和非常远期的未来-这使得延迟排序成为可能，在他们的测试中大大加快了速度。
Steinman 1994 事件地平线。生成的事件有一定的概率分布，让我们用此确定需要排序的内容。允许并行模拟。
Steinman 1996 事件地平线第二部分。将Steinman1994应用于事件列表管理。修改其他数据结构以供CQ使用。
Ronngren 1997 比较许多不同的日历队列。懒队列表现良好，但Brown1988经常表现更好。LazyQ和SCQ最坏情况下表现糟糕，Skew Heap和Sply Tree最坏情况下表现最佳。
Oh 1997 动态懒惰日历队列。改善了不平衡事件分布下传统CQ的性能。
Oh 1999 动态日历队列。适用于分布不均匀的情况，表现良好。
Cazzolla 1998 懒惰队列的Java实现及其分析（非学术论文）。
Tan 2000 SNOOPy：在最佳运行参数CQ的基础上增强了统计学特性。使用统计测试来创建更好的桶。在某些场景下运行速度比DCQ和CQ快100倍。
Hui 学位论文本科论文，详细描述了Hui 2002论文以及其他日历队列实现的优缺点。
Hui 2002 未来事件不需要立即排序，因此优先队列的大小可以被限制，在减少调整大小开销的同时也可以减小内存占用。
Goh 2003 MList。多层链接列表消除调整大小操作。通过实验显示，至少比Calendar Queue、Dynamic CQ、SNOOPy CQ、2层Dynamic Lazy CQ和3层Lazy Queue 快100%。
Siangsukone 2003 CQ中优化的桶宽度。演示了桶宽度对性能有显著影响。
Goh 2004 DSplay。消除昂贵的调整大小操作。至少比其他日历队列快100%。
Tang 2005 梯形队列。即使在具有无限方差的队列分布下，也提供了稳定的O(1)性能。类似于Lazy Queue，但更好。
Yan 2006 缓慢的日历队列。当事件大多按顺序插入时，可以利用某些统计特性实现2阶速度提升。
Himmelspach 2007 事件具有持续时间-不属于主要研究方向。需要额外的功能，该算法提供了这种功能，但可能有一定的后续工作。

此外，我们最近描述了布朗算法的一种变体，应该会表现更好。我认为描述已经相当充分，可以建立实现，并且样例代码在论文中提供。该出版物名为《用空间换时间：科学模拟中管理未来事件的恒定速度算法》（Lehman、Keene和Barnes），预计今年秋季之前将被编入索引。如果您想要一份副本，请留言，我会把它发送给您。

回答您问题的另一部分，您可以将日历队列视为针对具有不断降低优先级的事件进行优化的优先队列。通常以某种方式对事件的优先级（时间）进行分组，以避免必须触碰所有事件才能插入一个新事件（这可能会发生在某些堆管理形式中）。