Ric*_*ard
18
是的,布朗1988是我所知道的第一篇描述日历队列的论文,尽管布朗提到了几位先于他的作者.下面是日历队列文献的相对完整的参考书目以及每篇论文的笔记.如果您想要任何出版物的副本,请给我评论.
- Vaucher 1975比较事件列表算法.还介绍了三种新算法.灵感来自Brown1988.
- Henricksen 1977事件列表算法 - 基于Vaucher和Duval,适应间隔时间并在许多分布中表现良好
- Ulrich 1978 Brown1988声称这是O(1),除了溢出列表
- Jones 1986比较优先级队列,具有日历队列的早期版本
- Brown 1988推出Calendar Queue [aka:Sorted-discipline Calendar Queue]
- 戴维森1989发现同样的事情,提到了一些重要的改进,布朗承认同一封信的改进,并有一些自己的想法.戴维森表示琼斯1986年提供了一些有价值的日历机制
- Ronngren 1991 The Lazy Queue.一个具有近,远和远未来的日历队列 - 这可以实现延迟排序,从而大大加快了测试速度
- 斯坦曼1994年的事件地平线.生成的事件在发生时会有一些概率分布,让我们用它来确定需要排序的内容.允许并行模拟
- Steinman 1996 Event Horizon Part 2.将Steinman1994应用于事件列表管理.修改其他数据结构以在CQ中使用.
- Ronngren 1997比较许多不同的日历队列.Lazy Queue表现不错,但Brown1988经常表现更好.LazyQ和SCQ具有糟糕的最坏情况性能,Skew Heap和Sply Tree具有最差的最坏情况.
- 哦1997动态懒人日历队列.改善传统CQ在不均匀事件分布上的表现
- 哦1999动态日历队列.适用于不均匀分布
- Cazzolla 1998 Java实现的Lazy Queue与分析(不是学术论文).
- Tan 2000 SNOOPy:用最佳操作参数CQ进行统计增强.使用统计测试制作一个ebtter桶.在某些情况下,操作速度比DCQ和CQ快100倍
- Hui Thesis学士论文描述了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 Ladder Queue.即使在具有无限方差的队列分布下,也提供稳定的O(1)性能.与Lazy Queue类似,但更好.
- 严2006年日历排队缓慢.当事件大多按顺序插入时,可以使用一些统计属性来实现2阶加速
- Himmelspach 2007活动有持续时间 - 在主要研究范围之外.需要额外的功能,该算法提供了它,但可能有限的后续工作.
此外,我们最近完成了描述Brown算法的变体,该算法应该表现得更好.描述是,我认为非常适合构建实现,本文提供了示例代码.该出版物Trading Space for Time: Constant-Speed Algorithms for Managing Future Events in Scientific Simulations由Lehman,Keene和Barnes 授权,并应在今年秋天的某个时候编入索引.如果您想要一份副本,请发表评论,我会将其发送给您.
要回答问题的不同部分,您可以将日历队列视为优先级队列,该队列针对优先级不断降低的事件进行了优化.通常,事件的优先级(时间)以某种方式被分箱,以避免必须触摸所有事件以便插入一个事件(在某些形式的堆管理中可能发生).