algorithm - 什么是 Franta-Maly 活动列表？

Question

此问题的最佳答案引用了 Franta-Maly 事件列表。什么是 Franta-Maly 事件列表，它的用例是什么？

标签： algorithmcron

Answer 1

Franta-Maly 事件列表（或事件集）由 WR Franta 和 Kurt Maly 在 1977 年的一篇论文中描述，An Efficient Data Structure for the Simulation Event Set。在本文中，他们提出了一种新的事件调度算法，该算法改进了以前发布的算法。根据摘要：

首先，新算法的性能对偏态分布非常不敏感，其次，它的最坏情况复杂度为 O(sqrt(n))，其中 n 是集合中的事件数。此外，为估计平均复杂性而进行的测试表明它几乎与 n 无关。

该论文介绍了作者所谓的用于将事件插入事件集中的 TL（两级）算法：

除去其模拟术语，我们需要一个有效的解决方案来解决以下问题：为动态变化的记录集合设计一个物理数据结构，该结构支持使用最小值键检索记录。在模拟环境中，记录是事件通知，每一个都包含识别事件的信息，关键是事件发生的预定时间。预定的时间称为事件时间，记录的收集器¹称为事件集。

...

TL 算法的基本思想是限制为插入而必须扫描的通知数量。通过为每个间隔动态创建辅助密钥列表并将它们与右边界虚拟密钥相关联来满足此要求。每个二级键都指向一个区间内通知子列表的开头......每当这些子列表中的一个变得不平衡，即太大时，通过将通知移动到相邻列表或创建一个新的子列表来调整结构关联的辅助键。

^{1 我想建议，也许“记录收集者”是原始论文中的一个错字，而“记录收集”可能是这里的意图。}

Franta-Maly 论文的链接：http://staff.ii.pw.edu.pl/~gjb/aal/index_lists.pdf

---

^{注意：此答案的引用部分受以下版权声明的约束：}

^{ACM 通讯，1977 年 8 月，第 20 卷，第 8 期。版权所有 (c) 1977，计算机协会，Inc. 重新发布本材料的全部或部分内容的一般许可，但不以营利为目的，前提是 ACM 的版权声明已给出并提及该出版物、其发行日期以及经计算机协会许可授予的重印特权这一事实。作者地址：明尼​​苏达大学计算机科学系，明尼阿波利斯，明尼苏达州 55455。}