什么是日历队列？

发布于 2024-11-06 22:20:26 字数 166 浏览 0 评论 0原文

我正在致力于构建一个离散事件模拟器。维基百科提到有几种通用优先级队列非常适合在 DES 中使用。具体来说，它提到日历队列是一个很好的结构。我找到了一份 pdf（1988 年的），其中提到了日历队列，但在大多数情况下我找不到关于它们的任何其他内容。有人介意解释什么是日历队列、它们如何使用以及我可以在哪里找到示例实现吗？

原文

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

江湖正好 2024-11-13 22:20:26

是的，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 The Lazy Queue。具有近期、远期和非常远未来的日历队列 - 这可以实现延迟排序，从而在测试
Steinman 1994 Event Horizon 时大大加快速度。生成的事件在发生时具有一定的概率分布，让我们用它来确定需要排序的内容。允许并行模拟
Steinman 1996 Event Horizon Part 2。将 Steinman1994 应用于事件列表管理。修改 CQ 中使用的其他数据结构。
Ronngren 1997 许多不同日历队列的比较。 Lazy Queue 表现良好，但 Brown1988 通常表现更好。 LazyQ 和 SCQ 的最坏情况性能较差，Skew Heap 和 Sply Tree 的最坏情况性能最好。
噢，1997 年动态惰性日历队列。提高传统 CQ 在不均匀事件分布上的性能
Oh 1999 动态日历队列。适用于不均匀分布
Cazzolla 1998 Lazy Queue 的 Java 实现及分析（不是学术论文）。
Tan 2000 SNOOPy：通过最佳操作参数 CQ 进行统计增强。使用统计测试来制作一个 ebtter 桶。在某些情况下，运行速度比 DCQ 和 CQ 快 100 倍
Hui 论文学士论文描述了 Hui 2002 论文的更多细节以及其他日历队列实现的优缺点
Hui 2002 未来事件现在不需要排序；因此，可以限制优先级队列本身的大小，从而减少调整大小的开销。
Goh 2003 MList。多层链表消除了调整大小操作。实验证明比 Calendar Queue、Dynamic CQ、SNOOPy CQ、2 层 Dynamic Lazy CQ 和 3 层 Lazy Queue
Siangsukone 2003 优化 CQ 中的存储桶宽度至少快 100%。证明铲斗宽度对性能有显着影响。
吴 2004 DSplay。消除成本高昂的调整大小操作。比其他日历队列至少快 100%。
唐 2005 年阶梯队列。即使在具有无限方差的队列分布下也能提供稳定的 O(1) 性能。与惰性队列类似，但更好。
Yan 2006 日历队列缓慢。当事件大部分按顺序插入时，可以使用一些统计属性来实现 2 阶加速
Himmelspach 2007 事件有持续时间 - 在研究的主线之外。需要额外的功能，该算法提供了它，但后续工作可能有限。

另外，我们最近完成了对布朗算法的一种变体的描述，它应该表现得更好。我认为该描述足以构建一个实现，并且本文中提供了示例代码。该出版物的标题为《用空间换时间：科学模拟中管理未来事件的恒速算法》，作者为 Lehman、Keene 和 Barnes，应该会在今年秋天的某个时候被编入索引。如果您想要一份副本，请发表评论，我会将其发送给您。

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

Yes, Brown 1988 is the first paper I know of to describe calendar queues, though Brown mentions several authors who preceded him. Below is a relatively complete bibliography of the calendar queue literature along with my notes on each paper. Leave me a comment if you would like copies of any of the publications.

Vaucher 1975 Comparison of events list algorithms. Presents three new algorithms as well. Inspired Brown1988.
Henricksen 1977 Events list algorithm - adapts to interval times and performs well with a number of distributions, based on Vaucher and Duval
Ulrich 1978 Brown1988 claims this is O(1), except for the overflow list
Jones 1986 Compares priorities queues, has an early version of a calendar queue
Brown 1988 Introduces Calendar Queue [aka: Sorted-discipline Calendar Queue]
Davison 1989 Discovers the same, mentions some important improvements, Brown acknowledges the improvements in the same letter and has some thoughts of his own. Davison suggests that Jones 1986 has offered some valuable calendar mechanics
Ronngren 1991 The Lazy Queue. A calendar queue which has a near, far, and very far future - this enables delayed sorting, which speeds things up considerably in their testing
Steinman 1994 Event Horizon. Generated events have some probability distribution of when they occur, let's use this to determine what needs to be sorted. Allow for parallel simulation
Steinman 1996 Event Horizon Part 2. Applies Steinman1994 to event list management. Modifies other data structures for use in CQs.
Ronngren 1997 Comparison of many different calendar queues. Lazy Queue performs well, but Brown1988 frequently performs better. LazyQ and SCQ have bad worst-case performance, Skew Heap and Sply Tree have best worst-case.
Oh 1997 Dynamic Lazy Calendar Queue. Improve's conventional CQ's performance over uneven event distributions
Oh 1999 Dynamic Calendar Queue. Works well with uneven distributions
Cazzolla 1998 Java implementation of Lazy Queue with analysis (not an academic paper).
Tan 2000 SNOOPy: Statistically enhanced with optimum operating parameter CQ. Uses statistical tests to make a ebtter bucket. Operates up to 100x faster than DCQ and CQ in certain scenarios
Hui Thesis Bachelor's thesis describing many more details of the Hui 2002 paper along with pros and cons of other calendar queue implementations
Hui 2002 Future events don't need to be sorted right now; consequently, the priority queue proper's size can be limited, reducing resize overhead.
Goh 2003 MList. Multi-tier linked-lists eliminate resize operations. Shown experimentally to be at least 100% faster than Calendar Queue, Dynamic CQ, SNOOPy CQ, 2-tier Dynamic Lazy CQ, and 3-tier Lazy Queue
Siangsukone 2003 Optimised bucket widths in CQ. Demonstrates that bucket width can have significant effects on performance.
Goh 2004 DSplay. Eliminate costly resize operations. At least 100% faster than other calendar queues.
Tang 2005 Ladder Queue. Provides stable O(1) performance even under queue distributions with infinite variance. Similar to Lazy Queue, but better.
Yan 2006 Sluggish calendar queue. When events are mostly inserted in order, it is possible to use some statistical properties to acheive a 2-order speed-up
Himmelspach 2007 Events have durations - outside the main line of research. Extra functionality was needed, this algorithm provides it but may have limited follow-up work.

Also, we've recently finished describing a variant of Brown's algorithm which should perform better. The description is, I think quite adequate to build an implementation from and sample code is provided in the paper. The publication is entitled Trading Space for Time: Constant-Speed Algorithms for Managing Future Events in Scientific Simulations by Lehman, Keene, and Barnes and should be indexed sometime this fall. If you'd like a copy, leave a comment and I will send it to you.

To answer a different part of your question, you can think of a calendar queue as being a priority queue which is optimized for events which will have ever-decreasing priorities. Usually the priorities (times) of the events are binned in some way so as to avoid having to touch all the events in order to insert one (as may happen in certain forms of heap management).

回复收藏 0 原文

千纸鹤带着心事 2024-11-13 22:20:26

谷歌搜索找到了

离散事件日历队列中优化桶宽度的研究
模拟器

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

第 2 节描述了日历队列。

回复收藏 0 原文

吻风 2024-11-13 22:20:26

NIST 的定义：

一种快速优先级队列实现，具有 N 个桶，每个桶的宽度为 w，或覆盖 w 时间。优先级 p 大于当前优先级的项目进入存储桶 (p/w)%N。选择 N 和 w 以使每个桶中的项目较少。将物品分类在桶内。如果项目数量增加或减少很多，则将 N 加倍或减半并更改 w。

Paul E. Black，“日历队列”，《算法和数据结构词典》[在线]，Vreda Pieterse 和 Paul E. Black 编辑。 2005 年 1 月 24 日。（访问时间：2014 年 3 月 10 日）可从：http://www.nist.gov/dads/HTML/calendarQueue.html" rel="nofollow">http://www. nist.gov/dads/HTML/calendarQueue.html

回复收藏 0 原文

~没有更多了~